DP: 백준 9251 오답노트

https://www.acmicpc.net/problem/9251

1. 개요

두 문자열 $s1$과 $s2$에서 공통으로 등장하는 부분 수열 중 길이가 가장 긴 것(LCS)을 찾는 문제로써, 이 문제는 동적 계획법(Dynamic Programming, DP)을 활용해 해결하는 것이 포인트이다.

---

2. DP 테이블 구성

• DP 테이블 정의:
  $dp[i][j]$는 $s1$의 처음 $i$개의 문자와 $s2$의 처음 $j$개의 문자로 만들 수 있는 LCS의 길이를 의미한다.
• 초기값:
  빈 문자열과의 비교이므로 $dp[0][j]=0$, $dp[i][0]=0$로 초기화한다.
  그러기 위해서는 다음과 같은 형식으로 DP 테이블을 초기화 할것
  dp = [[0]*(len_2 + 1) for _ in range(len_1 + 1)]

---

3. 핵심 로직: 문자의 비교 처리

1. 문자가 일치하는 경우
   만약 $s1[i-1]$와 $s2[j-1]$가 같다면, 두 문자열 모두에서 해당 문자를 LCS에 포함시킬 수 있음
   $dp[i][j]=dp[i-1][j-1]+1$
   따라서 이전(i-1, j-1)에 계산된 LCS 길이에 현재 일치하는 문자를 추가하는 방식을 진행하면 되므로 단순 +1을 해주면 된다.

2. 문자가 일치하지 않는 경우
   두 문자가 다르면, 어느 한쪽의 문자를 제외한 경우 중 더 긴 LCS를 선택한다.
   $dp[i][j]=\max(dp[i-1][j],dp[i][j-1])$

   • $dp[i-1][j]$: $s1$의 현재 문자를 제외한 경우
   • $dp[i][j-1]$: $s2$의 현재 문자를 제외한 경우
     이 둘 중 최댓값을 선택하여 LCS 길이를 유지.

알고리즘 흐름

1. 테이블 초기화:
   $(|s1|+1) \times (|s2|+1)$ 크기의 2차원 리스트를 모두 0으로 초기화
2. 반복문을 통한 테이블 채우기:
   $i=1$부터 $|s1|$, $j=1$부터 $|s2|$까지 모든 경우에 대해 위 두 조건(일치/불일치)을 적용하여 $dp[i][j]$를 갱신
3. 결과 반환:
   최종적으로 $dp[|s1|][|s2|]$에 두 문자열의 LCS 길이가 저장된다.

---

4. 정답 코드

def LCS(s1, s2):
    len1, len2 = len(s1), len(s2)
    dp = [[0] * (len2 + 1) for _ in range(len1 + 1)]
    
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[len1][len2]

# 입력 예시
s1 = input().strip()
s2 = input().strip()

# 결과 출력
print(LCS(s1, s2))

---

$O(n \times m)$의 시간 복잡도