알고리즘

문제 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 다익스트라에 경로 추적을 결합한 문제이다. 출력 시, 각 집하장에서 다른 집하장까지의 최단 경로가 필요하므로 각 집하장마다 다익스트라를 실행해야 한다. 다익스트라 도중에 최단 경로가 갱신될 때, 현재 노드의 부모 노드를 갱신한다. next_node를 최단 경로로 도달하기 위해서는 current_node애서부터 와야 한다. 부모 노드를 추적하면 한 집하장에서 다른 집하장으로 최단 경로로 갈 때, 바로 다음 집하장을 알 수 있다. 코드 #include #inclu..

문제 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 풀이 다익스트라 문제이다. 도로를 하나의 그래프로 생각하는데 주목한다. 그래프의 노드는 바로 다음 노드와 거리가 1로 연결되어 있다. 위의 그래프에서 입력 받은 지름길을 추가한다. 역주행 할 수 없으므로, 지름길의 끝이 D를 넘어간다면 그래프에 추가하지 않는다. 지름길의 거리가 시작과 끝의 거리보다 길다면, 거리를 줄일 수 없으므로 그래프에 추가하지 않는다. 그래프를 0에서부터 다익스트라를 통해 D까지의 최소 거리를 구한다. 코드 #include..

문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 다익스트라 문제이다. 첫 시도에는 s를 시작점으로 다익스트라를 한번 실시하고, 경로를 추적하여 시도하였지만, 메모리 초과가 발생하였다. 그리고 이 방법은 x까지의 최단 경로가 여러 개 존재할 경우, 답이 올바르지 않을 수 있다. s, g, h를 시작점으로 다익스트라를 세번 실시한다. s -> g -> h -> x로 가는 최단 경로의 비용이 s -> x로 가는 최소 경로의 비용과 일치한다면, 해당 최소 경로는 g -> h를 거친다고 볼 수 있다. ..

문제 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 풀이 다익스트라 문제이다. b가 감염되고 s초 후, a가 감염된다는 뜻은, 노드 b에서 노드 a로 가는 간선의 비용이 s라는 뜻이다. 위의 조건대로 그래프를 만들고 c를 시작으로 다익스트라를 실시한다. c에서 갈 수 있는 컴퓨터의 수와 최대 거리를 구한다. 코드 #include #include #include #include #include using namespace std; vector edges; vector dist; void solution(int st..

문제 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 [백준][C++] 1261: 알고스팟 문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의 kantatatam.tistory.com 너비 우선 탐색 문제로, 위의 문제와 풀이가 동일하다. 하나 주의해야 할 점은, 시작 지점의 거리가 0이 아니고, 시작 지점의 도둑 루피..

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 너비 우선 탐색 문제이다. 다익스트라로 시도를 했을 때, 메모리초과와 시간초과가 발생하여 너비 우선 탐색으로 변경하였다. 미로의 각 칸을 하나의 노드로 생각하고, (0, 0)칸부터 탐색한다. 현재 노드의 상하좌우를 탐색한다. 탐색하는 노드까지의 거리는 현재 노드까지의 거리에서 벽이 있다면 +1 없다면 +0이다. 탐색하는 노드의 거리를 갱신할 수 있다면 갱신하고, 큐에 넣는다. 거리를 나타내는 배열이 2차원 배열임을 주목하자. 코드..

문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 구현, 시뮬레이션, 큐 문제이다. 뱀의 머리, 꼬리, 몸통의 정보를 따로 저장해둔다. pair head = make_pair(0, 0); // 현재 머리의 위치 pair tail = make_pair(0, 0); // 현재 꼬리의 위치 queue body; // 사과를 먹지 못했을 때, 줄어들 꼬리의 위치가 front snake[0][0] = true; // 뱀이 있는 영역을 표시 이동 후 머리의 위치를 queue에 넣어둔다. 이동 후 사과를 먹지 못했다면,..

문제 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 이분 탐색 문제이다. 세 수의 합을 4중 for문을 이용하면 시간복잡도가 O(N * N * N * N)으로 당연히 시간초과다. x + y + z = k x + y = k - z x + y + z = k는 x + y = k - z와 같다. 여기서 x + y를 2중 for문으로 미리 구해둔다. 미리 구한 합에서 k - z를 만족하는 값을 이분탐색으로 찾으면 시간복잡도가 O(N * N * log(N))이 므로..

문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 풀이 구현, 시뮬레이션 문제이다. 로봇 청소기가 후진하지 못할 때까지 while로 무한 루프를 돈다. 현재 위치의 상하좌우에 청소 가능한 칸이 있는지 확인한다. 북, 동, 남, 서 방향으로 이동할 때의 x, y의 위치 변화는 다음과 같다. // 북, 동, 남, 서 int move_x[4] = { -1, 0, 1, 0 }; int move_y[4] = { 0, 1, 0, -1 }; 청소 가능한 칸이 있다면 반시..

문제 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 풀이 두 포인터 문제이다. 두 포인터를 이용하여 start를 포함하며 반복되는 수가 없는 수열의 경우의 수를 계산하는 방식으로 해결한다. start부터 중복되는 수가 없을 때까지 end를 늘린다. 혹은 end가 N까지 도달하여 더 이상 수열을 늘릴 수 없을 때까지 늘린다. start에서 end까지 start를 포함하여 만들 수 있는 수열의 개수는 end - start개이다. 이 개수를 answer에 추가한다. 그 다음, start를 앞으로 늘려서 1번부터 반복한다...