DP(다이나믹 프로그래밍)

Dynamic Programming

- 그리디 알고리즘과 같이, 최적화 문제를 해결하는 알고리즘이다.

- 문제를 부분 문제로 분할한 후 가장 작은 부분 문제부터 해를 구하여 결과를 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구하는 알고리즘이다.

 

다음은 피보나치 함수를 DP로 구현한 예시이다.

# 기록할 배열의 크기를 먼저 정해놓는 경우
def fibo1(n):
    arr = [0] * (n+1)
    arr[1] = 1      # 최초의 부분문제의 해를 배열에 기록

    for i in range(2, n+1):
        arr[i] = arr[i-1] + arr[i-2]    # 각 부분문제의 해를 구하여 저장

    return arr[n]
    
    
# 배열의 크기를 미리 정하지 않고 해결하는 경우
def fibo2(n):
    arr = [0, 1]

    for i in range(2, n + 1):
        arr.append(arr[i-1] + arr[i-2])

    return arr[n]

 

 

팩토리얼도 DP로 구현 가능하다.

def factorial(n):
    arr = [1]

    for i in range(1, n + 1):
        arr.append(i*arr[i-1])

    return arr[n]
    
    

# 배열 크기를 미리 지정
def fact(n):
	table = [0] * (n+1)
    table[0] = 1
    
    for i in range(1, n+1):
        table[i] = i * table[i-1]

    return table[n]

 

 

- 위와 같은 문제를 DP로 해결하는 것은, memoization이나 단순 재귀로 문제를 해결하는 것보다 성능 면에서 효율적이라고 볼 수 있다. (재귀가 갖고있는 오버헤드의 문제점으로 인해)