PS 이야기

대한민국 ICPC 문제들은 데이터와 솔루션이 공개되지 않는다. 때문에 온라인 저지에서 한국 ICPC 문제들을 보기 힘들다. Baekjoon Online Judge 에서 간혹 한국 ICPC 문제들이 보인다. 어둠의 경로(?)로 데이터를 입수하는 방식이 아닌 관리자 혹은 회원이 데이터를 직접 만들어서 등록하는 방식으로 진행되는 것 같다. 그 곳에서 인터넷 예선 공부하기 너무 편했고, 그에 보답하기 위해 이번 인터넷 예선 데이터들을 만들어 보..

$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$까지 모두 방문했고 마지막..

이 문제는 전형적인 '가중치가 있는 이분매칭' 이다.이러한 이분 매칭을 푸는데는 크게 두 가지 방법이 있다.MCMF(Minimum cost & Maximum flow)와 헝가리안 메소드(Hungarian method) 가 있다.필자는 헝가리안 메소드를 푼지 오래되어 이 문제를 MCMF로 해결했다. 이 문제에서는 두 매치 사이에 간선이 없는 경우가 있어서 헝가리안 메소드로 풀릴 수 있는지 헷갈릴 정도로 헝가리안 메소드에 대해 모른다.MCMF가 ..

전형적인 이분매칭 문제다.대회 끝나고, 단순히 '매칭'이라고만 들었을 때는 전혀 와닿지 않았고 해법이 떠오르질 않았다. 그래프를 어떻게 구성해야되는 것이며 그래프를 어떻게 구성해야되는 것이며... 머리 속이 복잡했다.우선 이분 그래프의 양쪽에 0번 부터 $N-1$번까지 노드들을 총 $2N$개 만든다. i번 노드에서 j번 노드로 가는 방향성 에지가 있으면 이분그래프에서 왼쪽 i번 노드에서 오른쪽 j번 노드로 뻗는 간선을 그어준다.그 ..

문제에서 주어진 식을 그래프 DAG(Directed Acyclic Graph)로 잘 만들어주면, 비교적 쉽게 풀리는 문제다.한 마디로, 이 문제를 노가다성 문제라고 생각한다.DAG를 구성하는 방법은 구체적으로 설명하지 않겠다. 까다로울 수 있지만 특별한 알고리즘이 필요한 것도 아니고 사람마다 저마다의 방법이 있을 것이라 생각하기 때문이다.필자는 A(B|CD(E|_)G)E 가 입력으로 들어오면 아래와 같이 그래프를 구성했다.그래프를 구성 한 ..

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

이 문제는 말리면 꽤 시간이 많이 걸릴 듯 해보이는 문제다.대회 당시에는 나는 문제도 모른채, 팀원이 막힘 없이 풀어주었다.대회가 끝나고 글을 쓰기 위해 문제를 생각해보았는데, 생각하는데 오래 걸린 편이었다.이런 개미 문제 컨셉은 BOI? CEOI? 기출 문제에도 있다. 그 문제에서 중요한 점은 "개미의 충돌이 있어도 개미가 떨어지는 시점(시간)은 변함 없다." 이다. 이 문제에서도 꼭 필요한 아이디어다.추가 설명을 하자면..

두 개의 Priority Queue(heap) 를 이용해서 문제를 해결할 수 있다.하나는 max heap이고 하나는 min heap 이다.heap에 원소의 값과 동시에 index도 같이 pair로 삽입한다.그리고 pop 될 때 해당 index에 visit 체크를 해주고, 최대 최소 값을 구할 때에 이미 visit가 체크된 것은 무시해주면 된다.이러한 테크닉은 코딩이 편하며, 시간복잡도에 영향이 없다.하지만, 공간 복잡도에는 영향이 있지만 빅..

아직 풀지 못 했다.

한글 문제 부터 순서대로 훑어서 가장 먼저 풀게된 문제다. 처음에 수식으로 문제를 풀려하다가 시간이 오래걸릴 것 같아, $O(N)$에 풀게되었다. 생각은 해보지 않았지만, 분명 더 빠른 방법들도 존재할 것이다.우선 문제에서 $<x : y>$ 가 주어진다.이 때 가능한 연도는 $year = k \times N + y \space (0 \le k < M)$ 이다.따라서 k를 0 부터 M-1 까지 돌려보고 $year$ 를..