알고리즘 - LCS (Longest Common Subsequence)

⚠️ 내맘대로 작성한 글이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

 

1. LCS란?

Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. Substring 말고 Subsequence맞다.

Substring은 연속된 것만 가능하고 Subsequence는 연속되지 않은 것도 가능하다. 

Ex)

1번 : ABCDE

2번 : BCNKE

제일 긴 Substring : BC (BCNKE)

제일 긴 Subsequence : BCE (BCNDE)

 

 

2. 그럼 어떤 상황에서 LCS를 사용하나?

염기서열 유사성 분석, 음파 단어 검색 및 교정 등에 사용된다. 

 

 

3. 어떻게 사용하나?

	0	A	B	C	D	E
0	0	0	0	0	0	0
B	0
C	0
N	0
D	0
E	0

위와 같은 포멧을 기본으로 설정한다. 

 

세로의 첫번째 값과 가로의 값들을 비교한다. 

if(같을경우){

    대각선 위의 값 +1

}else{

    좌측갑과 위의 값 비교 후 더 큰 값

}

 

이런 방식으로 표를 채워넣는다

	0	A	B	C	D	E
0	0	0	0	0	0	0
B	0	0	1	1	1	1
C	0	0	1	2	2	2
N	0	0	1	2	2	2
D	0	0	1	2	3	3
E	0	0	1	2	3	4

이런 방식으로 구한다.

 

4. 핵심 기술 : Memoization(메모이제이션)

LCS는 대표적인 다이나믹 프로그래밍을 활용한 방법이다.

그렇기 때문에 Dynamic Programming의 핵심이자 전부인 메모이제이션이 중요하다. 

값들을 저장하면서 한번 계산한 값을 더이상 계산하지 않아도 되게 하는 방법이다. 

 

5. Example

https://naemamdaelo.tistory.com/34

[Java] 백준 9251번 : LCS

 

 

-꿑-