본문 바로가기

백준

 (223)
백준 17409 - 증가 수열의 개수 https://www.acmicpc.net/problem/17409 Intro 적당히 작은 N에 대해서는 DP[k][n] := n번째 수에서 LIS의 길이가 k인 경우의 수로 정의하여 $O(KN^{2})$ DP로 해결할 수 있다고 알려져 있다. 스택 오버플로우 다만 이 문제에서는 $N \leq 100000$ 이므로 무식하게 다중 반복문을 돌릴 수 없을 것이다. 어떻게 해야 할까? 아이디어 이 게시글 중반부에서 LIS를 세그먼트 트리로 구하는 법을 소개하고 있다. 이를 잘 응용하면 naive 한 DP를 수행하는데 걸리는 $O(N^{2})$ 시간 복잡도를 $O(N \log N)$으로 줄여볼 수 있지 않을까? 우리는 세그먼트 트리를 이용하여 n 이하의 수로 이루어지고 길이가 k의 수열의 개수를 관리할 것이다...
[ICPC] 백준 5012 - 불만 정렬 https://www.acmicpc.net/problem/5012 문제를 해결하기 위해 펜윅 트리에 다음 정보를 관리할 것이다. 현재 순회 중인 index에 해당하는 값 val 이상의 값이 출현하는 횟수 그러면 val을 pivot으로 할 때 구간은 다음과 같이 표현될 수 있다. [val보다 작은 index에서 val 이상의 값이 나타나는 횟수), val, (val 보다 큰 index에서 val 이상의 값이 나타나는 횟수] 이렇게 되면 왼쪽 구간에서 큰 수를 선택하는 경우와 오른쪽 구간에서 작은 수를 선택하는 경우를 곱셈법칙으로 계산하여 왼쪽 구간의 값 * (오른쪽 원소의 갯수 - 오른쪽 구간의 값)를 각 pivot마다 더해주어 답을 구할 수 있다. 하지만 이렇게 하면 왼쪽 구간에서 val보다 큰 값이 있..
[COCI] 백준 3006 - 터보 소트 https://www.acmicpc.net/problem/3006 Intro 문제를 잘 읽어보면 칵테일 정렬과 비슷한 논리로 진행됨을 이해할 수 있다. 그렇다고 진짜 칵테일 정렬을 수행하면 $O(N^{2})$의 시간복잡도로 참사가 일어날 것이 분명하다. 그렇다면 우리는 이 문제를 어떻게 풀어야 할까? 아이디어 위 gif 이미지를 보면 배열의 양 끝이 정렬되는 것을 알 수 있다. 그리고 우리는 정렬된 부분을 다시 건드리지 않는 것이 최적임을 너무나도 잘 알고있다. 이를 바꿔서 생각하면 터보 소트의 동작이 수행될 때마다 나머지 원소들이 정렬을 위해 이동해야 할 최대 거리가 1씩 줄어든다는 것이다. 그렇다면 정렬이 진행되는 과정에서 각 원소가 이동해야 하는 거리를 효율적으로 계산하면 괜찮을 거라는 생각을 할 ..
백준 18249 - 욱제가 풀어야 하는 문제 https://www.acmicpc.net/problem/18249 아이디어 문제에서 말한 그래프를 그려보자 문제의 요구사항에 맞춰 N개의 간선을 직접 선택하다 보면 다음 사실을 발견할 수 있다. 그래프를 위 그림처럼 보고 평행한 두 정점을 한 줄이라 취급했을 때 N개의 간선을 선택하면 N번째 줄까지 도달한 상태여야 한다. 즉 N개의 간선을 선택하는 방법은 N번째 줄에 도달하는 방법과 동치이며 한 줄을 잇는 한 줄 간선이나 4개의 정점을 교차하여 잇는 쌍칼 간선을 적절히 선택하여 N번째 줄에 도달하는 방법을 생각하면 된다. 쌍칼이 아니라 대각선 간선으로만 배치하는 경우 N개의 간선을 선택할 수 없다. 우리는 이 발견으로 다음 점화식을 세울 수 있다. $f(n) = f(n - 1) + f(n - 2) \;..
[COCI] 백준 2836 - 수상 택시 https://www.acmicpc.net/problem/2836 관찰 사람을 어떻게 태우던지 목적지에 도착해야 되므로 최소 M만큼의 거리를 이동한다. 어차피 배도 M으로 향해야 하므로 M방향으로 가는 사람들은 무시하고 역방향으로 가는 사람만 고려하면 된다. 역방향으로 가는 사람들은 어떻게 되는걸까? 한번 지나간 곳을 또 지나가는 것은 최적해에 도달할 수 없음을 떠올릴 수 있고 그러면 사람이 오르내리는 사건이 발생하는 최대 구간을 만드는 것을 생각할 수 있다. 최적해에 관한 예시로 5와 7 지점에서 역방향으로 가려는 손님이 있는데 5를 태운 다음 7을 태우지 않고 뒤로 돌아간다면 7을 태우기 위해 다시 그만큼 거리를 이동해야 하므로 최적해가 아님을 알 수 있다. 따라서 스위핑을 통해 역방향 노선을 적절히..

티스토리툴바