반응형
9251번: LCS
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
알고리즘 분류
- 다이나믹 프로그래밍
SOLUTION
import sys
str1 = list(sys.stdin.readline().rstrip())
str2 = list(sys.stdin.readline().rstrip())
lcs = [[0 for _ in range(len(str2)+1)] for _ in range(len(str1)+1)]
for i in range(1, len(str1)+1):
for j in range(1, len(str2)+1):
# 같은 알파뱃이라면 LCS + 1
if str1[i-1] == str2[j-1]:
lcs[i][j] = lcs[i-1][j-1] + 1
# 다른 알파뱃이라면 이전까지 비교한 값 중 최댓값으로 갱신
else:
lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])
print(lcs[-1][-1])'코딩테스트 대비 > BOJ' 카테고리의 다른 글
| [Baekjoon/Python] 9935번: 문자열 폭발 - 효과는 굉장했다! (0) | 2022.06.12 |
|---|---|
| [Baekjoon/Python] 9663번: N-Queen - 효과는 굉장했다! (0) | 2022.05.26 |
| [Baekjoon/Python] 16953번: A → B - 효과는 굉장했다! (0) | 2022.04.03 |
| [Baekjoon/Python] 11660번: 구간 합 구하기 5 - 효과는 굉장했다! (0) | 2022.04.03 |
| [Baekjoon/Python] 9465번: 스티커 - 효과는 굉장했다! (0) | 2022.04.03 |