(BOJ)-9251, Python

문제 요약

출처: (BOJ)9251 - LCS

두 수열이 주어졌을 때, 공통된 부분 수열중에서 가장 긴 부분 수열을 찾는 문제이다.

알파벳 대문자로만 이루어져 있다.

접근 과정

1. 완전탐색 접근(재귀)

비교할 두 문자가 같은 경우와 다른 경우를 기준으로 재귀적으로 구현했다. 하지만 예상대로 시간 초과가 발생했다.

시도한 코드

STR1 = list(input())
STR2 = list(input())
N1 = len(STR1)
N2 = len(STR2)

def recursion(idx1, idx2, count):
    global max_count 
    if idx1 == N1 or idx2 == N2:
        max_count = max(max_count, count)
        return 
    
    #두 문자가 같을 경우 둘 다 넘기기
    if STR1[idx1] == STR2[idx2]:
        recursion(idx1 + 1, idx2 + 1, count + 1)
    #아닐 경우 둘 중 하나 넘기기
    else:
        recursion(idx1 + 1, idx2, count)
        recursion(idx1, idx2 + 1, count)
    
max_count = 0
recursion(0, 0, 0)
print(max_count)

2. DP 접근(메모이제이션)

이전 접근을 바탕으로 메모이제이션 추가해 최적화를 진행해주었다! 결과는 맞았습니다! 시간은 1.34초 걸렸다.

코드 구현

import sys
sys.setrecursionlimit(40000)

STR1 = list(input())
STR2 = list(input())
N1 = len(STR1)
N2 = len(STR2)
dp = [[-1 for _ in range(N2)] for _ in range(N1)]

def recursion(idx1, idx2):
     
    if idx1 == N1 or idx2 == N2:
        return 0
    
    if dp[idx1][idx2] != -1:
        return dp[idx1][idx2]
    
    if STR1[idx1] == STR2[idx2]:
        dp[idx1][idx2] = recursion(idx1 + 1, idx2 + 1) + 1
    else:
        dp[idx1][idx2] = max(recursion(idx1 +1, idx2), recursion(idx1, idx2 + 1))    
    
    return dp[idx1][idx2]

print(recursion(0, 0))

3. DP 접근(점화식)

이번에는 점화식을 기반으로 접근해보도록 하겠다. 이미 이전 접근에서 점화식을 도출했으므로, 이를 재귀 호출 대신 반복문을 이용해 구현하면 된다.

이전 접근에서 다음과 같이 나타냈다.

1. 문자가 같은 경우

   dp[idx1][idx2] = recursion(idx1 + 1, idx2 + 1) + 1

2. 다른 경우

   dp[idx1][idx2] = max(recursion(idx1 + 1, idx2), recursion(idx1, idx2 + 1))

이제 이를 바텀업 방식으로 변환하려면, 작은 값부터 채워나간다는 생각만 가지면 된다. 위 식을 변형하면 다음과 같이 나오게 된다.

1. 문자가 같은 경우

   dp[idx1+1][idx2+1] = dp[idx1][idx2] + 1

2. 다른 경우

   dp[idx1+1][idx2+1] = max(dp[idx1][idx2+1], dp[idx1+1][idx2])

이렇게 나온 점화식을 바탕으로 구현했으며, 결과는 맞았습니다! 시간은 0.472초가 걸렸다.

코드 구현

STR1 = list(input())
STR2 = list(input())
N1 = len(STR1)
N2 = len(STR2)
dp = [[0 for _ in range(N2+1)] for _ in range(N1+1)]

for idx1 in range(N1):
    for idx2 in range(N2):
        if STR1[idx1] == STR2[idx2]:
            dp[idx1+1][idx2+1] = dp[idx1][idx2] + 1
        else:
            dp[idx1+1][idx2+1] = max(dp[idx1+1][idx2], dp[idx1][idx2+1])
            
print(max(map(max,dp)))

회고

바텀업 DP가 시간이 훨씬 빠르다. 탑다운 DP는 많은 함수 호출로 인해 스택 프레임을 계속 생성하고 관리하다보니 시간이 더 걸린다고 알게 되었다. 그래도 탑다운 DP 접근이 경우만 잘 쪼개서 접근한다면 가장 쉽게 접근할 수 있는 방법이지 않을까 생각이 든다..