[알고리즘] LCS(Longest Common Subsequence)

LCS란?

:"가장 긴 공통 부분 수열"이다. 알고리즘 LCS에서는 가장 긴 공통 부분 문자열이다. 두 개의 문자열이 있을 때, 그 문자열에서 순서를 유지하면서 공통으로 나타나는 글자들을 이어서 만들 수 있는 가장 긴 문자열을 찾는 것을 의미한다.

 

*부분 문자열이란?

:부분 문자열에는 연속된 부분 문자열인 Substring과 연속되지 않은 부분 문자열인 Subsequence라는 개념이 있다. 

 

Subsequence라는 개념을 예시를 들어 설명하자면, "ABCDEF"와 "AEBDF"라는 두 문자열이 있다면, 이 두 문자열에서 공통으로 나타나며 글자들이 두 문자열에서 같은 순서로 나타나는 문자열 중 가장 긴 부분 수열은  "ABDF"이다. 

 

 

예시

accykp와 ccap사이의 lcs를 구할 경우 만들어서 활용해야하는 배열

 

 

* 위 배열 활용법 *

배열의 초기 상태

 

조회하는 문자열이 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야한다. 

조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값을 교체한다. 

 

맨 첫번째 행의 모든 열을 0으로 하고 다음 모든 행의 첫번째 열에 0은 왜 넣는걸까?

=> 조회하는 문자열이 같을때, 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야하는데, 

앞에 0을 넣지 않으면 첫번째 문자열의 맨첫번째 값과 두번째 문자열의 맨 첫번째 값에 어떤 값을 넣어줘야 할지 모르기 때문이다. 

 

왜 바로 앞의값(왼쪽)의 값에서 +1을 하지 않을까? 

=> 바로 앞의값에서 +1을 하면 lcs의 값에 +1을 하는 꼴이 된다.

(하지만 두번째 단어의 조회할 자리는 여전히 같은 자리임=> 두번째 단어의 조회할 자리를 +1 하면 할수록 lcs의 값이 중복으로 +1되는 꼴)

 

왜 조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값으로 교체할까? 

왜 하필 현재 자리에서 왼쪽, 위의 값을 비교할까? 

 => 현재 자리의 왼쪽은 현재 자리의(같은행, 다른열==현재열-1) lcs값은 고려하지 않고 이전 문자까지의 lcs값만을 가지고 있는 것이고,

현재 자리의 위쪽은 현재 자리의 lcs값을 고려하지만, 새로 조회하는 문자와의 비교는 하지 않은 값이다. (다른행==현재행-1, 같은열)

 

왼쪽, 위의 값은 각각 자신이 할 수 있는 최적의 lcs를 구한 상태이다.

따라서 둘 중에 큰 값을 골라 현재의 자리의 값을 교체해줌으로써 최적의 값을 유지할 수 있게된다.