구사과

가중치 있는 방향 그래프 $G$ 에서 두 정점 $s, t$ 가 쿼리로 주어질 때, $s$ 에서 $t$ 로 가는 최단 경로를 구하는 문제를 흔히 모든 쌍 최단 경로 문제 (All-Pair Shortest Path, APSP) 문제라고 부른다. APSP 문제는 그래프 이론의 기초적인 문제 중 하나로, Floyd-Warshall Algorithm을 사용하여 $O(n^3)$ 시간에 해결하는 방법이 아주 잘 알려져 있으며 알고리즘을 공부하다 보면 누구나 접하게 될 기초 알고리즘 중 하나이다. Floyd Warshall Algorithm은 APSP 문제에 대해서 다음과 같은 자료구조를 만드는 알고리즘이라고 볼 수 있다: 자료 구조의 초기화에는 $O(n^3)$ 이 걸린다. 자료 구조는 $O(n^2)$ 의 메모리를 사..

You're gonna lose! You have to lose... You have to learn how to die (Yankee Hotel Foxtrot, 2001)

원래 한 150점 어치 풀이를 적어놓은 게 있었는데, 포맷하다가 글이 사라져서 더 이상 글을 쓰고 싶지 않았다. 그래도 아예 안 적을 수는 없으니 늦게나마 글을 작성해 본다. 문제 풀이 한 줄 요약 육각형 영역: 다각형 내부의 모든 격자점 간의 거리 합을 구하는 문제로 환원할 수 있다. 다각형의 3개의 축을 분리하여 생각하면, 각 축에 대해서 삼각분할과 비슷한 일종의 트리를 형성할 수 있고, 모든 경로가 이 트리 상의 유일한 경로로 환원됨을 관찰할 수 있다. BST에 Plane sweeping을 사용하여 이러한 트리를 빠르게 구성한 후 트리 안에서 동적 계획법을 수행할 수 있다. 밀림 점프: Cartesian tree 형태의 그래프에서 최단 경로 쿼리를 빠르게 해결하는 문제이다. 기본적으로 그래프의 Tr..

https://www.acmicpc.net/problem/19021 트리를 DFS하면서, 노드의 방문을 시작한 시점에 (, 끝내는 시점에 ) 를 붙이는 식으로 올바른 괄호 문자열을 만들어 줄 수 있습니다. 주어진 입력을 트리가 아니라 괄호 문자열이라고 생각하면 1, 2번 연산은 짝이 맞는 괄호 쌍을 추가하는 것이고 3번 연산은 짝이 맞는 괄호 쌍을 제거하는 것 으로 볼 수 있습니다. Edit Distance와 LCS의 관계처럼, 두 괄호 문자열의 최대 공통 부분 괄호 문자열을 찾아 줍시다. $T_1$ 의 모든 괄호를 제거 / $T_2$ 의 모든 괄호를 추가하는 비용을 미리 지불했다고 하면, 두 괄호 $A, B$ 를 매치했을 때의 비용은 $C_3 \times \text{(A, B를 매칭하는 데 드는 비용)..

https://www.acmicpc.net/problem/19616 모든 상태를 중 가중치가 가장 작은 $K$ 개를 탐색할 때 좋은 전략은, 상태 전이 그래프를 Heap과 같이 구성하는 것입니다. 몇 가지 특수 케이스를 탐색해 보고 전체 문제로 확장시켜 봅시다. $M = 1, x_1 = 0, y_1 = N$, 제곱 풀이 우리는 모든 가능한 $2^N$ 개의 집합 중 가중치가 가장 작은 $K$ 개를 탐색해야 합니다. 탐색 트리를 만드는데, 만약에 모든 상태가 가능한 집합에 일대일 대응되고 상태 $X$ 의 자식은 항상 현재 상태 이상의 가중치를 가지며 전이가 트리의 형태를 띈다 라고 하면, 루트 상태를 먼저 우선순위 큐에 넣은 후, 큐에서 현재 상태를 빼고, 현재 상태의 "자식 상태" 를 넣는 식으로 모든 가..

CCC 2017 S2. High Tide Low Tide 입력으로 들어온 수열을 정렬한 후, 만조때는 중앙값부터 감소하는 순서대로, 간조일때는 중앙값부터 증가하는 순서대로 출력합니다. $n = 2k + 1$ 이면: a[k+1] a[k+2] a[k] a[k+3] ... a[2] a[2k+1] a[1] $n = 2k$ 이면: a[k] a[k+1] a[k-1] a[k+2] ... a[1] a[2k] VKOShP 2017 A. Tourism 웬만하면 굉장히 큰 답을 찾을 수 있다는 게 핵심 포인트입니다. 만약 $S[1] = S[N]$ 이면 답은 $[1, N-1], [2, N]$ 입니다. 아니면, $S[1] = S[2] = \ldots = S[i]$ 가 만족하는 최대 $i$ 와 $S[N-j+1] = S[N-j+2..

대회 후기 일단 시작하고 나서 코딩하지 않고 이 글부터 썼다. 이 후 이 글을 따라서 코딩했는데 2번, 4번, 5번을 틀렸다. 2번은 큰 자릿수가 앞에 있다는 걸 몰랐다. 순서를 바꿔서 맞았다. 4번은 88점이 나오기에 풀이가 틀렸나 했다. 5번은 그냥 코딩 실수가 좀 있었고 고쳐서 맞았다. 698/800점을 받고 잤다. R2를 어쨌든 갈 거 같아서 고칠까 말까 하다가, 만점자가 꽤 많아서 무섭기도 하고, 블로그에 "이런 풀이를 짰는데 틀렸더라 ㅎㅎㅋㅋㅈㅅ" 라고 글을 쓰기는 뭐해서 4번을 생각해봤다. 설마 싶은 반례가 있었는데 머릿속으로는 이게 반례인지 아닌지 긴가민가했다. 짜 보다 보니까 반례인게 확실해 보였다. 고쳐서 오후 1시 반쯤 만점 1. 친구들 말이 복잡하지만 이런 뜻입니다. $N$ 개의 정..

IOI 2021 Day 2 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 최종 성적은 다음과 같다. 메달 결과는 1금 2은 1동이다. 반딧불, 100 / 67 / 70 / 100 / 62 / 75, 474점, 7등, 금메달 송준혁, 38 / 37 / 100 / 100 / 50 / 46, 371점, 31등, 은메달 최서현, 100 / 9 / 5 / 100 / 89 / 33, 336점, 47등, 은메달 장태환, 11 / 37 / 70 / 100 / 11 / 21, 250점, 122등, 동메달 Day 1의 만점자인 Mingyang Deng이..

IOI 2021 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다.한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라.반딧불, 100 / 67 / 70, 237점, 7등 - 11등송준혁, 38 / 37 / 100, 175점, 28등 - 29등장태환, 11 / 37 / 70, 118점, 71등 - 100등최서현, 100 / 9 / 5, 114점, 102등Day 1 만점자는 중국의 Mingyang Deng이 유일하다. 전체적으로 예년에 비해서 난이도는 어려운 편이다. 점수판을 보았을 때 올해는 세 ..

방향 그래프 $G$ 에 대해서, $G$ 의 위상 정렬 $O: V \rightarrow [n]$ 은 모든 간선 $u \rightarrow v$ 에 대해서 $O(u) < O(v)$ 가 성립하는 순열로 정의된다. $G$ 의 위상 정렬이 존재하기 위해서는 $G$ 가 사이클이 없어야 한다는 사실이 잘 알려져 있다 (Directed Acyclic Graph, DAG). 방향 그래프에 사이클이 없다면, 위상 정렬을 적용할 수 없다. 이 경우에는 그래프에 대한 강연결 컴포넌트 (SCC) 를 구해서 사이클을 하나의 정점으로 묶어주고, 이 DAG에서 위상 정렬을 적용하는 방법이 자주 사용된다. 위상 정렬과 SCC는 방향 그래프에서 사용하는 가장 기초적인 알고리즘 중 하나이며, 그 중요성에 대해서는 길게 설명하지 않겠다. ..