[백준 9251 파이썬] LCS (골드5, DP)

알고리즘 유형 : DP(Dynamic Programming)
풀이 참고 없이 스스로 풀었나요? : X

https://www.acmicpc.net/problem/9251

import sys
input = sys.stdin.readline

A = "0" + input().rstrip()
B = "0" + input().rstrip()

# A가 행, B가 열
LCS = [[0]*len(B) for _ in range(len(A))]

for row in range(1, len(A)):
    for col in range(1, len(B)):
        if A[row] == B[col]:
            LCS[row][col] = LCS[row-1][col-1] + 1
        else:
            LCS[row][col] = max(LCS[row-1][col], LCS[row][col-1])

print(LCS[-1][-1])

리뷰

나는 DP 문제를 접할 때, 길이가 N인 주어진 문자열이나 수열에 대해 무조건 상향식 또는 하향식으로 N과 N-1 사이의 부분 문제를 찾으려는 경향이 있는 것 같다.

이번 문제는 두 문자열에 대해, 한 문자열을 하나 씩 늘려가면서, 그 각각의 단계에 대해 또 다른 문자열을 첨부터 하나하나씩 늘려가며 LCS 값들을 구하는 것(2차원 배열 채우는 형태)까지가 문제에서 구하고자 하는 최종 답이고(물론 실제 답은 LCS[N][N]), 여기서 LCS[N][N]을 구할 때 DP가 활용되는 것이었다.

처음에 문제를 접근할 때,

1) 하향식으로, 한 문자열에 대해 끝의 문자로 끝이 나는 LCS를 싹 다 구하고 max 값 취하기(1차원 배열)

2) 상향식으로, 첫 번째 문자열과 또 다른 문자열 전체와의 LCS, 두 번째 문자열과 또 다른..... 이런 식으로

LCS 싹다 구하고(1차원 배열) max 값 취하기

이 정도 방법을 생각했었다. 물론 깔끔하게 망했지만...

오름차순으로 가능한 모든 경우의 수를 따지는 2차원 배열 형태로 LCS를 구하는 것을 목적으로 잡고, 그 것에서 점화식을 찾으면 되는 문제인데 그 아이디어를 떠올리질 못했다. 부분 문제 정의에서 아직 경험이 많이 부족한가보다...

아이디어가 핵심이었고, 구현 자체는 아주 간단했다.

풀이 요약

1. NxM 크기의 LCS 배열을 채우고 LCS[N][M]을 출력할 것이다.(N은 len(문자열A), M은 len(문자열B))

2. 우선 0행(A[0])과 0열(B[0])을 초기 값으로 채워줘야된다. (점화식이 row-1, col-1까지 나오기 때문)

3. 1행 1열부터 for loop 돌면서, LCS 값 전부 채우기

4. 만약 row행 col열의 A[row]와 B[col]이 같다면, 그 값이 없을 때의 LCS 값인 LCS[row-1][col-1]에서 문자열 하나를 더해주기만 하면 그게 구하는 LCS 값이므로, 이 경우 점화식은 LCS[row][col] = LCS[row-1][col-1] + 1 이다.

5. 만약 A[row]와 B[col]이 다르다면, 각각의 맨 끝 문자가 없을 때의 LCS 값, 즉 LCS[row-1][col]과 LCS[row][col-1]중 최대값이 구하는 LCS값이다. 두 경우를 고려하는 이유는, 내가 생각하기에는, 추가된 문자 직전의 LCS값, 그러니까 후보군으로는 LCS[row-1][col-1], LCS[row-1][col], LCS[row][col-1] 이 3개 정도가 있는데, LCS[row-1][col-1]은 나머지 두 경우보다 끝에 문자를 하나 더 추가하기 때문에 반드시 작거나 같으므로 고려할 필요가 없기에, 이를 제외한 두 경우 중 최대를 구하는 것인 것 같다.

이 때의 점화식은 LCS[row][col] = max(LCS[row-1][col], LCS[row][col-1])

배운 점, 부족했던 점

• 점화식과 메모이제이션을 활용하는 다양한 양상을 경험해야겠다.