[알고리즘] LCS 알고리즘

1. LCS 알고리즘이란?

   - LCS = 최장 공통부분 문자열

   - Substring : 연속된 부분 문자열

        ex. x = 'CCAYCKP'

             y = 'CCAPCAK'

   - Subsequence : 연속되지 않은 부분 문자열

        ex. x = 'ACAYKP'

             y = 'CAPCAK'

---

2. LCS 알고리즘 구현 (LCS 길이찾기)

문제 : [백준] 9251. LCS https://www.acmicpc.net/problem/9251

 

[풀이과정]

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	3	3	4
P	0	1	2	3	3	3	4

• x와 y에 가장 최근에 추가된 글자가 서로 같으면 board[i][j] = board[i-1][j-1] + 1
• x와 y에 가장 최근에 추가된 글자가 서로 다르면 board[i][j] = max(board[i-1][j], board[i][j-1])

[코드]

---

3. LCS 알고리즘 구현 (LCS 글자찾기)

문제 : [백준] 9252. LCS2 https://www.acmicpc.net/problem/9252

정답 : ACAK

[코드]