TigerCow.Door


안녕하세요.

이번 포스팅에서는 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보도록 하겠습니다.

궁금하신 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)


1. 최장 공통 부분 수열

(LCS: Longest Common Subsequence)


먼저 최장 공통 부분 수열이 어떠한 것인지 알아보도록 하겠습니다.

문제를 이해하기 위해 다음을 가정합니다.


X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>


이러한 두 수열 X, Y가 있습니다. 이때, <ABD>는 X와 Y의 공통 부분 수열입니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>

위에서 X 수열과 Y 수열에 밑줄을 쳐놓은 부분을 통해 <ABD>는 X와 Y의 공통 부분 수열이라는 것을 알 수 있습니다.
꼭 연결되어 있어야 하는 것이 아니며, 단지 단조 증가하는 수열로써 존재하면 되는 것이죠.
그렇다면 최장 공통 부분 수열이란 무엇일까요?
바로 위에서 알아본 <ABD>와 같은 공통 부분 수열들 중에서, 가장 길이가 긴 것을 말합니다.
X, Y수열을 살펴보면 <ABD>를 제외하고도 <ABCD>와 같은 공통 부분 수열도 있습니다.
물론 하나의 공통부분 수열만 존재할 수도 있지만 2개 이상의 공통 부분 수열을 가질 수도 있습니다.
그러한 공통 부분 수열들 중에서 가장 길이가 긴 것을 우리는 최장 공통 부분 수열(LCS)라고 말합니다.
위의 X, Y수열에서는 아래 밑줄 친 것과 같이 <ADABCDCC> 가 가장 긴 공통 부분 수열, 최장 공통 부분 수열 입니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>



2. 최장 공통 부분 수열의 최적 구조


우리는 앞에서 동적 프로그래밍의 최적 구조를 살펴보았습니다.

그럼 지금 알아보고 있는 LCS의 최적 구조는 어떻게 될까요? 바로 다음과 같습니다.




3. 최장 공통 부분 수열의 길이 구하기


그럼 이제 본격적으로, 최장 공통 부분 수열의 문제를 풀어보도록 합니다.

우리가 최종적으로 구해낼 것은 두 수열 X, Y가 있을 때 두 수열의 최장 공통 부분 수열의 길이입니다.


먼저 X의 i번째 문자열과 Y의 j번째 문자열까지의 최장 공통 부분 수열의 길이를 c[i,j]라고 가정합니다.



위의 내용을 하나씩 확인해보도록 하겠습니다.


3-1. i=0 or j=0

두 수열 중 하나의 수열의 길이가 0 이라면, 최장 공통 부분 수열의 길이도 0입니다. 서로 일치하는 문자가 전혀 존재할 수 없기 때문이죠.


3-2. i,j>0 and Xi = Yi

i,j가 양수인 것은 당연합니다. 문자열을 거꾸로 확인하지는 않을테니까요.

양수인 i,j에 대해서 Xi와 Yj가 서로 일치한다면 해당 문자는 최장 공통 부분 수열에 포함되는 문자일 것 입니다.

따라서 해당 문자를 제외한 나머지 문자열에서 LCS를 탐색하게 되고, 최종적으로 반환이 될때는 제외한 문자가 최장 공통 부분 수열에 포함되므로 +1을 합니다.


3-3. i,j>0 and Xi != Yi

양수인 i,j에 대해서 Xi와 Yj가 서로 일치하지 않다면, 각각의 수열에서 하나씩 제거해서 LCS를 탐색합니다.

Xi와 Yj가 서로 일치하지 않을 때는 각각의 수열에서 마지막 문자를 제거한, c[i,j-1] 또는 c[i-1,j] 둘 중 하나가 최장 공통 부분 수열을 포함하고 있을 것입니다. 



4. 테이블 그리기


그럼 위에서 알아본 방법으로 LCS를 어떻게 구할까요?

바로 아래와 같은 테이블을 통해서 LCS를 구합니다.


 

j

0

1

2

3

4

5

6

i

 

Yi

B

D

C

A

B

A

0

Xi

0

0

0

0

0

0

0

1

A

0

 

 

 

 

 

 

2

B

0

 

 

 

 

 

 

3

C

0

 

 

 

 

 

 

4

B

0

 

 

 

 

 

 

5

D

0

 

 

 

 

 

 

6

A

0

 

 

 

 

 

 

7

B

0

 

 

 

 

 

 



먼저 X수열은 <ABCBDAB>이며 Y수열은 <BDCABA>라고 가정합니다.

테이블의 첫번째 열과 첫번째 행은 i또는 j가 0이므로 모두 0으로 채우도록합니다.

그리고 하나의 칸씩 채워보도록 하는데 이후 LCS의 길이뿐 아니라 그 수열까지 함께 구할 수 있도록 화살표를 함께 사용합니다.


각각에 대해서 탐색을 할때는 다음과 같은 방법을 이용합니다.

ㄱ) 두 문자가 같을 때, 좌측위에 있는 숫자에 1을 더한 값을 가지며 화살표는 좌측위를 가리킵니다.

ㄴ) 두 문자가 다를 때, 좌측이나 위에 있는 숫자중 큰 값을 가리키며 같은 값을 가집니다. 동일한 값일 때는 위의 값에 대해 행동합니다.


먼저, i가 1일때 1부터 6까지의 j에 대해 확인합니다.

X1는 A이며 Y1은 B이기 때문에 두 문자가 서로 다르고, 좌측과 위에 있는 숫자가 같은 값을 가지기에 그 값을 가지며 위를 가리킵니다.

X1과 Y2도 같은 방식이고, X1과 Y3 또한 같은 방식입니다.

X1과 Y4를 보시면 서로 같은 문자, A를 가지고 있습니다. 따라서 대각(좌측상단) 방향의 값보다 1큰 값인 1을 값으로 가지며 대각을 화살표로 가리킵니다.

이러한 방법으로 모든 칸을 채우면 아래와 같이 채워지게 됩니다.




따라서 LCS의 길이는 4이며 LCS수열을 구하고 싶다면 제일 좌측 하단에서부터 시작해 화살표 방향으로 따라가며 대각선방향을 가리키는 부분의 문자를 나열하면 됩니다.


이렇게 해서 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보았습니다.

추후 시간이 된다면 LCS알고리즘을 파이썬으로 직접 구현하여 테스트 해보도록 하겠습니다.


블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요



안녕하세요. 문범우입니다.

이번 포스팅부터 Introduction to Algorithm (3rd Edition) 책의 15장. 동적 프로그래밍(ch15, dynamic programming)에 대해서 이야기하려 합니다.

매주 1~2번 정도 포스팅 될 예정이며, 공부를 하면서 내용을 정리해서 올리기 때문에 잘못된 정보나 지식이 포함되어 있을 수 있으니 참고용으로 확인해주시고, 잘못된 내용에 대해서는 피드백 주시면 감사하겠습니다.

오늘은 동적 프로그래밍에 대한 개요와 동적 프로그래밍의 막대 자르기(Rod Cut)에 대해서 알아보겠습니다.


1. 동적 프로그래밍(Dynamic programming)


동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합하여 문제를 해결합니다.

이때, 프로그래밍이란 것은 코딩을 하는 것이 아니라 테이블을 이용하여 문제를 해결하는 방법을 말합니다.

동적 프로그래밍은, 동적 계획법, Dynamic programming, DP 등으로 부르기도 합니다.


분할정복 알고리즘은 기본적으로, 하나의 문제를 겹치지 않는 부분 문제들로 분할(divide)하여 해당 부분 문제들을 재귀적으로 해결한 후, 각각의 결과를 다시 결합하여 원래의 문제를 해결합니다.

반면, 동적 프로그래밍에서는 부분 문제가 서로 중복될 떄, 즉 부분 문제가 다시 부분 문제를 공유할 때 적용됩니다.

동적 프로그래밍 알고리즘을 이용하여 부분 문제를 한번만 해결하고 그 해를 테이블에 저장함으로써 각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있습니다.


일반적으로 최적화 문제(Optimization problem)에서 동적 프로그래밍을 적용합니다.

최적화 문제에서는 대체적으로 다양한 해를 가질 수 있는데 우리는 다양한 해들 중에서 최적(최소 또는 최대)의 해를 찾기를 원합니다. 이러한 해를 그 문제에 대한 유일한 최적해라고 하지 않고, 한 개의 최적해라 합니다. 최적의 값을 가지는 해가 여러개 존재할 수 있기 때문이죠.

동적 프로그래밍 알고리즘을 개발할 때는 아래의 4단계를 따릅니다.


1. 최적해의 구조의 특징을 찾는다.

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다.

4. 계산된 정보들로부터 최적해를 구성한다.


1~3 단계는 주어진 문제에 대한 동적 프로그래밍 해의 기초가 됩니다.

이어서 4 단계에서는 최적해의 값만 필요한 것이 아니라 최적해 자체가 필요할 때 수행하는 것으로써 값만 필요할때에는 생략할 수 있습니다.


2. 막대 자르기


막대 자르기 문제는 다음과 같습니다.

길이가 n인 막대와 i = 1,2,3,...,n에 대한 가격 p_i의 표가 주어지면 해당 막대를 잘라서 판매했을떄 얻을 수 있는 최대수익 r_n을 결정하는 것 입니다. 길이가 n인 막대의 가격 p_n이 충분히 비싸면 최적해는 자르지 않은 것일 수도 있습니다.


아래 표와 그림을 통해 확인해보겠습니다.


표에는 막대의 길이가 얼마일 때, 얼마의 가격인지가 나와 있습니다.

그리고 아래 그림에서 막대를 다양한 방법으로 잘라, 그 가격을 나타내고 있습니다.

(a) ~ (h)를 봤을 때 어떤 경우가 최적의 해 인가요?

막대를 2의 길이, 두 개로 자른 (c)의 경우의 수익이 10으로써 가장 최적의 해를 나타내고 있습니다.


위와 같이, 길이가 n인 막대는 개의 다른 방법으로 자를 수 있습니다.

제일 좌측에서 부터 i = 1,2,3,...,n-1 에 대한 모든 i길이마다 자르거나 자르지 않거나 하는 독립적인 선택이 가능하기 때문입니다.

만약 최적해가 막대를 에 대해 k의 조각으로 나누면,

막대를 조각 길이 로 나누는 다음의 최적의 분해는

 이며,

다음과 같은 최대의 해당 수익을 제공합니다.


좀 더 일반적으로 말하면, 에 대한  값을 더 작은 막대로부터의 최대 수익을 이용해 나타낼 수 있습니다.



첫 번째 인자 은 자르지 않고 길이가 n인 막대를 그대로 파는 것에 해당합니다.()

max 함수에 대한 다른 인자는 막대를 처음에 i와 n-i의 길이가 되도록 둘로 나누고 두 조각을 더 최적으로 잘라서 두 조각으로부터 최적의 이익을 얻습니다. 그런데 어떤 i의 값이 최대의 수익을 가져오는지 미리 알 수 없기 때문에 i에 대한 모든 가능한 값을 고려해야 합니다.


다시말해서, 크기가 n인 원래 문제를 풀기 위해서 종류가 같은 더 작은 크기의 문제를 풉니다.

처음에 자르기를 진행하여 도출된 두 가지의 문제는 서로 독립적인 예로 생각해도 됩니다.

전체적인 최적해는 두 부분 문제의 각각에 대해 수익을 최대화하는 해를 이용합니다.

이에 따라 막대 자르기 문제는 최적 부분구조(Optimal substructure)를 가졌다고 말합니다.

따라서 길이가 n인 막대의 모든 분해를 첫 번째 조각과 나머지 조각의 어떤 분해로 볼 수 있습니다. 그렇게 할 때는 막대를 전혀 자르지 않는 방법의 해를 포함하여 좀 더 간단한, 아래와 같은 식을 얻을 수 있습니다.



우리는 위의 식을 토대로 몇 가지 알고리즘을 구현해보도록 하겠습니다.


2-1. 하향식 재귀의 표현


알고리즘의 의사코드는 아래와 같습니다.



위의 CUT-ROD 의사코드에 대해 간략히 확인해볼까요?

길이 n이 0인 막대기는 당연히 0을 반환합니다.

그리고 그것이 아닐때에, 최대 수익 q를 음의 무한대로 초기화를 진행하고 i가 1부터 n까지 값으로 재귀 함수를 호출합니다.

이러한 알고리즘의 총 수행시간은,

   

입니다.


CUT-ROD 알고리즘이 위와 같은 수행시간을 보이듯, 비효율적인 이유는 무엇일까요?

그것은 CUT-ROD 알고리즘이 같은 인자를 똑같이 반복해서 계산하려고 하기 때문입니다.

아래의 트리를 보면 이해하기 쉬울 것 입니다.

n=4 일때를 보여주는 위의 트리에서, 재귀적으로 호출되는 함수 때문에 n=1 일때, n=2일때의 경우가 반복되서 호출되고 있습니다. 

즉 CUT-ROD 함수에서는 길이가 n인 막대를 자르는 데 가능한 개의 경우의 수를 모두 고려하고 있는 것 입니다.



3. 동적 프로그래밍을 이용한 최적의 막대 자르기


이제 1에서 알아보았던 동적 프로그래밍을 이용하여 막대 자르기 문제를 효율적으로 해결해보록 하겠습니다.

동적 프로그래밍은 위에서 알아본 바와 같이, 각 부분 문제를 단 한번만 풀고 그 해를 저장하도록 처리합니다.

그렇게 함으로써 반복되는 부분 문제의 해를 구할 떄 다시 계산하지 않고 저장된 값을 참조만 함으로써 시간소요를 줄일 수 있습니다. 하지만 이렇게 동적 프로그래밍은 시간을 절약하기 위해 부가적인 메모리를 사용합니다.

이것은 시간-메모리 트레이드 오프(Time-memory trade-off)의 한가지 예로써 작용합니다.


막대자르기 문제를 동적 프로그래밍 방법으로 해결하는데 있어서 크게 두 가지 방법이 존재합니다.

하나는 메모하기를 이용한 하향식 방법, 다른 하나는 상향식 방법입니다.



3-1. 메모하기를 이용한 하향식


메모하기를 이용한 하향식의 기본 개념은 2-1에서 진행한 하향식 재귀와 비슷합니다.

하지만 특정 부분 문제를 해결하였을때 해당 부분 문제의 해를 배열이나 해시 테이블에 저장해놓도록 수정하여 이후 같은 부분 문제가 반복되었을때 다시 계산하지 않고 배열이나 해시 테이블을 참조하여 이용할 수 있도록 함으로써 시간을 절약합니다.

아래는 메모하기가 더해진 하향식 CUT-ROD 의 의사코드입니다.

메인 알고리즘, MEMOIZED-CUT-ROD는 새로운 배열 r[]을 선언하고 음의 무한대로 초기화 합니다.

배열 r의 구성은, 특정 길이 n'에 대한 최적의 해를 r[n']에 저장합니다.

그리고 길이 n에 대해서 MEMOIZED-CUT-ROD-AUX 함수가 호출이 됩니다.

그리고 1행에서 길이 n에 대한 최적의 해가 존재하다면 그것을 리턴하게 됩니다.

(초기에 배열 r[]을 음의 무한대로 초기화 하였으니 특정 길이 n'에 대하여 r[n']의 값이 0보다 크거나 같다면 길이 n'에 대한 최적의 해가 저장되어 있다는 것을 알 수 있습니다.)

계산되어 있지 않다면 이후 3행부터는 2-1에서 진행한 하향식 재귀함수와 동일합니다.



3-2. 상향식 방법


상향식 방법은 보다 간단합니다.

상향식 방법에서는 동적 프로그래밍 방법에서 부분 문제의 자연스러운 순서를 사용합니다.

만약 i > j 이라면 크기 i의 부분 문제는 크기 j 의 부분 문제보다 작습니다. 그러므로 해당 상향식 방법에서는 크기가 0부터 n으로 커지는 부분 문제의 크기 순으로 해결합니다.


수도코드의 1행에서 배열 r[]에 대해서 선언하고 이후 우리는 r[] 배열에 부분 문제의 결과를 저장할 것 입니다.

그리고 길이가 0인 막대에 대한 최대 수익은 0 이므로 2행에서 r[0]=0 으로 저장합니다.

3행에서부터는 길이가 1부터 j까지 하나씩 증가하는 각 부분 문제를 해결하여 값을 구하고 그것의 값을 7행에서 배열 r[]에 저장합니다.

마지막 8행에서 우리가 얻고자 하는 길이 n에 대한 최대 수익값을 리턴하게 됩니다.

이러한 상향식 방법의 수행시간은 을 가집니다.



3-3. 해의 재구성


우리가 위에서 공부한 두가지 알고리즘에서는 최적 해의 대한 값만 도출합니다.

즉, 길이가 n에 대한 막대를 통해 얻을 수 있는 최대 수익만을 반환할 뿐이지 해당 막대를 어떻게 잘라야 하는지는 리턴하지 않습니다.

이러한 동적 프로그래밍 방법을 각각의 부분 문제에 대한 계산된 최적 값 뿐만 아니라, 그 최적 값에 이르는 선택도 기록하도록 확장할 수 있습니다. 즉 이러한 정보와 함께 최적 값 뿐 아니라 최적해 자체를 쉽게 출력할 수 있습니다.



위의 수도코드에서는 그 전과 다르게 1행에서 배열 s[]를 선언합니다. 그리고 8행을 확인하시면 잘라내는 첫번째 조각의 최적크기 i를 보관하는 것을 알 수 있습니다.

그리고 최적 해를 가지는 r과 최적의 첫 번째 막대 크기들의 배열 s[]을 반환합니다.

아래 수도코드는 길이 n의 막대의 최적 분할에서의 모든 조각 크기의 리스트를 함께 출력합니다.





이렇게 해서 동적프로그래밍에 대한 개요와 하나의 예제인 막대 자르기(Rod-cutting) 에 대해서 공부해보았습니다.

추가적으로 궁금하신 점이나 피드백해주실 점은 댓글 또는 이메일(doorbw@outlook.com)을 이용해주세요 :)



블로그 이미지

Tigercow.Door

Web Programming / Back-end / Database / AI / Algorithm / DeepLearning / etc

댓글을 달아 주세요