-
[BOJ] 왕들의 외나무다리 돌게임
BOJ18937 왕들의 외나무다리 돌게임 어제 종료된 Semi-Game Cup의 제일 첫 문제입니다. 열심히 노느라 참가를 하지는 못했지만, 문제가 공개된 후에 풀어보니 A번인 이 문제만큼은 난이도가 평이하고 재밌더군요. 문제에서 제시된 게임은 각 플레이어가 다음과 같은 행동을 취할 수 있는 님게임과 일치합니다. 돌을 임의의 개수만큼 가져온다. 해당 무더기에서 가져온 돌 중 일부를 다시 쌓는다. 이 때, 먼저 모든 무더기의 돌의 개수를 xor한 값이 0이 되게 한 플레이어는 상대방이 돌을 쌓던 돌을 가져가던 다시금 돌의 개수를 xor한 값이 0이...
-
LCS 정복하기 4
BOJ18438 LCS 5 이전에 풀이를 작성한 LCS 1/2/3에 비해 갑자기 난이도가 수직 상승한 문제입니다. (LCS 4는 특수한 케이스니 제외합니다. LCS 4의 풀이는 나중에 다른 글에서 소개하도록 하겠습니다.) 최대 길이 7000의 문자열 두 개의 LCS를 TL 1s, ML 7MB에 구해야합니다. TL은 그럭저럭 평범한 것 같은데, ML이 심상치 않다. 이 ML이 난이도를 D2까지 올려놓은 원인인 셈이죠. LCS 2 문제에서 한 대로 공간복잡도 $O(NM)$에 역추적하려고 하면 최대한 크기가 작은 short형을 사용하더라도 MLE는 피할 수 없습니다. 만약 길이만을 구하는...
-
LCS 정복하기 3
BOJ1958 LCS 3 단순히 생각해서 LCS(A,B,C) = LCS(LCS(A,B),C)라고 생각할 수 있으나 두 문자열의 LCS가 하나가 아닐 수 있다는 점에서 무수히 많은 반례를 만들 수 있습니다. 2166번과 같은 근본적인 접근으로 다음과 같은 점화식을 세울 수 있습니다. DP [i] [j] [k] = DP [i-1] [j-1] [k-1] + 1 when A [i] == B [j] and B[j] == C[k] DP [i] [j] [k] = max(DP [i-1] [j] [k], DP [i] [j-1] [k], DP [i] [j] [k-1]) otherwise 점화식만...
-
LCS 정복하기 2
BOJ9252 LCS 2 NM lcs backtracking 문제입니다. 2166번에서 구한 대로 dp table을 작성한 후 점화식의 특징을 이용하여 backtrack할 수 있습니다. 길이 a,b인 문자열 A,B에 대해 (a,b)에서 시작해 (0,t) 또는 (t,0) 꼴의 좌표에 도달할 때까지 다음의 세 행동 중 하나를 취하며 추적하여 LCS로 가능한 문자열을 추출할 수 있습니다. (x,y)=>(x-1,y) when dp [x] [y] == dp [x-1] [y] (x,y)=>(x,y-1) when dp [x] [y] == dp [x] [y-1] (x,y)=>(x-1,y-1) when a [x] == b [y] dp 점화식에 의해...
-
LCS 정복하기 1
BOJ9251 LCS LCS 정복하기, 그 첫 번째. 가장 기초적인 $O(NM)$ dp로 LCS 길이 구하기입니다. LCS란 Longest Common Subsequence의 약자로, 두 수열의 공통된 부분수열을 의미합니다. 이때 부분수열은 연속하지 않아도 됩니다. 예를 들어 IHATEPIZZA와 ILOVEPIZZA의 LCS는 길이 7인 IEPIZZA라고 할 수 있겠죠. 같은 두 문자열이라고 해도, LCS는 여러 개일 수도 있습니다. IEATCHICKEN과 IAETCHICKEN이 그 예시인데요, 길이 7의 IECHICKEN과 IACHICKEN 모두 LCS임을 알 수 있습니다. 그렇다면 LCS의 길이는 어떻게 구할까요? DP로 생각해봅시다. DP [i] [j] = (A[1..i]와 B[1..j]의...