구사과

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