알고리즘 문제 - LCS
2023. 6. 15.
시리즈 "알고리즘 문제풀기" 개요
- 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초. 내 풀이로는 도저히 시간 내에 무리였나보다.