CS 공부/백준 - Python
[백준 9251번] LCS : LCS(Longest Common Subsequence, 최장 공통 부분 수열) / 다이나믹 프로그래밍 - 파이썬(Python)
nanocat
2023. 2. 22. 13:14
https://www.acmicpc.net/problem/9251
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. LCS는 다이나믹 프로그래밍의 일종이다.
❗다이나믹 프로그래밍이란?
- 다이나믹 프로그래밍(Dynamic Programming, 동적계획법 또는 동적 프로그래밍이라고도 불린다.)은 일종의 문제 해결 패러다임으로, 문제를 해결하기 위해 더 작은 문제를 해결하고 해를 재활용하는 방식이다. 보통 테이블을 재사용하며 분할 정복 기법과 유사하다. Top-down approch와 bottom-up approach가 있다.
❗LCS에 대한 참고
최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 최장 공통 부분수열 문제는 LCS라고도 불린다. 이는 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다.(종종 단 두 개중 하
ko.wikipedia.org
풀이
def LCS(word1, word2):
m = len(word1)
n = len(word2)
C = [[0 for i in range(n + 1)] for j in range(m + 1)] # word1과 word2에 대한 테이블 생성
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]: # 두 원소를 비교하여 같다면 다음 원소로 확장
C[i][j] = C[i-1][j-1] + 1
else: # 두 원소가 같지 않다면 두 수열 중 더 긴 것이 얻어짐
C[i][j] = max(C[i-1][j], C[i][j-1])
return C[m][n]
def main():
word1 = input()
word2 = input()
print(LCS(word1, word2))
if __name__ == '__main__':
main()