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

코딩테스트 준비 중 여러 종류의 알고리즘을 만나다보니 머리로만 기억하는 것은 한계가 있다고 느끼고 지금부터라도 하나씩 차근차근 정리하려한다.

Longest Common Subsequence(최장 공통 부분수열)	- 부분수열이라는 단어를 되뇌이면 이해하기 쉽다. - 예를 들어 두 문자열 ABCFH와 ACDBC에서 ABC가 LCS가 된다. - A와 BC는 연속되어있는 문자열은 아니지만 두 문자열에서 모두 공 통으로 존재하는 문자다.
Longest Common Substring(최장 공통 문자열)	- String.substring을 생각하면 쉽다. - 연속으로 이어진 공통 문자열이다. - 예를 들어 두 문자열 ABCFH와 ACDBC에서 BC가 LCS가 된다.

두 문자열 ABCFH와 ACDBC의 최장 공통 부분수열을 구하는 2차원 배열을 그림으로 표현해보자.

LCS라는 2차원 배열에 두 문자열을 비교한 값을 저장한다. 아래에 점화식에서 보겠지만 각 문자열의 길이+1로 배열을 생성해줘야 점화식이 성립할 수 있다. 그래서 0번째 행,열은 기본값 0이 들어간다.
방법은 간단하다. 가장 윗줄에 있는 ABCFH의 문자열을 왼쪽의 ACDBC문자열을 순서대로 비교하면서 공통 문자가 나올 때마다 값을 대입하면 된다.

첫번째 그림에서 볼 수 있듯이 A와 A는 공통이기에 1을 대입, 그다음 AB와 A를 비교하는 개념인데 실제 코드 부분에서는 그렇게 비교를 할수 없기에 이전에 있는 (1,1)의 값을 가져온다. 나머지 열들도 마찬가지로 진행한다.

두번째 그림에서 (2,1)을 보면 1이 대입되어있다. 이부분도 단지 C(2)와 A(1)의 비교가 아닌 A(1)C(2)와 A(1)의 비교이기 때문이다. 그래서 (1,1)에 있는 1을 대입해준다.
그리고 두번째 그림의 주황생으로 칠해진 부분이 중요하다. AC와 AB를 비교한 다음 C(3)이 나왔고 공통된 문자가 나왔기에 (1,2)에 +1을 해준다. 그 이유는 A(1)과 A(1)B(2)에 C가 공통 문자열에 추가됐기 때문이다.
즉, 문자가 같은 경우 LCS[i][j] = LCS[i-1][j-1] + 1이 된다.

세번째 그림에서도 똑같이 진행을 한다. 다만 위에서 보았듯 왼쪽열과 윗쪽행의 값을 대입해야하는데, 주황색으로 칠한부분을 보면 두개의 값이 다르다. 이 때는 더 큰 값을 대입해준다.
왜냐하면 이전 값인 LCS[i-1][j], LCS[i][j-1] (최대 공통 부분수열)을 알아야만 현재 LCS[i][j]의 값을 알 수 있기 때문이다. 즉, (3,3)의 값을 구하기 위해선 이전까지의 이어온 최장 공통 부분수열의 값이 필요하다는 것이다. 그래서 이전 값 2개중 큰 값을 선택해야 한다.

위 그림을 토대로 점화식을 세우면

- 문자가 같은 경우
lcs[i][j] = lcs[i-1][j-1] + 1;

- 문자가 다른 경우
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);

와 같이 세울수 있다.

두 문자열 ABCFH와 ACDBC의 최장 공통 문자열을 구하는 2차원 배열을 그림으로 표현해보자.

최장 공통 부분수열을 구하는 방법과 크게 다르지 않다.
차이가 있는 부분은 최장 공통 부분수열(이하 subsequence)에선 연속된 문자열이 아니어도 공통된 문자를 찾는 것이고, 최장 공통 문자열(이하 substring)은 연속된 공통 문자열을 찾는 것이다.

그렇기에 subsequence에선 이전의 값들을 이용해 dp방식으로 배열을 채워 나갔다.
substring에선 문자열 하나씩을 비교하고 다를 경우 0을 대입하고, 같을 경우 subsequence와 마찬가지로 왼쪽 위 대각선의 값 + 1. 즉, LCS[i][j] = LCS[i-1][j-1] + 1이 된다. 이유는 subsequence와 같다.

위와 같은 방식으로 대입하다 보면 대각선으로 연속되는 숫자의 무리를 볼 수 있다. 그 중 최대 값을 가지는 연속된 대각선의 값이 LCS가 된다.

위 그림을 토대로 점화식을 세우면

- 문자가 같은 경우
lcs[i][j] = lcs[i-1][j-1] + 1;

- 문자가 다른 경우
lcs[i][j] = 0;

와 같이 세울수 있다.

Longest Common Subsequence와 Longest Common Substring의 차이는 연속되야만 하느냐 아니냐의 차이다. 값을 찾는 방식의 원리는 같다.

티스토리툴바