LCS (최장 공통 부분 수열)

 

📍 정의 및 특징

두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제

- DP의 일종

- 문제 유형 : 최장 공통 부분 수열 길이 구하기, 최장 공통 부분 수열 구하기

 

#DP

 

 

📍 필요 변수

✔ 2차원 LCS 배열     - LCS 길이 찾기용

✔ 2차원 result 배열 - LCS 배열 결과값 저장용

 

 

📍 실행 과정

Case 1) 최장 공통 부분 수열 "길이" 찾기

/* LCS 길이 구하기 */

if(i == 0 || j == 0)
    LCS[i][j] = 0;
else if (ch1[i] == ch2[j])
    LCS[i][j] = LCS[i - 1][j - 1] + 1;
else
    LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1])

1. 문자열 A와 B를 한 글자씩 비교함
2. 두 문자가 다르면, LCS[ i ][ j ] 에 0 저장
3. 두 문자가 같다면, LCS[ i ][ j ] 에 LCS[ i - 1 ][ j - 1 ] + 1 값을 저장
4. 과정 1~3 반복

 

 

Case 2) 최장 공통 부분 "수열" 찾기

1. LCS 배열의 맨 마지막 값에서 시작 (역추적)
2. LCS[ i - 1 ][ j ] 와 LCS[ i ][ j - 1 ] 中 현재와 같은 값 찾기
   1) 같은 값 찾으면, 해당 값으로 이동 (왼쪽/위쪽)
   2) 같은 값 없다면, result 배열에 해당 문자 넣고 LCS[i - 1][j - 1]로 이동
3. 과정2 반복하다 0 도착 시 종료
   ∴  result 배열의 역순 = LCS

 

 

➕ 예제

[백준/JAVA] 9251번: LCS

[백준/JAVA] 9252번: LCS 2

 

---

(참고)

[백준] 9251번 : LCS - JAVA [자바]

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

알고리즘 - LCS(Longest Common Subsequence, 최장 공통 부분 문자열) 알고리즘