[백준/9251] LCS | 최장공통수열

9251 LCS

LCS 문제 해결 기법

1. 두 수열 중 하나를 비교대상으로 잡고 나머지 수열의 문자열을 하나씩 추가하면서 공통 수열 길이 값을 table에 표시해준다.
2. 문자열이 같으면 dp table에 저장을 하고, 다시 구하지 말자.
3. dp table은 memoization 방식으로 이어나간다.

---

알고리즘

이 문제는 부분 수열 중 가장 긴 것을 찾는 것으로 그냥 숫자만 출력해주면 돼서 dp table에 같은 문자를 확인하면 +1 누적해주면 된다,,

table 설명을 위해 i=6, j=4일 때를 예를 들어보자면

일단 table은 이중 for문으로 j가 먼저 돌고있는 상황이다. 그러니까 'ACAYKP'라는 문자열에 대해서 'CAPCAK'를 상대적으로 놓고 하나씩 비교를 하고 있는 것이다.

 

가장 긴 공통 문자열의 길이를 묻는 거니까 P에 대해 CAPCAK를 돌면서 이전에 저장해두었던 것을 memozation/누적으로 적용해주고 나와 같은 알파벳이 있는지 찾는다. (6,4)일때는 P != C이니까 그대로 3으로 진행되는 것이다.

반면 (2,4)에서는 이미 앞에서 A-A 쌍이 발견되어 +1이 추가된 상황에서 C-C 쌍이 발견되어 +1 추가해서 2가된 것.

 

최종 코드

import sys

s1 = input()
s2 = input()

dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]

for i in range(1, len(s1)+1):
    for j in range(1, len(s2)+1):
        # j부터 증가하면서 상대적으로 비교
        if s1[i-1] == s2[j-1]:
            # 같은 문자가 발견되면 memoization을 통해 누적값 갱신
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            # 문자가 다르면 위나 왼쪽 중에서 큰 값으로 누적값 갱신
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            
print(dp[len(s1)][len(s2)])

 

알게된 점

이해 자체가 어려웠다ㅠㅠ 그래도 손으로 써보니까 괜찮았음

이걸 내가 혼자 어떻게 생각할 순 있어도 dp로 구현한다는게 힘든 것같다. 그냥 많이 풀어보고 외울 건 외워야겟다