Dynamic Progamming (동적 계획법, DP)

Dynamic Progamming?

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

 

원리

• 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것
• 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그 문제를 간단하게 해결할 수 있다.
• 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다.
• 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

 

언제 사용할까 ?

• 최적화 문제
• 경우의 수 구하기 

 

과정

1. 문제를 부분 문제로 분할한다.
2. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다.
3. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다. 

 

✔︎ Memoization

: 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

 

---

 

코드 비교

ex) 피보나치 수를 구하는 함수

1. 재귀 함수로 구현

 

def fibo(n):
  	if n < 2:
      	return n
    else:
      	return fibo(n-1) + fibo(n-2)

 

• 위의 코드는 문제점이 있다. 바로 "엄청난 중복 호출이 존재한다"는 것이다.
• n=50 으로 준다고 예를 들면, DP를 적용하지 않은 코드는 함수를 21891번 호출하지만, DP를 사용한다면 39번만 호출한다.
  • 왜냐하면 fibo(n)을 구할 때의 fibo(n-2)는 fibo(n-1)을 구할 때는, 그때 당시 fibo(n-1)일 텐데
    ( fibo(n)에서의 fibo(n-2) == fibo(n-1)에서의 fibo(n-1) )
    그럼 이걸 처음 구할 때, 이 값을 저장해놓으면 가져오기만 하면 되지만(DP), 그렇지 않다면 fibo(n)을 구할 때, fibo(n-2)를 또 재귀를 통해서 구해와야 하기 때문이다. (이게 n이 커진다면 엄청난 중복 호출이 된다.)
  • 따라서 DP를 이용하면 실행 시간을 Θ(n)으로 줄일 수 있다. 

 

 

2. DP로 구현

1) recursive(재귀) 방식 

• 탑다운(top-down) 방식 (재귀로 계속 내려가기 때문)

 

def fibo1(n):
    global memo
    if n >= 2 and memo[n] == 0:
      	memo[n] = fibo2(n-1) + fibo2(n-2)
    return memo[n]

n = int(input())
memo = [0] * (n+1)
memo[1] = 1

 

2) iterative(반복 구조) 방식 

• 바텁업(bottom-up) 방식 (계속해서 채워나가기 때문)

 

def fibo2(n):
    f = [0, 1]
    
    for i in range(2, n+1):
      	f[i] = f[i-1] + f[i-2]
        
    return f[n]
  
n = int(input())
f = [0] * (n+1)

 

• DP는 재귀적 구조에 사용하는 것보다 반복적 구조로 DP를 구현한 것이 성능 면에서 보다 효율적이다.
• 재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문이다.

 

---

 

문제 풀어보기

• SWEA) 4869. 종이 붙이기
  • 풀이 코드
• SWEA) 4613. 러시아 국기 같은 깃발
  • 풀이 코드
• BOJ) 9095. 1, 2, 3 더하기
• BOJ) 2193. 이친수
• BOJ) 1904. 01타일

 

---

참조

https://ko.wikipedia.org/wiki/동적_계획법