시리즈 "알고리즘 문제풀기" 개요

  • 1~2주 (최소) 1개 문제 풀기를 목표로 한다.
  • JavaScript 로 푼다.

문제

Baekjoon Online Judge - 9251. LCS

수열 A 와 B 가 주어졌을 때, "가장 긴 공통 부분 수열"(= Longest Common Subsequence, LCS)의 길이를 구하는 문제다.

예를 들어 수열이 "ACAYKP", "CAPCAK" 일 경우 LCS 는 "ACAK" 다.

접근

이 문제 또한 이전 문제와 마찬가지로 DP 카테고리에 있던 문제이므로, DP 로 푸는 것이라는 건 알고 있었다.

그렇다면 이 문제는 어떻게 작은 단위로 쪼개고 어떻게 그 답을 재활용해서 더 큰 단위의 답을 찾아내느냐가 문제였다.

생각해낸 방법은 수열 A 의 각 문자들의 수열 B 에서의 위치를 알아내고, 그걸로 LIS 를 찾아내는 것이었다.

수열 1 "ACAYKP", 수열 2 "CAPCAK" 를 예로 들면

  • 수열 1 의 첫 문자 "A" 는 수열 2 에서 5번째, 2번째에 위치한다.
  • 두 번째 문자 "C" 는 수열 2 에서 4번째, 1번째에 있다.
  • 세 번째 문자 "A" 는 수열 2 에서 5번째, 2번째에 위치한다.
  • ...

이런 식으로 위치를 알아낸 뒤 그 위치로 문자들을 치환한다.

ACAYKP => A(52)C(41)A(52)Y()K(6)P() => 5241526

그리고 치환된 수열로 LIS 를 찾는 것이다.

시도

시도 결과

잘 동작한다. 채점에서도 잘 동작한다. 92%까지는. 92%에서 "시간초과"가 뜬다. 각 수열의 최대 길이는 1000자. 시간 제한은 고작 0.1초. 내 풀이로는 도저히 시간 내에 무리였나보다.

다시 접근

아무리 머리를 쥐어짜도 풀이를 떠올릴 수 없었다. 그래서 결국 구글링을 해봤다. 다른 사람들의 풀이는, DP 는 DP 이되 2차원으로 생각한 것이었다. 이해가 잘 안 되어서 글을 여러 개 읽어봤는데 이 글이 제일 쉽게 설명한 것 같다.

풀이를 읽어봤으니 다시 풀어보자.

풀이

후기

머리를 싸맨 것에 비하면 풀이는 너무나도 간단하다. DP 로 푸는 문제라는 걸 알면서도 문제를 풀지 못하다니 참으로 난감할 따름이다. 어렵다 어려워.

참고