5.5 최장 공통 부분 수열 길이 구하기 - 메모전략

재귀 호출로 LCS를 풀 경우 시간 복잡도는 지수 시간이므로 이를 줄이기 위해 DP로 풀어본다.

재귀 호출 구조의 경우 하위 문제의 반복이 나타나므로 일단 메모 전략을 적용해 본다.

 

메모 전략에 사용되는 캐시는 초기값은 -1인 2차원 배열이다.
캐시의 인덱스에서 0은 빈 문자열을 의미하므로 전체 크기는 (m+1) x (n+1) 이 된다.
그다음은 아래의 조건에 따라 처리하면 된다.
1. 첫 번째 문자열의 첫 글자(인덱스 i)와 두 번째 문자열의 첫 글자(인덱스 j)의 LCS 길이를 처음 계산할 때 이 값을 캐시 테이블에 저장([i][j])
2. 재귀 호출 과정을 이어가다가 다시 i와 j 값으로 재귀 함수가 호출되면 LCS 길이를 다시 계산하지 않고 캐시에 저장된 값을 반환.

위의 조건들을 코드로 옮기면 다음과 같다.

import sys
sys.setrecursionlimit(10**6)

def solve(a, b):
	m, n = len(a), len(b)

	if m == 0 or n == 0:
		return 0

	if a[-1] == b[-1]:
		return 1 + solve(a[:-1], b[:-1])
	else:
		return max(solve(a, b[:-1]), solve(a[:-1], b))

cache = [[-1 for _ in range(31)] for __ in range(31)]

def solve_memo(a, b):
	m, n = len(a), len(b)

	if m == 0 or n == 0:
		return 0
		
	if cache[m][n] != -1:
	  return cache[m][n]

	if a[-1] == b[-1]:
		cache[m][n] = 1 + solve(a[:-1], b[:-1])
	else:
		cache[m][n] = max(solve(a, b[:-1]), solve(a[:-1], b))
		
		
	return cache[m][n]

if __name__ == '__main__':
	a, b = input().split()

	print(solve_memo(a, b))

메모 전략을 사용한 소스는 재귀와 크게 차이가 나지는 않는다.

그러나 cache object를 사용해서 재계산만 없애는 것이기에 재귀 자체는 여전히 존재한다.

 

다음 포스팅에서는 재귀가 없는 형태로 DP를 구현할 예정이다.