PS 이야기

대한민국 ICPC 문제들은 데이터와 솔루션이 공개되지 않는다. 때문에 온라인 저지에서 한국 ICPC 문제들을 보기 힘들다. Baekjoon Online Judge 에서 간혹 한국 ICPC 문제들이 보인다. 어둠의 경로(?)로 데이터를 입수하는 방식이 아닌 관리자 혹은 회원이 데이터를 직접 만들어서 등록하는 방식으로 진행되는 것 같다. 그 곳에서 인터넷 예선 공부하기 너무 편했고, 그에 보답하기 위해 이번 인터넷 예선 데이터들을 만들어 보았다. 시간 날 때 마다 만든다고 시작한 것이 하다보니, 상당히 많은 문제들의 데이터를 만들게 되었다. 과거 KOI 준비하면서 내 솔루션이 맞는지 검증하기 위한 프로그램을 C++로 코딩했었는데, 최근 들어서 python으로 하면 굉장히 편하다는 것을 느꼈다. KOI는 이제..

$O(N^2)$ Dynamic Programming 으로 풀린다.BOI 2009 beetle 문제와 매우 비슷한 문제이다. beetle 문제가 더 어렵고 이 문제는 더 간단하며, 다양한 풀이가 있을 것으로 예상된다.우선 다이나믹 배열의 정의는 아래와 같다.L[i][j] = $p_i$ 부터 $p_j$까지 모두 방문했고 마지막 방문 지점이 $p_i$일 때 ($i < j$)R[i][j] = $p_i$ 부터 $p_j$까지 모두 방문했고 마지막 방문 지점이 $p_j$일 때 ($i < j$)이 문제에서 N개의 점을 모두 방문해야한다. (i,j) 순서쌍이 있을 때 앞으로 몇 곳을 더 방문해야되는지 그 수를 계산할 수 있다. 앞으로 방문해야할 곳의 수를 $c$라 하자.이후 거리 $d$를 이동해야되면 가중치로 $d$가 ..

이 문제는 전형적인 '가중치가 있는 이분매칭' 이다.이러한 이분 매칭을 푸는데는 크게 두 가지 방법이 있다.MCMF(Minimum cost & Maximum flow)와 헝가리안 메소드(Hungarian method) 가 있다.필자는 헝가리안 메소드를 푼지 오래되어 이 문제를 MCMF로 해결했다. 이 문제에서는 두 매치 사이에 간선이 없는 경우가 있어서 헝가리안 메소드로 풀릴 수 있는지 헷갈릴 정도로 헝가리안 메소드에 대해 모른다.MCMF가 다루는 그래프는 일반 maximum flow 문제에서 다루는 그래프와 사뭇 다르다.maximum flow 에서 다루는 문제에서 그래프의 간선은 하나의 특성 값, 유량을 갖는다.하지만 MCMF에서 다루는 그래프에서 간선은 두 개의 특성 값, 유량과 비용을 갖는다.유량이..

전형적인 이분매칭 문제다.대회 끝나고, 단순히 '매칭'이라고만 들었을 때는 전혀 와닿지 않았고 해법이 떠오르질 않았다. 그래프를 어떻게 구성해야되는 것이며 그래프를 어떻게 구성해야되는 것이며... 머리 속이 복잡했다.우선 이분 그래프의 양쪽에 0번 부터 $N-1$번까지 노드들을 총 $2N$개 만든다. i번 노드에서 j번 노드로 가는 방향성 에지가 있으면 이분그래프에서 왼쪽 i번 노드에서 오른쪽 j번 노드로 뻗는 간선을 그어준다.그 뒤 최대 매치수가 곧 답이다.이 방법으로 답이 나오는 이유에 대한 자세한 설명은 생략한다.포트퍼거슨으로 짜도 시간안에 나올 수 있다. 하지만, Hopcroft-karp 알고리즘을 통해 최악에 $O(M \sqrt{N})$의 시간복잡도로 풀 수 있으며, 평균 시간복잡도 $O(M \..

문제에서 주어진 식을 그래프 DAG(Directed Acyclic Graph)로 잘 만들어주면, 비교적 쉽게 풀리는 문제다.한 마디로, 이 문제를 노가다성 문제라고 생각한다.DAG를 구성하는 방법은 구체적으로 설명하지 않겠다. 까다로울 수 있지만 특별한 알고리즘이 필요한 것도 아니고 사람마다 저마다의 방법이 있을 것이라 생각하기 때문이다.필자는 A(B|CD(E|_)G)E 가 입력으로 들어오면 아래와 같이 그래프를 구성했다.그래프를 구성 한 뒤에는 DP(Dynamic Programming)을 통해 해결하면 된다.그래프를 구성하는 노드의 개수를 $N$이라 하고, 입력으로 주어지는 두 번째 문자열의 길이를 $L$이라 하자.우선 그래프에서 위상정렬를 통해 각 노드의 순서를 구한 뒤 그 순서대로 처리한다.다이나믹..

따로 설명할 것 없이, 문제에서 주어진 조건대로 해결 하면 된다.한 사람의 등수를 계산하는 것이기 때문에 따로 정렬해줄 필요도 없다.문제 설명에 따라, 같은 시간에 이뤄진 제출이 없으므로, 같은 등수를 갖는 두 팀은 나올 수 가 없다.문제 이름은 KCPC지만, 등수를 배정하는 기준은 2013년도부터 시행된 KOI 기준과 동일하다.

이 문제는 말리면 꽤 시간이 많이 걸릴 듯 해보이는 문제다.대회 당시에는 나는 문제도 모른채, 팀원이 막힘 없이 풀어주었다.대회가 끝나고 글을 쓰기 위해 문제를 생각해보았는데, 생각하는데 오래 걸린 편이었다.이런 개미 문제 컨셉은 BOI? CEOI? 기출 문제에도 있다. 그 문제에서 중요한 점은 "개미의 충돌이 있어도 개미가 떨어지는 시점(시간)은 변함 없다." 이다. 이 문제에서도 꼭 필요한 아이디어다.추가 설명을 하자면, 개미의 충돌이 있고 두 개미가 서로 방향을 바꿔, 왔던 길을 다시 가더라도 멀리서 봤을 때, 충돌 없이 개미가 서로 지나쳐 가는 것이랑 다를 것이 없다.하지만 이 문제에서는 떨어지는 개미의 index를 알아야 한다.필자는 이 문제를 쉽게 생각했다가 말려 시간이 오래걸린 케이스다.또 ..

두 개의 Priority Queue(heap) 를 이용해서 문제를 해결할 수 있다.하나는 max heap이고 하나는 min heap 이다.heap에 원소의 값과 동시에 index도 같이 pair로 삽입한다.그리고 pop 될 때 해당 index에 visit 체크를 해주고, 최대 최소 값을 구할 때에 이미 visit가 체크된 것은 무시해주면 된다.이러한 테크닉은 코딩이 편하며, 시간복잡도에 영향이 없다.하지만, 공간 복잡도에는 영향이 있지만 빅오표기법 상으로는 영향이 없다.(Memory sensitive 한 문제에서는 직접 heap를 구현해야할 수도 있다.)처음에 문제를 각 쿼리마다 최대, 최소 값을 출력해야 되는 문제를 오해하고 생각해 보다 간단한 방법이 존재할 수도 있다.** 대회 때는 없던 크리티컬한 ..

아직 풀지 못 했다.

한글 문제 부터 순서대로 훑어서 가장 먼저 풀게된 문제다. 처음에 수식으로 문제를 풀려하다가 시간이 오래걸릴 것 같아, $O(N)$에 풀게되었다. 생각은 해보지 않았지만, 분명 더 빠른 방법들도 존재할 것이다.우선 문제에서 $$ 가 주어진다.이 때 가능한 연도는 $year = k \times N + y \space (0 \le k < M)$ 이다.따라서 k를 0 부터 M-1 까지 돌려보고 $year$ 를 구한 뒤 $x \equiv year (\bmod M)$인 경우가 있으면 그 $year$를 출력하면 되고, 아니면 -1을 출력하면 된다.자세히 적진 않았지만 modulo 연산을 통해 0이 나오면 M으로 바꿔주는 과정이 필요하다.