[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming, DP)

• 최적화 이론의 한 기술이며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘 설계 기법입니다.
• 동적 계획법을 사용하여 중복되는 계산을 피하면서 효율적으로 문제를 해결할 수 있습니다.

 

사용 조건

1. 중복 부분 문제 구조(Overlapping Subproblems)
   
   • DP는 기본적으로 문제를 작게 나누고 그 결과 값을 재활용해서 전체 답을 구합니다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능합니다.
2. 최적 부분 문제 구조(Optimal Substructure)
   • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 나타낼 수 있는 경우를 의미합니다.

 

구현 방법

1. Bottom-Up

• 작은 문제들을 풀고, 작은 문제들의 답을 이용해 큰 문제를 푸는 방법을 반복해 최종 문제를 해결합니다.
• 아래부터 하나하나씩 채우는 과정을 table-filling 이라 하며, 이 Talbe이 저장된 값에 직접 접근하여 재활용하므로 Tabulation 이라고도 불립니다.
• 주로 반복문을 사용해 구현합니다.

# 동적 계획법 Bottom up을 이용한 피보나치 수열
def fibonacci_bottomup(n):
    if n <= 1:
        return n
    # 초기값 설정
    memo = [0, 1]
    for i in range(2, n+1):
        # 이전 두 값을 더해서 현재 값을 구함
        current = memo[i-1] + memo[i-2]
        # memo 리스트에 현재 값을 추가함
        memo.append(current)
    # 결과값 반환
    return memo[n]

 

2. Top-Down

• 위에서부터 바로 호출을 시작하여 결과 값을 재귀를 통해 전이시켜 재활용하는 방식입니다.
• 이미 이전에 계산을 완료한 경우에는 단순히 메모리에 저장되어 있는 내역을 꺼내서 활용하는 방식으로, Memorization 이라고 불립니다.
• 주로 재귀 함수를 사용하여 구현합니다.

# 동적 계획법 Top down을 이용한 피보나치 수열
def fibonacci(n, memo):
    # 이미 계산한 값이 있으면 그 값을 반환
    if memo[n] is not None:
        return memo[n]
    # n이 0이거나 1일 경우 값을 반환
    if n <= 1:
        memo[n] = n
    else:
        # 이전 두 값을 더해서 현재 값을 구하고 memo에 저장
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

def fibonacci_topdown(n):
    # memo 리스트 초기화
    memo = [None] * (n+1)
    return fibonacci(n, memo)

 

피보나치 수열을 구현한 코드에 40이 주어졌을 때 실행시간

• DP를 사용하지 않은 경우 : 약 27초
• DP를 사용한 경우 : 약 0.0002초

 

 

분할 정복 vs 동적 계획법

공통점

• 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다.

차이점

• 분할정복 : 하위 문제가 동일하게 중복이 일어나지 않은 경우에 사용한다.
• 동적 프로그래밍 : 하위 문제가 동일한 중복이 일어나는 경우에 사용한다.