머가필요해

[ Terminology & Problem ]

이번에 살펴보고자 하는 알고리즘은 "Longest Common Subsequence (LCS)" 이다.
어떤 문제를 해결하고자 하는 것인지 설명하기 전에 용어에 대한 정의부터 살펴보겠다.

여기에서 주의깊게 살펴봐야 할 것은 "Substring"인데, 연속적인 character를 의미한다.

반면, "Subsequence"는 비연속적인 character 순서를 포함한다.

2개의 string이 주어졌을 때, 공통적으로 있는 subsequence를 "Common Subsequence"라고 한다.

그리고 "Common Subsequence" 중에서 가장 긴 길이를 갖는 것을 "Longest Common Subsequence (LCS)"라고 한다.

이런 LCS를 구하는 방법을 찾는 것이 이번 목표이다 ^^

[Brute force approach]

착실하게 (무식하게?) 찾는 방법은 다음과 같다.

당연히 이렇게 찾는 것은 말이 안된다.

입력 string의 갯수가 n개라고 했을 때 2의 n승만큼 subsequence가 나오기 때문이다.

[Notation]

이후 설명할 내용에서 사용하는 notation을 정리하면 다음과 같다.

[Idea]

똑똑하게 해결하기 위한 아이디어는 다음과 같다.

복잡해보이는데, 가만히 살펴보면 엄청 당연한 이야기를 하고 있다.

특정 위치의 chracter가 같다면 LCS는 그 같은 값은 일단 LCS에 포함되는 것이고,

각 입력 string에서 동일한 값보다 1씩 작은 string의 LCS값을 더해주면 전체 LCS가 된다.

반면, 특정 위치의 chracter가 같지 않다면 LCS는 입력 string중 하나의 값을 1 차감한 내역으로 다시 LCS를 구하면 된다.

[ Longest Common Subsequece - Dynamic Programming Algorithm ]

위의 아이디어를 정리하면 다음과 같은 알고리즘이 된다.

이걸 어떻게 하는 것인지 살펴보자.

다음과 같은 2개의 string이 입력되었을 때 다음과 같은 표를 그리고 초기화 하자.

  - X = ABCBDAB

  - Y = BDCABA

앞에서 정리한 알고리즘을 기반으로 하나씩 값을 채워나가면 된다.

① x ≠ y 이므로 둘 중 큰 값 선택해야 하는데, 둘 모두 0이므로, 0

② ③ 상동

④ ⑥ x = y 이므로, 왼쪽 대각선 위의 값 + 1

⑤ x ≠ y 이므로 둘 중 큰 값 선택해야 하는데, ④ 값이 1이므로, 1

그리고, 어느 곳에서 값을 받아갔는지 화살표로 표기 해줘야 한다.

이런식으로 하나씩 값을 작성해 나가면 다음과 같이 된다.

LCS값이 어떻게 되었는지는 다음과 같이 추적해볼 수 있다.

화살표를 보면 알겠지만, 정답이 하나만 있는 것은 아니다.

[Pseudo Code]

손으로 진행했던 것을 코드로 만들어 보자.

손으로 진행했던 것과 차이가 있는 부분 위주로만 설명해봤다.

위 표에서 화살표를 살짝 끄적였는데, code에서는 b array를 통해 기록하도록 했다.

결과를 출력하기 위한 코드는 다음과 같다.

[Time & Space]

code를 보면 직관적으로 파악 가능한 것 처럼 Time complexity는 다음과 같다.

Space는 b array + c array 공간이 추가적으로 필요하기에 다음과 같다.

그런데, Space를 줄일 수 있는 경우가 있다.

실제 String 정보까지는 필요없고, 길이값만 필요하다고 하면 다음과 같이 작은 space만 필요로 한다.

또 다른 경우로는 다음과 같은 case가 있을 수 있다.

LCS에 대해서는 여기까지~

왠지 이름만 들어도 어려울 것 같은 느낌이 팍팍 드는, Dynamic Programming !!!

연구비를 타내기 위해 그냥 있어보이려고 멋지게 작명하다보니 이런 이름을 가졌다고 한다.

사람 사는게 다 그렇지 뭐~ ^^

"Dynamic Programming"은 뭔가 계산하는 알고리즘이라기 보다는

작은 문제를 풀어서 그 중간 결과를 기록해 놓음으로써 다시 재계산하지 않도록 하는 방법이다.

여러 유형의 문제를 Dynamic Programming으로 푸는 것을 살펴볼텐데

그 첫번째로 살펴볼 것이 바로 "Assembly-line scheduling" 이다.

[Definition]

'Assembly-line'이라는 것에 대한 정의 부터 살펴보자.

컨베이어벨트를 따라 단계별로 부품 조립하는 것을 생각하면 된다.

- station : 조립 단계. 제품 조립은 n개의 station을 거치면 완성이 된다.

- a : 각 station 단계에서 소요되는 시간

- line : 하나의 컨베이어 벨트로 생각하면 된다.

- e : line에 조립을 시작하도록 하기 위해 소요되는 시간

- x : 조립 완료된 제품을 전달하기 위해 소요되는 시간

- t : line을 옮기기 위해 소요되는 시간

[Problem]

여러 line으로 구성된 assembly-line이 있을 때,

어떤 경로가 가장 짧은 소요 시간으로 조립할 수 있는지 최적의(가장 빠른) 경로를 찾는 방법은?

[Solution-1]

가장 확실하고 무식한(?) 방법으 모든 경우의 수를 구해서 찾는 방법이다.

하지만, 말 그대로 무식한 방법이기에 ... 경우의 수가 너무 크다.

[Solution-2]

스마트한 방법을 찾아보자.

▷ Idea

어느 시점(S)에서 자기 순서까지 올 수 있는 방법은 2가지 경우 밖에 없다.

자기가 있는 동일한 line의 직전 단계에서 오는 방법과, 다른 line의 직전 단계에서 오는 2가지의 경우이다.

그러면, 그 2가지의 경우 중에 가장 빠른 것을 선택하면 되게 되는 것이다.

▷ How to

그러면 예시를 살펴보자.

각 단계에서 소요되는 시간을 더해가면서 정리하면 된다.

보다 더 짧은 시간을 선택하면 되기 때문에 □로 표기된 값들이 선택된 결과들이다.

이렇게 선택하는 과정에서 소요되는 Running Time은 어떻게 될까?

각 Station에서 2개씩 값을 보면 되기 때문에 2n의 Running Time이 필요하고,

entry + exit 과정이 있기 때문에 이를 정리하면 다음과 같다.

Brute-force 방법으로 할 때에는 어느 시점(S)에서 자기한테 까지 오는 모든 경우의 수를 살펴보지만

지금 방식에서는 바로 직전의 2가지 경우만 살펴보기 때문에 n에 비례하는 복잡도를 갖게 되었다.

그러면, 중간에 각 S단계에 따른 값들을 어떻게 저장하면 될까?

위와 같은 표 내용만 기록/기억 하고 있으면 되는 것이다.

그런데, 이 것만 가지고는 어떤 경로로 구성된 것인지 알기가 어렵다.

이 내용을 기록할 표가 하나 더 필요한 것이다.

그런데, 2개의 테이블이 모두 필요할까?

경로만 확인 가능해도 되는 경우에는 L table만 있으면 된다.

S table은 현재 값과 직전 값만 알면 되고, 최적해(S* = 38) 값만 저장하면 된다.

S table에서 S3를 계산할 때 S2 값만 알면 된다. 즉, S1의 내용은 필요 없다.

메모리를 굳이 table 전체 크기만큼 잡아 놓지 않아도 된다는 것이다.

L table 값만 알면 최적 경로를 찾을 수 있기 때문이다.

반대로 S 값을 갖고 있는 table만 있어도 L 값 table 없이 경로를 찾아낼 수는 있다.

하지만 L 값 table을 사용하는 것이 훨씬 더 편하기에 L Table을 이용하는 것이다.

▷ Pseudo Code

코드로 구현해보면 다음과 같다.

뭔가 복잡해보이는데, 살펴보기 편하게 구분해보면 다음과 같다.

결과를 출력하는 부분은 아래와 같이 구현해볼 수 있다.

실행 결과는 다음과 같이 나올 것이다.

▷ Space consumption

일단 기본적으로는 S table과 L table 모두 필요로 한다는 전제 하에 다음과 같은 메모리 사용량을 필요로 한다.

▷ Running time

하나의 요소 別 소요 시간이 Θ(1) 소요시간이 걸린다고 했을 때, 전체 소요 시간은 Θ(n)이라고 할 수 있다.

뭔가 심오한 Dynamic Programming의 세계이다~