본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 11404번 : 플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬문제였습니다. 풀이방법 1. 출발점과 도착점이 같은 입력이 여러번 주어질 수 있으므로 더 작은 가중치를 가진 도시를 인접행렬 dist배열에 저장해줍니다. 2. 플로이드 와샬 알고리즘을 수행합니다. i -> k 도시로 가는 비용 + k -> j 도시로 가는 비용 보다 i -> j로 가는 비용이 크다면 갱신해줍니다. 3. 각 도시로 가는 최소비용을 출력합니다. Code #include #define I..
(C++) - 백준(BOJ) 1913번 : 달팽이 www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 구현문제였습니다. 풀이방법 1. (n/2, n/2) = 1로 시작합니다. 2. cnt가 n*n될때까지 cnt를 1씩 증가시켜주면서 방향을 전환해줍니다. 한 변을 채운다는 느낌으로 선언한 a배열에 cnt를 저장해주시면됩니다. 한 변을 채우고 나면 dir변수를 바꿔서 방향을 전환해줍니다. Code #include using namespace std; int n, x, y, dir, findNum, cnt = 1, p..
(C++) - 백준(BOJ) 1339번 : 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 모든 단어를 확인합니다. 매 단어마다 각 글자의 자릿수를 확인해 1의 자리라면 나온 알파벳의 가중치는 1이고 10의 자리라면 10, 100의 자리라면 100을 부여합니다. 이렇게 모든 알파벳별로 부여된 가중치의 값은 cost배열에 저장됩니다. 2. 해당 가중치와 알파벳이 저장된 cost배열을 보며 pair형태의 vector변수 v에 push해준 뒤 가중치가 큰 순으로..
(C++) - 백준(BOJ) 1916번 : 최소비용 구하기 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 문제였습니다. 풀이방법 1. 도시 사이에 연결된 간선과 가중치를 vector 자료구조 graph변수에 저장합니다. 2. 출발도시부터 i도시까지의 최소비용을 저장할 변수 dist배열 선언 후 모든 값을 큰수 INF로 초기화 합니다. 3. dijsktra 함수를 실행합니다. 3-1. dist[startCity] = 0 입니다. 출발도시의 최소비용은 0이기 때문입니다. 3..
(C++) - 백준(BOJ) 17144번 : 미세먼지 안녕! www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현문제였습니다. 풀이방법 매 초마다 다음과 같은 순서로 작동합니다. 1. 공기청정기의 방향을 잡아줍니다 : 바람의 방향을 dx,dy배열에 저장했습니다. 각자 상,우,하,좌에 해당합니다. 그 다음 방의 한칸마다 바람의 방향을 지정해주어 공기청정기 가동시 적절히 이동하도록 합니다. 2. 확산시킵니다 : 공기 청정기로는 확산되지 않습니다. 또한 동시에 퍼져야 하기 때문에 미세먼지가 이동하는 양과 확산 방향의 개수..
(C++) - 백준(BOJ) 1918번 : 후위 표기식 www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net stack으로 해결한 문제였습니다. 풀이방법 1. 정답을 출력할 string 변수 ans, 연산자를 넣어줄 stack op 변수를 선언합니다. 2. 입력받은 string 변수 str의 size만큼 loop를 돌며 다음을 수행합니다. 2-1. str[i] == '('면 무조건 op에 push 2-2. str[i] == ')'면 '('를 포함한 한블럭의 op를 pop() 2-3. str[i] == '*' ..
(C++) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[1차]) : 캐시 programmers.co.kr/learn/courses/30/lessons/17680#qna
(C++) - 백준(BOJ) 14659번 : 한조서열정리하고옴ㅋㅋ www.acmicpc.net/problem/14659 14659번: 한조서열정리하고옴ㅋㅋ 첫째 줄에 봉우리의 수 겸 활잡이의 수 N이 주어진다. (1 ≤ N ≤ 30,000) 둘째 줄에 N개 봉우리의 높이가 왼쪽 봉우리부터 순서대로 주어진다. (1 ≤ 높이 ≤ 100,000) 각각 봉우리의 높이는 중복 없이 www.acmicpc.net greedy 문제였습니다. 풀이방법 1. i번째 봉우리에서 시작합니다. 그 다음 i+1봉우리부터 끝까지 loop를 돌며 i번째 봉우리의 높이보다 작은 j번째 봉우리들의 개수를 세줍니다. 조건에 만족할 때마다 ans에 세준 개수를 저장합니다. 만약 반대라면 구간을 건너뛰기 위해 i = j-1을 저장하고 break;해줍니다. 2. ans를 출력합니다. Code #include..

티스토리툴바