구사과

http://www.hani.co.kr/arti/opinion/column/935716.html [세상읽기] 죽은 스탈린, 살아있는 진영론 / 조형근 사망 4개월 전인 1952년 당 대회에서의 스탈린. 이렇게 미화되지 않은 사진들은 공개되지 않았다. 러시아 국립사회정치사문서보관소. 삼인 제공 www.hani.co.kr 스탈린은 진영 테제의 창시자였다. 세상은 공존할 수 없는 적대 진영으로 나뉘어 있으며, 정치는 진영 간의 전쟁이라고 믿었다. 이상을 떠벌리는 지식인 부류를 경멸했다. 역사에 만약은 없지만 그의 미친 듯한 중공업 육성이 없었다면 소련은 나치한테 패망했을 확률이 높다. 그렇게 소련은 기적처럼 살아남았다. 진영론을 폄하할 수 없는 까닭이다. 그렇게 기적이 된 소련은 사회주의도 민주주의도 아닌 괴..

9. Dynamic Tree DP Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.) In Line 다음과 같은 문제를 생각해 보자. Problem. 길이 $N$ 의 배열이 있을 때, 다음 두 연산을 쿼리당 $O(\log N)$에 계산하여라. 원소 갱신: $A[x] := v$ 최대 부분합 쿼리: 부분배열을 골라, 그 안의 원소 합을 최대화하여라. 즉, $Ma..

Grand Prix of Gomel Ptz Winter 2020 Gennady Korotkevich Contest 5이다. kdh랑 같이 했다. 문제들이 너무 수학적 성향이 강해 내 취향은 아니었다. B: online FFT 테크닉으로 된다는데, 그 online FFT가 그냥 분할 정복 같아서 차라리 G 말고 이걸 할까 하는 후회가 있었다. 뭐 분할 정복을 시도 안 해 본 건 아니지만.. 300iq가 웃긴 풀이를 알려줬는데, $n + k$ 개의 결과를 $2n+k$ 개의 결과로 확장하는 방법이 있다. $2n+k$ 각각의 계수는 (self-convolution) + ($[x/2, x/2+k]$ 근처에서 튀어나온 계수 몇개 제거) 정도로 구할 수 있다. 우항은 $n+k$ 개의 결과가 있으면 $O(nk)$ 에 ..

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/..