[Python] 백준 - 9251 LCS

출처: 백준 온라인 저지
https://www.acmicpc.net/problem/9251

찾아보니 LCS (Longest Common Subsequence) 알고리즘 자체가 다익스트라 알고리즘처럼 따로 이름을 가지고 있는 알고리즘이었다. 대표적인 동적 프로그래밍 알고리즘 중 하나라고 한다.

https://chanhuiseok.github.io/posts/algo-34/

위 출처의 글을 보고 LCS 알고리즘을 이해할 수 있었다. 그런데 사실 코딩 테스트를 볼 때 이러한 알고리즘의 규칙을 직접 찾아서 적용하기는 어려울 것이다. 따라서 LCS 알고리즘처럼 중요한 알고리즘은 미리 알아둘 필요가 있다.

위 설명으로 알고리즘을 이해한 뒤, 코드를 구현해보았다.

최종 풀이

from sys import stdin


string_1 = list(stdin.readline().rstrip())
string_2 = list(stdin.readline().rstrip())

a = len(string_1)
b = len(string_2)

matrix = [[0] * (b + 1) for _ in range(a + 1)]

for i in range(1, a + 1):
    for j in range(1, b + 1):
        if string_1[i - 1] == string_2[j - 1]:
            matrix[i][j] = matrix[i - 1][j - 1] + 1
        else:
            matrix[i][j] = max(matrix[i - 1][j], matrix[i][j - 1])

print(matrix[a][b])