태그

[SW Expert Academy] Advanced-8 Dynamic Programming1-2

Dynamic Programming (동적 계획법)


 플로우 1. 수학적 귀납법 2. 비둘기집의 원리 3.메모이제이션 4. 동적 계획법(dynamic programming) 5. 분할 정복 vs DP 6. Knapsack 7. Best-Frist Search(A* algorithm)
1. 수학적 귀납법
1)n=1일때 성립함을 증명한다.
2)n=k일때 성립하면 -> n=k+1일떄도 성립함을 증명한다.

-예시
피보나치수를 구하기 위한 recursive function(fibo(n)) 코드를 떠올려보자.
fibo(n)의 재귀적 호출  횟수는?

T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2) +1 if n>=2
T(n) >= 2*T(n-2) >=2^2*T(n-4)..... >=2^(n/2)*T(0) = 2^(n/2)

-증명
T(2) = T(0) + T(1) + 1 = 3 > 2^1(1 = n/2임)
T(3) =T(1) + T(2) + 1 = 5 > 2^(3/2) = 2.83

2<=m<n인 모든 m에 대해 T(m) > 2^(n/2)라고 가정하면,
T(n) = T(n-1) + T(n-2) + 1 >= 2^( (n-1)/2 ) + 2^( (n-2)/2) ) + 1 >=  2^((n-2)/2)*2 = 2^(n/2)
따라서 성립

2. 비둘기집의 원리
비둘기 n+1마리, 비둘기 집 n개라면 -> 적어도 한개의 비둘기집에는 2마리 이상의 비둘기가 있다.
n+1개의 물건을 n개의 상자에 넣으면 어느 하나의 상자에는 2개이상의 물건이 들어있다.

-귀류법을 통한 증명
n개의 비둘기 집과 n+1마리의 비둘기가 있다고 가정하자.
만일 어떤 비둘기 집에서 1마리의 비둘기만이 거주한다면, 전체 비둘기집에는 많아야 n마리의 비둘기가 있음.
이는 n+1마리의 비둘기가 있다는 가정에 모순된다.
따라서 적어도 1개의 비둘기집에는 2마리 이상의 비둘기가 있다.

-예시
-서울 시민(1000만명) 중 같은 갯수의 머리카락(20만이하)를 가지는 사람이 있을까?

-피보나치 수열 중복 증명
n번째 피보나치수를 구하기 위해서는 fibo(0)~fibo(n-1)까지의 값을 알아야함. -> 총 n번 호출하면 구할 수 있다.
하지만 피보나치 수열 함수의 호출 횟수는 2^(n/2)임.
따라서 같은 함수를 호출하는 중복이 반드시 발생함.

3. 메모이제이션
컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 다시 계산하지 않도록 하여 실행 속도를 높이는 기술
피보나치수를 구할때 메모이제이션을 이용하면 실행시간이 O(n)으로 줄 수 있다. 
//memo[0], memo[1]은 1로 초기화, 나머지는 0으로 초기화
fibo(n):
 if n>=2 and memo[n] = 0:
  memo[n] = fibo(n-1)+fibo(n-2)
 return memo[n]

그런데, 재귀호출을 사용하면 시스템 호출 스택으로 인한 메모리 사용량이 증가하고, 함수 호출을 위한 추가 작업이 필요하다. (실행속도 저하 및 스택오버플로우 위험성)
함수 호출 오버헤드를 없애기 위해서 반복문을 사용한다.

4. Dynamic Programming
최적화 원칙(Principle of Optimality)이 적용되어야함.
-최적화 원칙: 어떤 문제에 대한 해가 최적일때, 그 해를 구성하는 작은 문제들의 해 역시 최적이어야한다.
-원칙에 위배되는 예제
Longest Path문제 (사이클이 없는 단순 경로)
A->D로 가기 위한 longest path가 A->C->B->D이라고 해서,
A->C로 가는 최장 경로가 반드시 A->C인것은 아니다. (A->B->C)
(A->B->C->B->D는 사이클이 생기니까)
이런 문제는 DP로 해결 안된다.

5. 분할 정복 vs DP
분할 정복
1) 문제를 부분 문제로 분할
2) 부분 문제를 재귀적으로 해결, 필요 시 부분문제의 해를 결합
3) merge/quick sort를 보면, 작은 문제의 해가 큰 문제의 해에 중복되서 사용되지 않는다. 

-하향식 방법
-주어진 큰 문제를 나눌 수 없을때까지 쪼개서, 작은 문제의 해를 구하고 더 큰 문제를 해결

DP
-부분 문제들이 더 작은 부분문제들의 해를 공유하고(중복 발생),
-모든 부분 문제를 한번만 계산하고 결과를 저장함으로써(메모이제이션), 필요시 재사용한다.
-상향식 방법
-의존성에 위배되지 않게 작은 문제의 해를 구하여 더 큰 문제의 해를 구함.
fibo_dp(n)
 f[0] = 0, f[1] = 1
 for i in 2->n:
  f[i] = f[i-1] + f[i-2]
 return f[n]

6. Kanpsack(배낭) 문제
Kanpsack문제는 물건을 쪼개서 담을 수 있으면 greedy, 그렇지 않다면 DP로 풀면 된다. 

-완전 검색으로 구하기
물건의 부분집합을 전탐색하여 모두 구하고, 그 중 총 무게가 W이하이면서도 총 Price가 최대인 집합을 탐색한다.
kanpsack(W, k, curValue): //k: 배낭을 넣을 물건(0, ... NUM_OF_ITEM-1)
 if W >= 0:
  if k == NUM_OF_ITEM:
   if maxValue < curValue:
    maxValue = curValue
  else:
   knapsack(W-weight[k], k+1, curValue+value[k])
   knapsack(W, k+1, curValue)

-DP로 구하기
M[i][w] =      0                                              , if i==0 or w==0
                m[i-1][w]                                      , if wi>w
                max(vi + m[i-1][w-wi], m[i-1][w])  , if wi<=w

-메모이제이션 + 재귀함수
W가 엄청나게 크면, 이 방법이 DP보다 빠를 수도 있다고 생각한다.

kanpsack(i, W):
 if m[i][w] != -1:
  return m[i][w]
 if i==0 or w==0:
  return m[i][w]=0
 else:
  case1=case2=0
  if W>=weight[i]:
   case1 = kanpsack(i-1, W-weight[i]) + value[i]
  case2 = kanpsack(i-1, W)
  m[i][w] = max(case1, case2)
  return m[i][w]

-DP
for i <- 0 to n: m[i][0] = 0
for w <- o to W: m[0][w] = 0

for i <- 1 to n:
 for w <- 1 to W:
  if wi > W:
   m[i][w] <- m[i-1][w]
  else:
   m[i][w] = max(m[i-1][w], m[i-1][w-wi] + vi)
return m[n][W]


7. 상태 공간 트리 탐색 방법
상태 공간 트리 탐색 방법에는 크게 3가지가 있다: DFS, BFS, Best-First Search (A* algorithm).

-최적화를 위한 방법
1. 가지치기
탐색하는 노드에서 최적해를 찾을 가능성이 없으면 가지치기를 수행한다,
2. 유망성 판단
탐색하는 노드의 유망성을 판단: 한계치(bound)를 계산한다.
bound: 그 노드에서 계속 탐색을 수행하면 얻을 수 있는 후보 해답의 최대치
지금까지 찾은 최적의 값보다 bound가 좋지 않으면 유망하지 않다.


-DFS+유망성
checknode(node v):
 node u
 if value(v) is better than best:
  best <- value(v)
 if promising(v)
  for each child u of v:
   checknode(u)

-Kanpsack에 유망성을 적용해보기
wi, pi: i번째 물건의 무게/가치
무게 당 가치(pi/wi) 순으로 내림차순 정렬한다. 

방문하는 각 노드에서 다음 값을 계산한다
profit: 그 노드에 오기까지 넣었던 물건 가치의 합
weight: 그 노드에 오기까지 넣었던 물건 무게의 합
bound: pi/wi가 큰순으로 물건을 계속 담는다. k번째 물건이 쪼개져서 담을 수 있다고 가정하면, k번째 물건을 쪼개서 담는다. 물건을 쪼개서 담는 가치의 최대값이 곧 bound가 된다. 

알고리즘은 O(2^n)이지만, 일반적으로 DP보다 빠르다고 함. 
DFS의 문제는 재귀적이라 작성이 복잡하고 반복적인 함수 호출 비용이 발생한다.

-BFS+유망성

//일반적인 BFS
BFS(T): //T: 상태공간트리
 node u, v
 init(Q)
 v <- root of T
 visit(v)
 enqueue(Q, v)
 while !empty(Q):
  dequeue(Q, v)
  for each child u of v:
   visit(u)
   enqueue(Q, u)

//Knapsack: BFS+유망성
BFS(T):
 node u,v
 init(Q)
 v <- root of T
 enqueue(Q, v)
 best = value(v)
 while !empty(Q):
  dequeue(Q, v)
  for each child u of v:
   if value(u) is better than best: best = value(u)
   if bound(u) is better than best: enqueue(Q, u)
//방문하는 자식 노드의 bound를 계산하여 가지치기를 한다. 

일반적으로 DFS+유망성보다 느림

-Best-First Search
1. 주어진 노드의 모든 자식 노드를 탐색한다.
2. 유망하면서 확장되지 않은 노드를 확인한다.
3. 그 중 가장 좋은 bound를 가지는 노드를 우선적으로 확장한다. 

BFS에 비해 탐색 성능이 우수하다.
priority queue를 이용하여 최대 bound를 가진 노드를 우선적으로 탐색한다.

best_first_search(T):
 node u, v
 init(PQ)
 v = root of T
 best = value(v)
 insert(PQ, v)
 while not empty(PQ):
  remove(PQ, v)
  if bound(v) is better than best:
   for each child u of v:
    if value(u) is better than best:
     best = value(u)
    if bound(u) is better than best:
     insert(PQ, u)

-단점
최적해를 빠른 시간에 찾는다는 보장이 없다. -> 일반적으로 최적해는 상태 공간 트리의 깊은 곳에 존재할 가능성이 높기 떄문이다.
최적해를 찾을 가능성이 높은 노드를 평가하는 비용 발생
후보 노드들의 리스트를 저장하기 위한 많은 메모리 요구




















Reference
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만, 인사이트



라벨:

댓글

댓글 쓰기

가장 많이 본 글