티스토리 뷰

백준 9252 : LCS 2

등급 : Gold IV

9252번: LCS 2 (acmicpc.net)

 

9252번: LCS 2

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

www.acmicpc.net

사용 알고리즘 : Dynamic Programming

사용 자료구조 : -

 

다이나믹 프로그래밍으로 풀 수 있는 고전적인 문제이다.

배열의 가장 첫 부분을 비우고, 두 글자가 같은 부분이 나오면, 이전까지 같은 부분이 있었는지 확인해 + 1을 해준다.

→ str1[i] == str2[j]이면, dp[i][j] = dp[i-1][j-1] + 1.

     (ACA와 CA의 경우 A를 제외하고 ACC 중 이전까지 일치한 길이 1. ∴ 현재 위치 일치 갯수 = 2 )

 

두 글자가 같지 않다면, 이전 글자를 확인하여 더 큰 값을 가져오도록 한다.

→ str[i] != str[j]이면, dp[i][j] = max(dp[i][j-1], dp[i-1][j])

이와 같은 방식으로 진행하면, 위와 같은 DP 배열이 완성된다.

즉, 최대 길이는 DP배열의 끝 값인 4가 된다.

또한 최대 길이에 해당하는 문자는 가장 끝부터 검색하여 서로 문자가 다르면 인덱스가 더 작은 같은 값인 곳으로, 

서로 문자가 같다면 대각선으로 이동하게 구현해주고, 역순으로 출력하면 된다.

( 위의 경우 K, A, C, A순으로 결과값 저장. 이후 역순인 ACAK로 출력 )

cpp
코드 펼치기
java
코드 펼치기
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/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
글 보관함