99클럽 코테 스터디 _ 23일차 TIL (동적 계획법)

 

< 문제 >

[백준] 9251. LCS / 골드5

---

< 풀이 >

Dynamic Programming
시간복잡도 : O(N X M)       *N : length s1,   M : length s2

 

def find_lis():
    s1 = "0" +  str(input())
    s2 = "0" +  str(input())

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

    for i in range(1, len(s1)):
        for j in range(1, len(s2)):
            if s1[i] == s2[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1], dp[i-1][j])
    print(dp[len(s1)-1][len(s2)-1])

find_lis()

 

 

 

풀이 방식

1. 입력받은 문자열 처리
   • s1, s2 앞에 "0"을 추가하는 이유는 인덱스를 1부터 시작하기 위해서
   • 1-based index로 처리할 수 있다.
2. dp 테이블 초기화
   • dp[i][j] 는 s1[1: i] 와 s2[1: j] 의 최장 공통 부분 수열(LCS) 길이를 저장
     • s1[1: i]  : 1번 인덱스부터 i까지의 부분 문자열
     • s2[1: j]  : 1번 인덱스부터 j까지의 부분 문자열
3. dp 점화식
   • 두 문자가 같은 경우 (s1[i] == s2[j])
     • 두 문자가 같으면 공통 부분 수열에 추가할 수 있다.
     • dp[i][j] = dp[i-1][j-1] + 1   :  이전까지의 LCS에 +1
   • 두 문자가 다른 경우 (s1[i] != s2[j])
     • 두 문자가 다르면 최댓값을 선택한다.
     • dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

---

 

 

 

문제 예시 실행

 

s1 = "ACAYKP"  ,  s2 = "CAPCAK"

 

 

dp 테이블 초기화

s1 \ s2	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
Y	0	0	0	0	0	0	0
K	0	0	0	0	0	0	0
P	0	0	0	0	0	0	0

 

 

dp 갱신 과정 일부

1.  i=1, j=1 (s1[1] = A, s2[1] = C)
   • 다름 → dp[1][1] = max(dp[0][1], dp[1][0]) = max(0,0) = 0
   •  

     s1 \ s2	0	C	A	P	C	A	K
     A	0	0

2. i=1, j=2 (s1[1] = A, s2[2] = A)
   • 같음 → dp[1][2] = dp[0][1] + 1 = 1

   • s1 \ s2	0	C	A	P	C	A	K
     A	0	0	1

3. i=2, j=1 (s1[2] = C, s2[1] = C)
   • 같음 → dp[2][1] = dp[1][0] + 1 = 1

   • s1 \ s2	0	C	A	P	C	A	K
     A	0	0	1
     C	0	1

4. i=2, j=3 (s1[2] = C, s2[3] = P)
   • 다름 → dp[2][3] = max(dp[1][3], dp[2][2]) = max(1,1) = 1

   • s1 \ s2	0	C	A	P	C	A	K
     A	0	0	1	1
     C	0	1	1	1

 

 

모든 과정 진행 후 dp 테이블 갱신 결과

LCS = "ACAK"

s1 \ s2	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	2	2
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4