구사과

8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = |S|, m = |T|$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le |S| - 1$ 에 대해, $LCS(S[i:] + S[:i], T)$ 의 값을 계산하는 문제가 된다. 이 문제는 일반적인 LCS 계산법을 사용하면 쉽게 $O(n^2m)$ 에 해결할 수 있으니, 이 글에서는 더 빠른 풀이를 논의한다. Circular LCS라는 문제는 경시대회에 간혹 등장하긴 하나, 이 문제 자..

GCJ 2008 World Finals A. Juice 사과와 바나나 주스의 비율로 가능한 후보는 $N^2$ 개입니다. 단순히 생각하면 $10000^2$개이지만, 사과의 비율을 $i$번째 사람을 만족시키는 최소 비율로 하고, 바나나 주스의 비율을 $j$번째 사람을 만족시키는 최소 비율로 하여도 문제가 없기 때문입니다. 사과, 바나나 주스의 비율을 고정하면 당근 주스의 비율이 $10000-A-B$와 같이 자동적으로 정해집니다. 사용할 사과 주스의 비율 $A$를 고정시킵시다. 이제 각각의 사람을 순서대로 고려합니다. 만약에 어떤 사람이 원하는 사과 주스의 비율이 $A$를 초과하면 무시해 줍니다. 그렇지 않은 경우, 이 사람이 원하는 바나나/당근 주스의 비율이 $B, C$ 라고 하면 $B_i \le B, C_..

4. Knuth's Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할 때 사용되었기 때문에 Knuth의..

동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다. 현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식 격차를 줄이는 데 도움을 주려 한다. 이 글을 읽을 때는 이 최적화 기법들이 단순히 동적 계획법에만 국한되어 있지 않다는 점을 유의하는 것이 좋다. 예시 문제로 올라와 있는 문제들도 동적 계획법과 상관이 ..

NEERC Northern Subregional 2015 A. Alex Origami Squares 일반성을 잃지 않고 $w \le h$ 라고 합시다. 두 가지 케이스가 있습니다: 세로로 길게 3개의 색종이를 늘어놓는 것. ㄴ자 모양으로 색종이 3개를 늘어놓는 것. 각 케이스에 대한 색종이의 길이는 단순 비교 연산과 나눗셈으로 계산 가능합니다. NEERC Northern Subregional 2015 J. Journey to the “The World’s Start” 먼저 몇 가지 사실을 짚고 넘어갑시다. 문제에는 출발지 방향으로 역행해도 된다고 되어 있으니, 굳이 역행을 해서 도움이 되는 경우는 없고, 목적지 방향으로 계속 움직이면 됩니다. 목적지 방향으로 계속 움직일 것이니, 이동에는 무조건 정확히 ..

Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으면서 $x, y$ 축에 평행한 가장 큰 정사각형은 무엇인가? D) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으면서 $x, y$ 축에 평행하고, 한 변이 $x$ 축에 포함되는 가장 큰 직사각형은 무엇인가? E) $..

소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 "어려운" 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다 빠른 알고리즘을 찾는 것은 쉽지 않다. 일반적으로 가장 자주 사용되는 알고리즘은 Pollard-rho라는 알고리즘이다. 이 알고리즘은 대회에 사용될 수 있을 정도로 복잡하지 않고, 평균 $O(N^{1/..

추석에 BOJ에서 13문제 연습 셋을 만들고 풀기로 결심했다. 아직은 그렇다 ㅋㅋ! 문제 A. Bridge Park B. Kangaroos C. Hotline D. Justice for All E. Farm and Factory F. Longest Rivers G. Conquer The World H. Uncrossed Knight's Tour I. Hashigo Sama J. 빛의 왕과 거울의 미로 1 K. 빛의 왕과 거울의 미로 2 L. Celtic Knots M. Farm Village 9월 9일 K. 빛의 왕과 거울의 미로 2 비트 DP와 비슷한 식으로 한 줄에 대한 상태를 저장하는데, 단순한 불리언 변수로는 부족하니까 연결 상태에 대한 union-find를 메모이제이션하는 느낌으로 해결할 수 있..

IOI 2019 Day 2 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. 김세빈, 100 / 100 / 40 / 72.30 / 66 / 57, 435.30점, Day2 27등, 전체 18등, 금메달. 윤교준, 72 / 100 / 40 / 90.97 / 66 / 57, 425.97점, Day2 16등, 전체 22등, 금메달. 임유진, 72 / 100 / 40 / 61.41 / 66 / 57, 396.41점, Day2 40등, 전체 37등, 은메달. 이온조, 38 / 100 / 64 / 50.61 / 52 / 24, 328.61점, Day2 120등, 전체 83등, 동메달. 미국의 Benjamin Qi는 작년과 같이 이번에도 Day 2에서 조금 노는 (?) 모습을 보였고 1등 성적을 받지 못하였으나..

IOI 2019 Day 1 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 김세빈, 100 / 100 / 40, 240점, 8등 - 25등 윤교준, 72 / 100 / 40, 212점, 26등 - 59등 임유진, 72 / 100 / 40, 212점, 26등 - 59등 이온조, 38 / 100 / 64, 202점, 60등 올해도 미국의 Benjamin Qi가 만점인 300점을 3시간 30분만에 얻었다. 문제가 쉽지 않았음에도 불구하고 빠른 시간 안에 300점을 얻은 것이 놀라울 따름이다. 단순히 Day1에서 큰 점수차를 보여줬을 뿐만 아니라 실질적으로 다른 학생들과 실력 격차가 크다는 것을 증명했다고 생각한다. 2019년 2연속 우..