5.5 최장 공통 부분 수열 길이 구하기 - DP

LCS의 마지막(이라고 했지만 하나 더 남음) 과정인 DP

캐시 리스트를 하나 만들어서 업데이트하는 방식으로 구현하면 된다.

이전에 했던 소스들과 유사한 부분이 있음.

 

문자열 a, b의 길이 m, n에 대해서 cache [m+1][n+1]을 만든다.
m+1, n+1인 이유는 두 문자열 모두 빈 문자열인 경우를 추가해야 하기 때문.

 

각 문자열들을 첫 번째 인덱스부터 순회하면서 비교했을 때 동일하면

(i-1, j-1)의 값에서 +1을 하면 되고

다르다면

(i-1, j)과 (i, j-1) 중 큰 값으로 업데이트를 해주면 된다.

표를 보면 오히려 이해가 쉬운데, 순회하는 방향이 결국엔 문자열이 증가하는 방향이므로 공통된 문자를 count 하는 거라고 볼 수 있다.

 

위의 내용을 소스로 옮기면 다음과 같다.

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

    cache = [[0 for __ in range(m + 1)] for _ in range(n + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                cache[i][j] = cache[i - 1][j - 1] + 1
            else:
                cache[i][j] = max(cache[i - 1][j], cache[i][j - 1])

    return cache[m][n]


if __name__ == '__main__':
    a = input()
    b = input()
    print(solve(a, b))

예전에 BOJ에 제출했던 소스와 거의 같다. 예전에 제출했을 땐 solve라는 함수를 안 썼었음.

아마 예전에도 구글링 해서 제출했던 거 같은데.. 그리고 유튜브 강의도 봤었던 듯 ㅋㅋㅋㅋ

근데 기억이 안 나는 걸 보면.... 이렇게 포스팅해놔도 나중에 또 까먹지 않을까 싶다 ㅠㅠ

까먹기 전에 반복해서 습관처럼 만드는 게 좋겠지!!