LCS

TEST CASE

혹시 문제를 풀다가 예시들은 모두 제대로 출력되는데 제출하면 틀렸다고 나오시는 분들은 아래의 테스트 케이스에 대해 생각해보면 도움이 될 것 같다.

AGGTAB
GXTXAYB

문제

두 수열이 주어졌을 때 그들의 부분 수열 중 가장 긴 수열을 찾는 문제다. 이 문제 역시 DP를 이용해 푸는 유형이다.

처음에 DP유형인 것을 알고 풀기 시작했지만 풀어내는데 꽤 긴 시간이 걸렸다.

값을 저장할 이차원 배열을 만든 후 차례차례 값을 집어 넣으며 가장 긴 길이의 수열을 구한다. 입력 예시를 이용해 이해해보자.

예제 입력

ACAYKP
CAPCAK

위와 같은 입력은 아래와 같은 이차원 배열로 나타낼 수 있다.

0 ‘A’ ‘C’ ‘A’ ‘Y’ ‘K’ ‘P’
‘C’ 0 C C C C C
‘A’ A C AC AC AC AC
‘P’ A C AC AC AC ACP
‘C’ A AC AC AC AC ACP
‘A’ A AC ACA ACA ACA ACP
‘K’ A AC ACA ACA ACAK ACAK


먼저 CAPCAK의 C부터 ACAYKP를 탐색하게 된다.

  • C와 A는 중복되는 단어가 없음으로 0
  • C와 C로 단어가 같음으로 C
  • C와 A는 중복되지 않지만 직전에 C가 겹쳤음으로 C
  • 나머지 단어들도 마찬가지로 C가 입력된다.

다음으로 A를 살펴보자

  • A 와 A로 단어가 같음으로 A
  • A 와 C는 중복되는 단어가 없음으로 직전에 겹친 값인 A를 가져와야한다. 하지만 ‘A’,’C’ 길이가 같음으로 윗줄의 C가 그대로 내려온다.
  • A 와 A로 단어가 같음으로 해당 칸 왼쪽 윗줄의 값에 A를 추가해 AC
  • A 와 Y로 중복되는 단어가 없어 직전에 겹친 값인 A를 해당 칸 왼쪽 윗줄의 값에 A를 더해 입력한다.

이와 같은 과정을 ‘P’, ‘C’, ‘A’ 그리고 ‘K’에 대해서도 거치면 위의 표와 같은 dp리스트를 얻을 수 있다.

  • 위에서 단어가 겹치는 상황을 만날 때 해당 칸 왼쪽 윗줄의 값에 해당 단어를 더했다. 그래서 코드를 작성할 때는 index범위를 벗어나는 것을 방지하기 위해 단어의 왼쪽에 ‘0’을 이어붙여 주었다.
  • 위에선 DP리스트에 단어들을 집어넣어 설명했지만 코드를 짤 때는 단어의 개수를 리스트에 넣어주면 된다.


CODE

import sys
import heapq
a = input()
b = input()
a = '0'+a
b = '0'+b
dp = list([0]*(len(a)) for _ in range(len(b)))

for i in range(1, len(b)):
    tmp = 0
    for j in range(1, len(a)):
        dp[i][j] = dp[i-1][j]  #먼저 윗줄의 값을 그대로 받아온다.
        if b[i] == a[j]: #단어가 겹치면 해당칸 왼쪽 윗줄의 숫자에 +1을 해준다.
            tmp = dp[i-1][j-1]+1
        if tmp <= j+1 and dp[i][j] < tmp:
            dp[i][j] = tmp #저장되어 있는 값이 tmp보다 짧을때 값을 업데이트
print(max(dp[-1])) #마지막 줄의 최대값을 출력한다.

dp를 출력해보면 다음과 같다.

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1]
[0, 1, 1, 2, 2, 2, 2]
[0, 1, 1, 2, 2, 2, 3]
[0, 1, 2, 2, 2, 2, 3]
[0, 1, 2, 3, 3, 3, 3]
[0, 1, 2, 3, 3, 4, 4]


LCS 2

LCS문제와 동일하지만 가장 긴 수열의 길이와 그 수열을 모두 출력하는 문제다. 코드를 짤 때 DP리스트에 숫자 대신 겹치는 단어들을 추가하도록 수정하면 된다.

CODE

import sys
import heapq
a = input()
b = input()
a = '0'+a
b = '0'+b
dp = list(['']*(len(a)) for _ in range(len(b)))

for i in range(1, len(b)):
    tmp = ''
    for j in range(1, len(a)):
        dp[i][j] = dp[i-1][j]
        if b[i] == a[j]:
            tmp = dp[i-1][j-1]+b[i]
        if len(tmp) <= j+1 and len(dp[i][j]) < len(tmp):
            dp[i][j] = tmp

lcs = dp[-1][-1]
print(len(lcs))
if len(lcs) != 0:
    print(lcs)

dp를 출력해보면 다음과 같다.

['', '', '', '', '', '', '']
['', '', 'C', 'C', 'C', 'C', 'C']
['', 'A', 'C', 'CA', 'CA', 'CA', 'CA']
['', 'A', 'C', 'CA', 'CA', 'CA', 'CAP']
['', 'A', 'AC', 'CA', 'CA', 'CA', 'CAP']
['', 'A', 'AC', 'ACA', 'ACA', 'ACA', 'CAP']
['', 'A', 'AC', 'ACA', 'ACA', 'ACAK', 'ACAK']

설명에서 사용한 표의 값들과 일치하는 것을 확인하자!

이렇게 DP 대표 유형 5개중 3개를 다루어 보았다. 얼핏 Edit distance와 Matrix Chain Multiplication을 살펴 보았는데 굉장히 어려워 보인다… 일주일 내로 이해하는 것을 목표로 해야겠다.


DP 대표 유형

[다시 풀어보기] ✔ - 2020.11.11