«   2022/05   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
Archives
Today
11
Total
83,907
관리 메뉴

차근차근

[백준 9251] LCS 본문

Algorithm (Python)/DP

[백준 9251] LCS

SWKo 2020. 9. 12. 01:59

0. 제목

  • 백준 9251 LCS
  • BOJ 9251 LCS
  • 파이썬 9251 LCS
  • Python 9251 LCS

1. 문제

www.acmicpc.net/problem/9251

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net


2. 풀이

  • 두 문자열의 길이를 조금씩 늘려 가며 확인하여 공통 부분 수열의 최대 길이를 계산한다.
  • 두 문자열을 X, Y라고 할 때 X[i-1] = Y[i-1] 이면 dp[i] = dp[i-1][j-1] + 1, X[i-1] != Y[i-1] 이면 dp[i] = max(dp[i-1][j], dp[i][j-1]) 이다.


3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
= input()
= input()
 
dp = [[0* (len(y) + 1for _ in range(len(x) + 1)]
 
for i in range(1len(x) + 1):
    for j in range(1len(y) + 1):
        if x[i - 1== y[j - 1]:
            dp[i][j] = dp[i - 1][j - 1+ 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
            
print(dp[len(x)][len(y)])

'Algorithm (Python) > DP' 카테고리의 다른 글

[백준 1495] 기타리스트  (0) 2020.09.13
[백준 9251] LCS  (0) 2020.09.12
[백준 11053] 가장 긴 증가하는 부분 수열  (0) 2020.09.12
[백준 12865] 평범한 배낭  (0) 2020.09.11
[백준 1904] 01타일  (0) 2020.09.10
0 Comments
댓글쓰기 폼