«   2022/10   »
            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
0
Total
96,326
관리 메뉴

차근차근

[백준 9251] LCS 본문

대학교/Algorithm

[백준 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' 카테고리의 다른 글

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