LCS(최장 공통 부분 수열 - longest common subsequence) 재귀적 방법 & 중복제거의 메모이제이션

발췌 문헌

<뇌를 자극하는 알고리즘>

ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

LCS 문제는 최적의 부분구조를 가진다. 이 문제는 더 작은, "부분문제"로 쪼개질 수 있고, 이것은 반복해서 자명한 부분문제가 될 때까지 더 간단한 부분문제로 쪼개질 수 있다. LCS는 또한 겹치는 부분문제를 가진다. 더 높은 부분문제에 대한 풀이는 몇몇의 하위 부분문제의 풀이에 의존한다. "최적의 부분구조"와 "겹치는 부분문제"는 동적 프로그래밍이라는 가장 간단한 부분문제에서 출발하는 문제 풀이 기법으로 접근될 수 있다. 이 과정은 부분문제의 해답을 표에 저장하는 방식인 메모이제이션을 통하여 상위 단계의 부분문제에서 해답을 접근할 수 있도록 하는 과정을 필요로 한다. 

이 방법은 다음과 같이 묘사된다.

주어진 두 문자열의 최장 공통 부분수열(longest common subsequence)은 다음과 같이 표현된다.

이 두 문자열을 매개 변수로 받아 이들 사이에서 나올 수 있는 LCS의 길이를 구하는 함수를 LCS라고 하자.

 

 

 

0. i나 j 둘 중 하나가 0인 경우 (두 문자열 중 하나라도 길이가 0인 경우)

i나 j가 0이라는 것은 두 문자열 중 하나의 길이가 0이라는 것을 의미하고,

둘 중 하나의 길이가 0이라면 공통 부분 순서라는 것이 존재하지 않는다.

문자열의 원소들은 1부터 시작하는 것으로 정의되어 있으므로, (i = 1 혹은 j = 1)

첨자가 0이라는 것은 문자열이 없다는 것이다.

 

점화 관계로 이를 표현하면 아래와 같다. 4가지 경우로 나온다.

아래는 4가지 경우는 두 문자열의 길이가 모두 0이 아니다라고 전제를 한다. 

(즉, i와 j 둘 다 0이 되지 않는다.)

 

1. 두 문자열의 맨 마지막 원소가 같은 원소로 끝나는 경우(LCS에 포함이 되는 경우)

 

예를 들어, 아래와 같은 두 문자열 X와 Y가 있다고 가정해보자. 

Set_Of_LCS는 집합으로 문자열 X와 Y의 공통 문자의 집합이다. 현재 집합에는 G가 들어있다.

위의 두 문자열의 맨 마지막 원소가 같다.

그리고 나서 문자열의 길이가 i - 1인 문자열 X와 문자열의 길이가 j - 1인 문자열 Y의 LCS를 구한다.

두 문자열의 맨 마지막 원소가 같은 경우에 LCS(Xi,Yj)를 구하기 위해서는 두 문자열의 마지막 원소를 지움으로써

두 문자열의 길이를 줄이고, 이 줄어든 문자열에 대한 LCS를 찾은 후 삭제한 원소를 붙이면 된다고 하였는데,

구현 시에는 마지막 원소를 지우는 것 보다는 탐색할 문자열의 길이를 한 칸씩 줄이는 방법으로 구현을 하도록 한다.

예를 들어, X문자열이 X = < ABCG > 라 하면 문자열의 길이 i는 4이다. 

문자열의 길이 i만큼만 읽는 방식으로 구현을 한다.

i가 3이면 ABC만 읽는다. 그리고 LCS의 원소를 찾으면 LCS의 길이는 하나씩 증가시키는 형태로 구현을 한다. 

점화식은 아래와 같이 표현된다.

 

2. 두 문자열의 맨 마지막 원소가 모두 LCS에 포함이 되지 않는 경우

두 문자열의 맨 마지막 원소가 모두 LCS에 포함이 되지 않는 경우는 먼저,

두 문자열의 맨 마지막 원소는 서로 달라야 한다.

즉, 두 문자열의 맨 마지막 원소가 LCS의 마지막 원소가 아닌 경우을 의미한다.

LCS(Xi,Yj)는 두 문자열의 맨 마지막 원소로 끝나지 않는다.

 

예를 들어, 아래와 같은 두 문자열 X와 Y가 있다고 가정해보자. 

두 문자열의 LCS의 마지막 원소는 X와 Y의 마지막 원소가 아닌 다른 문자인 경우를 의미한다.

이 경우에는 K가 LCS(Xi, Yj)의 마지막 원소가 된다.

(때로는 LCS의 마지막 원소가 공집합인 경우도 있다.)

Set_Of_LCS는 집합으로 문자열 X와 Y의 공통 문자의 집합이다. 

Set_Of_LCS에는 X와 Y의 맨 마지막 원소로 끝나지 않는다.

 

위의 두 문자열의 맨 마지막 원소가 서로 다르고

두 문자열의 LCS의 마지막 원소가 X와 Y의 마지막 원소가 아닌 경우에는

문자열의 길이가 i - 1인 문자열 X와 문자열의 길이가 j - 1인 문자열 Y의 LCS를 구한다.

점화식은 아래와 같이 표현된다.

 

3. 문자열 Y의 맨 마지막 원소가 LCS에 포함이 되는 경우

이 경우는 두 문자열의 LCS(Xi, Yj)가 문자열 Y의 맨 마지막 원소로 끝나는 경우이다.

두 문자열의 맨 마지막 원소는 서로 달라야 한다.

 

예를 들어, 아래와 같은 두 문자열 X와 Y가 있다고 가정해보자. 

Set_Of_LCS는 집합으로 문자열 X와 Y의 공통 문자의 집합이다. 집합에는 문자열 Y의 마지막 원소인 B가 들어있다.

그 이유는 두 문자열의 LCS가 문자열 Y의 맨 마지막 원소 B로 끝난다고 가정했기 때문이다.

LCS(Xi,Yj)를 구하기 위해서는 문자열의 길이가 i - 1인 문자열 X와 문자열의 길이가 j인 문자열 Y의 LCS를 구한다.

 

점화식은 아래와 같이 표현된다.

 

4. 문자열 X의 맨 마지막 원소가 LCS에 포함이 되는 경우

이 경우는 두 문자열의 LCS가 문자열 X의 맨 마지막 원소로 끝나는 경우이다.

두 문자열의 맨 마지막 원소는 서로 달라야 한다.

위의 3과 반대인 경우이다.

 

예를 들어, 아래와 같은 두 문자열 X와 Y가 있다고 가정해보자. 

Set_Of_LCS는 집합으로 문자열 X와 Y의 공통 문자의 집합이다. 집합에는 문자열 X의 마지막 원소인 A가 들어있다.

그 이유는 두 문자열의 LCS가 문자열 X의 맨 마지막 원소 A로 끝난다고 가정했기 때문이다.

LCS(Xi,Yj)를 구하기 위해서는 문자열의 길이가 i인 문자열 X와 문자열의 길이가 j - 1인 문자열 Y의 LCS를 구한다.

 

점화식은 아래와 같이 표현된다.

 

LCS의 최대값은 위의 Case1~4까지의 가장 큰 값이 된다.

 

구현

위의 점화식을 구현하면 아래와 같다.

 

프로그램 실행결과

소스 파일

main.c

0.00MB

 

 

Memoization을 통한 중복 호출의 제거

위의 점화식은 X와 Y의 LCS가 부분 LCS의 답으로부터 만들어지고 있음을 보여준다.

즉, 이 문제는 최적 부분 구조로 되어 있어서 동적 계획법으로 해를 구하는 것이 가능하다.

크기가 i X j의 테이블이 있다고 했을 때, Table[i,j]는 LCS의 길이이며

Table의 각 요소는 Table[i,j]의 부분 문제들의 답을 담고 있다는 것을 설명한다.

여기서 프로그래밍 시에 주의해야 할 점이 있는데, 위 점화식에서 나오는

i = 0, j = 0은 프로그래밍 언어에서의 배열 인덱스처럼 첫 번째 요소를 가리키는 것이 아니다.

i = 0 또는 j = 0은 말 그대로 '아무 것도 없음'을 나타낸다. (각 문자열의 길이가 0임을 나타냄)

문자열 X의 첫 번째 요소는 i = 1, 문자열 Y의 첫 번째 요소는 j = 1이다.

프로그래밍 시에 LCS의 테이블의 크기는 i X j가 아닌 (i + 1) X (j + 1)이다.

이 테이블이 점화식의 테이블보다 행과 열이 1씩 더 긴 이유는 

'아무 것도 없는' 행(i = 0)과 열(j = 0)을 표현하기 위함이다.

위에 대한 표현이 어려우면 일단 넘어가도록 하자. 밑에서 자세히 설명할 것이다.

 

즉, 예를 들면 문자열 X가 "AGCAT" 이고 문자열 Y가 GAC이면 각 문자열의 길이는 5와 3이다.

이 문자열들을 각 각 일차원 배열에 저장한다고 하면

X는 0번 인덱스에서 4번 인덱스의 공간을 차지하고

Y는 0번 인덱스에서 2번 인덱스의 공간을 차지한다.

 

그런데 이차원 배열 Table에 이 문자열의 정보를 저장할 시에 1행 혹은 1열서부터 저장한다.  

LCS의 길이는 맨 마지막 위치에 저장이 된다.

이 경우에는 Table[5,3]에 LCS가 저장되어 있다.

 

즉, 테이블의 아래와 같다.

세로는 X 문자열, 가로는 Y 문자열이다.

 

여기서, 우리가 이차원 배열을 하나 만들긴 했는데, 배열에 저장할 값은 무엇인지 생각해보자.

즉, 위에서 우리가 i = 0 또는 j = 0은 말 그대로 '아무 것도 없음'을 나타낸다고 하였는데

왜 그런지 보자.

배열에 저장할 값은 LCS[i,j]의 길이이다. 

예를 들어보자.

Table[1,1]의 의미는 문자열의 길이가 1인 문자열 X와 문자열의 길이가 1인 문자열 Y의 LCS의 값이 저장된다.

즉, X = <A> 와 Y = <G> 의 LCS는 0이 된다.

Table[3,2]의 의미는 문자열의 길이가 3인 문자열 X와 문자열의 길이가 2인 문자열 Y의 LCS의 값이 저장된다.

즉, X = <AGC> 와 Y = <GA> 의 LCS는 1이 된다.

Table[0,1]의 의미는 문자열의 길이가 0인 문자열 X와 문자열의 길이가 1인 문자열 Y의 LCS의 값이 저장된다.

즉, X = <> 와 Y = <G> 의 LCS는 0이 된다. 문자열 Y와 비교할 문자열 X는 없다는 의미이다.

이와 마찬가지로,

Table[1,0]의 의미는 문자열의 길이가 1인 문자열 X와 문자열의 길이가 0인 문자열 Y의 LCS의 값이 저장된다.

즉, X = <A> 와 Y = <> 의 LCS는 0이 된다. 문자열 X와 비교할 문자열 Y는 없다는 의미이다.

이와 같기 때문에 Table의 0번째 행에는 모두 0이 저장되어 있고, 0번째 열에는 모두 0이 저장되어 있다.

이와 같이 Table의 내용을 다음과 같이 적을 수 있다.

 

 

위에서 구한 점화식을 이용해서 Table에 값들을 저장해보자.

 

구현

아래는 점화식을 통해 Table에 LCS의 값을 저장하는 함수이다.

Table에 LCS의 길이값이 저장이 되어있으면 그 값을 리턴한다.

만일 Table에 기록이 되어 있지 않으면 해당 LCS의 길이값을 찾고 기록을 한다.

 

프로그램 실행결과

 

위의 프로그램 실행결과의 Table의 내용과 위에서 우리가 계산해서 적은 내용이 같은지 확인해보자.

 

소스 파일

main.c

0.00MB

위의 실행결과에서 Table의 내용을 출력함을 볼 수 있는데, 간지가 나지 않는다.

Table의 내용을 좀 더 간지나게 출력해보자.

Table의 내용을 출력하는 함수를 만들어 보자.

프로그램 실행결과

그리고 우리는 한 가지 더 구하고 싶을 것이다.

LCS의 길이까지 구했다면, 과연 LCS는 무엇인지 궁금할 것이다.

이 LCS를 찾는 방법에 대해 알아보자.

이는 Table의 내용을 추적해서 알아낼 수 있는데 알고리즘은 다음과 같다.

 

Process1. Table의 맨 우측하단의 요소를 시작 셀(Cell)로 지정하고,

             LCS의 요소를 담기 위한 리스트를 준비한다.

Process2. 현재 위치한 셀의 값이 왼쪽, 왼쪽 위, 위 셀의 값보다 크면

             현재 셀의 값을 리스트의 헤드에 삽입하고 왼쪽 위 셀로 이동한다.

Process3. 현재 위치한 셀의 조건이 Process2에 해당하지 않으며, 

             현재 셀의 값과 왼쪽 셀의 값이 같고 위 셀의 값보다 큰 경우에는 왼쪽으로 이동한다.

             이동만 할 뿐, 리스트에 아무 것도 넣지 않는다.

Process4. 위의 Process2와 3 중 어느 경우에도 해당하지 않는 경우에는 위 셀로 이동한다.

            이동만 할 뿐, 리스트에 아무 것도 넣지 않는다. 

Process5. i = 0 또는 j = 0 이 될 때까지(두 문자열의 길이가 하나라도 0이 될때 까지) 위의 Process2~4를 반복한다.

 

Table의 내용을 추적해서 Table에 저장되어 있는 데이터를 이용해서 LCS를 찾는 함수는 아래와 같다.

프로그램 실행결과

현재까지의 내용이 저장된 소스 파일

main.c

0.01MB

 

아래로 가서 DP로 구현해보자.

designatedroom87.tistory.com/119

LCS(최장 공통 부분 수열 - longest common subsequence) DP