Algorithm Analysis - Dynamic Programming 2 SERIES 2/4

Blog Logo
on



read

Algorithm Analysis: Dynamic Programming 2

알고리즘 관련 모든 글은 연세대학교 안형찬 교수님의 CSI_3108: Algorithm Analysis의 강의 내용과 자료입니다.

Dynamic programming을 적용할 수 있는 또다른 문제를 살펴보겠습니다.

Longest nondecreasing subsequence

Given a sequence of integers $ a_1, … , a_n$, find a longest subsequence (which is not necessarily contiguous) that is nondecreasing.

예시를 보겠습니다.

40, 41, 2, 41, 7, 8, 15, 1, 3

이전 Minimum cost travel처럼 $OPT(i)$1를 $a_1, … , a_i$에 있는 longest non-decreasing subsequence의 “길이”라 해보겠습니다. 그렇다면 $OPT(9)$를 구할 때 그 이전 solution인 $OPT(8)$에 3을 더할 수 있을지 없을지 모릅니다. 왜냐하면 $OPT(i-1)$에서 있는 longest non-decreasing subsequence의 끝 원소가 3보다 큰지 작은지 알 수 없기 때문입니다. 쉽게 말해 이전 재귀 호출에서 온 결과값에는 이전 원소에 대한 정보가 없는 상태입니다. Boundary 원소(subsequence 끝에 있는 원소)가 무엇인지에 따라 우리의 현재 재귀 단계에서의 결정이 영향을 받습니다. 이런 경우를 decision들이 boundary를 걸쳐서 coupled되어 있다고 합니다. 이를 고쳐보겠습니다.

이미 말했듯이 우리의 현 재귀 단계에서의 $a_i$가 그 non-decreasing subsequence에 포함될지 여부가 결정이 되기 힘든 상태입니다. 그렇다면 아예 우리의 $OPT(i)$는 $a_i$를 반드시 포함하는 longest non-decreasing subsequence의 길이라고 정의해보겠습니다. 이 경우, 우리의 $OPT(i)$는 $a_i$ 1개로만 이루어져 있는 subsequence이거나 아니면 앞쪽에서 나온 결과에서 $a_i$보다 작거나 같은 $a_j$를 마지막으로 갖는 sequence 중 가장 긴 것에 $a_i$가 붙은 형태의 sequence가 됩니다. 점화식은 이렇게 마지막 결정을 “rewinding”하는 방식으로 작성하게 됩니다.

Lemma2 1

For all $1 \le i$ ,

점화식은 해당 optimal solution을 찾을 수 있도록 전체 경우를 다 커버해야 하고, 그리고 구현 가능해야 합니다. 지금부터 그것을 증명해보겠습니다.

$Proof.$

이제 위의 점화식을 증명하는 과정입니다. 증명의 큰 그림은 아래와 같습니다.

  • $LHS(좌변) \le RHS(우변)$ 임을 보이고
  • $LHS(좌변) \ge RHS(우변)$ 임을 보이면
  • 결국 $LHS(좌변) = RHS(우변)$ 이라는 사실이 됩니다.

우선 $a_1, … , a_i$의 수열에서 마지막 원소인 $a_i$로 끝이 나는 longest non-decreasing subsequence를 생각해보겠습니다. 이를 $a_{k_1}, … , a_{k_l} \,\, (k_l = i)$이라 지칭하겠습니다. 만약 $l=1$의 경우에는 $OPT(l)=1$ 입니다.

하지만 그렇지 않고 만약 $l > 1$ 이라면, $j = k_{l-1}$ ($1 \le j \le i-1, \,\, a_j \le a_i$) 를 상정하겠습니다. 우리는 이를 통해 $OPT(j) \ge OPT(i) -1$ 를 알 수 있습니다(이 말이 아직 무슨 말인지 잘 와닿지 않을 수 있습니다. 하지만 일단 끝까지 읽어보기를 바랍니다). $OPT(i)$와 $OPT(j)$는 우선 우리 가정에서 optimal한 solution을 냅니다. 하지만 $OPT(i)$에서 1을 뺀 숫자가 $j$번째 원소까지의 subsequence에 대해 optimal한 값인지는 아직 모릅니다(아직은 우리가 지금 증명하는 중이니까). 그렇지만 “$OPT(i)-1$”은 $a_{k_1}, … , a_{k_{l-1}}$이고, 이는 $a_1, … , a_j$ 중 어떤 하나의 non-decreasing subsequence라는 사실은 압니다. 이는 아무리 커도 $OPT(j)$는 넘지 못 합니다. 왜냐하면 $OPT(j)$가 우리가 앞서 가정했듯이 optimal하기 때문입니다. 이에 따라 Lemma1에서 $LHS(좌변) \le RHS(우변)$임을 알았습니다.

이제 반대도 보이겠습니다. 앞서 말했듯이 우리는 $OPT(i)$를 $a_i$를 반드시 포함하는 longest non-decreasing subsequence의 길이라고 정의했기 때문에 $OPT(i) \ge 1$ 입니다. 나아가 $OPT(i) \ge OPT(j) +1$ 가 성립합니다. 왜냐하면 $OPT(j)$에 무언가 하나를 더해서 $OPT(j)+1$짜리 어떤 하나의 non-decreasing subsequence를 만든다 하더라도 optimal한 $OPT(i)$보다 클 수는 없기 때문입니다. 따라서 $LHS(좌변) \ge RHS(우변)$이 됩니다.

그러므로 $LHS(좌변) = RHS(우변)$ 가 성립합니다.


알고리즘 구현

이제 알고리즘을 적어보겠습니다.

//우선 0번째에서 가장 긴 길이는 0입니다(초기화 목적)
M[0]=0

//이제 1번째 원소에서부터 n번째 원소까지 돌면서
for i, from 1 to n:

	prev_maxSubsequent=-infinity
	// 지금 i보다 앞에 있는 원소들을 돌면서
	for j, from 0 to i-1:

		// 만약 그 앞에 있는 애들 중 j번째 원소가 i번째 원소보다 작거나 같으면서
		// 지금까지 봤던 앞선 subsequent보다 길이가 길면
		if (a_j <= a_i) && (M[j]>prev_maxSubsequent):

			// 그 j번째 원소가 갖는 max subsequent를 저장해둡니다.
			prev_maxSubsequent=M[j]

	// i번째 원소 앞에 있는 애들을 다 돌고 나와서는
	// i번째가 갖는 가장 긴 subsequence의 길이는
	// 이전 원소들로 끝나는 subsequence 중에서 가장 긴 길이에 1을 더해준 것입니다.
	M[i] = prev_maxSubsequent+1

정리를 해보면 나보다 앞에 있는 애들 중 나보다 작은 애로 끝나는 longest subsequence 중에서 가장 긴 것의 길이를 받아와서 내 자신을 더해주는(+1) 과정입니다.

시간복잡도 계산

이 알고리즘은 $O(n^2)$의 시간복잡도를 갖습니다. 왜냐하면 나보다 앞선 애들 중에서 찾는 for문이 $O(n)$인데(1부터 $i-1$까지, 즉 최대 $n-1$까지) 이런 과정을 최대 $n$번 하기 때문입니다. 좀더 간단하게 시간복잡도를 계산하는 방법은 Memoization을 위한 table에 몇 개의 원소(“행의 숫자x열의 숫자”를 하면 총 원소 개수가 나오겠죠?)가 있고, 그 table의 칸 하나를 채우기 위해서 시간이 얼마나 걸리는지를 생각하는 식입니다.

실제 subsequence를 뽑아보기

지금까지는 단순히 가장 긴 non-decreasing subsequence의 길이를 리턴했습니다. 하지만 마지막으로 이번에는 그 실제 subsequence를 출력하는 알고리즘을 구현하겠습니다.

M[0]=0

for i, from 1 to n:
	prev_maxSubsequent=-infinity

	for j, from 0 to i-1:
		if (a_j <= a_i) && (M[j]>prev_maxSubsequent):
			prev_maxSubsequent=M[j]

			//prev_maxSubsequent인 애의 index를
			//previous라는 배열의 i번째(현 상위 for문 index)에 저장해둡니다
			previous[i]=j

	M[i] = prev_maxSubsequent+1

max_length=0
for i, from 1 to n:
	if M[i] > max_length:
		max_length=M[i]
		last_index=i

while last_index!=0:
	//a가 원래 인풋으로 주어진 sequence
	//가장 긴 길이를 갖는 subsequence의 마지막 애를 stack에 넣습니다
	push a[last_index] to STACK

	//그리고 이전에 저장해두었던 previous를 이용해 이 last_index이전에 어떤 애가 왔었는지를 찾아내
	//last_index를 업데이트 합니다
	last_index=previous[last_index]

	//더이상 전에 어떤 애가 없고 이번 애에서 시작한 거라면 previous[last_index]는 0일 것입니다.
	//그러면 while문을 빠져나옵니다

pop everything from STACK
return sol

마지막에 STACK에서 다 pop하면 그 해당 longest non-decreasing subsequence가 출력됩니다.

정리

이전 글부터 지금까지 논의된 결과를 보면, minimum cost travel에서는 마지막 도시에서 잘 지 여부가 결정이 되지 않으니 그냥 무조건 마지막 도시에서는 자는 것을 $OPT(i)$로 설정하였습니다. 그리고는 그 마지막 도시를 기준으로 그 도시에 하루만에 도달할 수 있는 도시들만 고려하여 그 도시들로 다시 $OPT(k)$를 호출하였습니다.

이번 문제에서는 마지막 원소가 그 longest non-decreasing subsequence에 포함될지 여부를 모르니 $OPT(i)$를 $i$번째 원소를 무조건 포함하여 그 원소를 마지막으로 하는 longest non-decreasing subsequence의 길이라고 가정했습니다. 그래서 이번 원소 1개로 이루어진 subsequence가 되든지, 아니면 그 이전 것(이번 원소보다 작거나 같으면서)으로 끝나는 가장 긴 non-decreasing subsequence에 $i$번째 원소를 더한 꼴(+1)이 되게끔 하였습니다.

따라서 마지막 decision을 rewinding할 때 무언가 결정 여부가 앞 결과에 따라 바뀐다면 아예 결정을 지은 형태로 $OPT(i)​$를 재정의해보는 것도 좋은 전략인 것 같습니다. 그리고는 그 지어진 결정을 중심으로 문제를 접근해보는 것이 요점이 아닐까 싶습니다.

  1. Optimal solution을 리턴하는 함수라는 의미입니다 ↩

  2. 부명제 (다른 진술이 참임을 검증하기 위해 참인 것으로 여겨지는 진술) ↩

Algorithm Analysis

Written by
Blog Logo

순록킴

Published

Supported by