devbelly

문제 https://www.acmicpc.net/problem/18785 알고리즘 DFS 풀이 Bessie가 트리위에 주어진 맵을 이동해가며 시계를 조정할 때, 모든 시계가 가르키는 시간이 12시가 되도록 할수 있는 방의 시작갯수를 구하는 문제입니다. 임의의 출발지에서 모든 노드가 12가 될 수 있는지를 확인하는 것이 목표입니다. $N$제한이 2500이므로 $O(N^2)$에 근접하는 알고리즘을 떠올려봅시다. 첫 번째로는 리프노드의 시간을 12시로 맞추기 위해서는 무조건 리프노드와 리프노드의 부모를 계속해서 왔다갔다 해야지만 리프노드를 원하는 숫자 12로 맞출 수 있습니다. 12로 설정된 리프노드는 우리의 관심사 밖이므로 제거되고 리프노드의 부모였던 노드는 새로운 리프노드가 됩니다. 위 시뮬레이션을 계속 ..

문제 https://www.acmicpc.net/problem/20970 알고리즘 Graph 풀이 $N$마리의 소가 $K$번 자리를 바꾸는 것을 계속 반복할 때, 각 소가 차지했던 위치의 수를 구하는 문제입니다. $K$번 자리를 바꾸는 것을 한 사이클이라고 하겠습니다. 하나의 사이클을 반복하면 아래와 같은 결과를 얻을 수 있습니다. 1번째 있는 소는 3, 3, 2 번째를 들른 후 한 사이클이 끝나면 4번째에 있는 곳에 위치하게 됩니다. 아래 2,3,4,5 번째 소들도 마찬가지로 그림을 해석하면 됩니다. 이 사이클을 계속 반복했을 때 원래 자리로 돌아오도록 시뮬레이션하면 답을 구할 수 있습니다. 아래 사진은 1번째소를 시뮬레이션한 결과입니다. 파란색 원들이 각각 시작점과 끝점입니다. 그 사이에 들렀던 노란..

문제 https://www.acmicpc.net/problem/20649 알고리즘 DP, Sorting 풀이 x, y 좌표가 모두 다른 소들의 좌표가 주어졌을 때, 각 소들의 잘못 점수(?)를 구하는 문제입니다. 문제를 관찰하면 동쪽으로 이동하는 소들 $A$는 북쪽으로 이동하는 소들 $B$중에서 $A$보다 오른쪽에 있으면서 아래 있는 소들에게 막히는지 안 막히는지 확인해야 하고 반대로 $B$는 $B$보다 왼쪽에 있으면서 위에 있는 소들에게 막히는지 안 막히는지 확인해야 합니다. 그래프가 DAG의 형태를 띠는 것에서 DP를 착안합시다. 이차원 포문을 통해 모든 소들의 쌍을 검사하며 각 소들의 관계를 따져보도록 합시다. 하지만 소들을 정렬하지 않은 채 무작정 이차원 포문을 통해 각 소들의 관계를 따지게 되면..

문제 www.acmicpc.net/problem/6068 알고리즘 Greedy 풀이 일을 처리하는데 걸리는 시간, 일의 마감기한이 주어졌을 때 일을 시작해야하는 가장 늦은 시간을 구하는 문제입니다. 일을 마감기한에 딱 맞춰서 끝내는 것이 일을 가장 늦게 시작할 수 있을 것입니다. 마감기한이 가장 늦은 일부터 마감시간에 딱 맞게 일을 역순으로 처리해나가며 현재시간과 다음으로 처리해야할 일의 마감기한중 작은 값을 현재시간으로 취해나가며 시뮬레이션 하면 됩니다. 코드 #include #define rep(i, n) for (int i = 0; i N; rep(i, N) { int a, b; cin >> a >> b; vt.e..

문제 www.acmicpc.net/problem/20968 알고리즘 Dijkstra 풀이 소의 품종마다 서로 연락할 수 있는 관계가 주어졌을 때, 첫 번째 소가 맨 마지막 소에게 메시지를 전달하기 위한 최솟값을 구하는 문제입니다. 일반적으로 PQ를 이용한 다익스트라의 시간복잡도는 $O(ElogV)$입니다. 문제에서 $N$제한이 50000이므로 무작정 다익스트라를 사용하게 되면 시간 초과를 받게 됩니다. 빨간색 원이 현재 PQ에서 꺼낸 소라고 하겠습니다. 녹색은 빨간색 품종이 연락할 수 있는 품종을 의미합니다. 만일 위와 같이 녹색품종들이 모두 빨간색에서 메시지를 받을 수 있다면 굳이 첫 번째를 제외한 2, 3, 4번째들을 검사할 필요는 없습니다. 즉 현재 소에서 연락 가능한 품종들마다 가장 가까이 있는 ..

문제 www.acmicpc.net/problem/3015 알고리즘 stack 풀이 $N$명이 사람이 서있을 때, 서로 볼 수 있는 쌍을 구하는 문제입니다. 서로 보기 위해선 각 사람 사이에 그 사람들보다 큰 키가 존재해서는 안됩니다. 문제의 단순화를 위해 모든 키가 유니크하다고 가정하겠습니다. 파악해야할 것은 키의 구간이 내림차순으로 존재한다면 해당 구간은 추후에 매칭이 될 가능성이 있는 사람들입니다. 아래 그림은 이에 대한 예시로써, 흰색사람의 키가 내림차순인 형태입니다. 이후에 나오는 주황색 사각형과 흰색 사각형들이 매칭이 됩니다. 또한 빨간색 사각형처럼 자신의 왼쪽에 있는 사람이 자신보다 키가 크다면 무슨일이 있어도 주황색 사각형의 왼쪽부분과는 매칭이 될 수 없습니다. 이러한 특징을 파악해 오름차순..

문제 www.acmicpc.net/problem/20971 알고리즘 DP 풀이 특정 구간을 칠하지 않은 상태로 할 때, 남은 구간들을 칠하기 위한 최솟값을 구하는 문제입니다. 문제의 가장 큰 특징은 페인트를 칠하는 순서가 정해져 있다는 것입니다. 이를 유의하며 풀도록 합시다. 쿼리를 빠르게 처리하기 위해 DP 아이디어를 떠올렸습니다. 특정 구간에 대한 DP를 사용하기 위해선 $cache[i][j]$와 같은 배열을 사용할 수 있는데, 구간의 길이가 100,000 이라는 점에서 해당 2차원 배열을 사용하기는 어렵습니다. 하지만 문제를 자세히 보면 특정 구간을 칠하기 위한 최솟값이 아닌 특정 구간을 제외한 나머지 구간을 칠하기 위한 최솟값을 묻고 있습니다. 이는 DP의 정의가 "앞에서부터 길이 $N$인 구간을..

문제 www.acmicpc.net/problem/18320 알고리즘 이분탐색 풀이 갚을 금액, 기한, 하루에 최소 갚을 금액이 주어졌을 때, 조건을 충족하는 $X$를 구하는 문제입니다. 문제를 풀기 위한 첫 번째 단계는 $X$를 결정해야하는 것입니다. 결정문제는 이분탐색으로 바꿀 수 있습니다. 이 문제가 어려운 이유는 $X$를 결정했을 때, 그대로 시뮬레이션하여 $K$일 이내에 돈을 갚을 수 있는지 계산하게 되면 시간초과가 발생하기 때문입니다. 이유는 $N$제한이 $10^{12}$이기 때문입니다. $X$를 결정하는 시간복잡도는 $O(logN)$에 해당하는데 그대로 시뮬레이션 하게 되면 $X$마다 선형시간이 요구되기 때문입니다. 한가지 할 수 있는 관찰 중 하나는 John이 갚아나가는 금액은 비오름차순의 ..