알고리즘/개념

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

XZXXZX 2021. 6. 6. 19:59
728x90
반응형

컴퓨터의 연산 속도에 한계가 있으며 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다. 이러한 점은 많은 제약을 발생시킨다. 그래서 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

 

메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.

대표적인 방법은 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)기법이다. 

 

다이나믹 프로그래밍에는 2가지 방식이 있다.

  • 탑다운 방식
  • 보텀업 방식

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다.

피보나치 수열

피보나치 수열에서는 첫 번쨰 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있다.

  • n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수
  • 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1

이 점화식을 따라서 피보나치 수를 구하는 소스코드를 구현하면 다음과 같다.

# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현
def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

print(fibo(4)) # 4번째 피보나치 수

하지만 이렇게 피보나치 수열의 소스코드를 작성하게 될 경우 x의 크기가 커지면 커질수록 수행시간이 기하 급수적으로 늘어나게 된다. 동일한 함수가 지속적으로 실행되게 되어 반복호출 되는 수가 증가하기 떄문이다.

이러한 문제를 해결하기 위해서 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 다만 항상 다이나믹 프로그래밍을 사용할 수 는 없으며, 조건을 만족할 때 사용할 수 있다.

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열은 이러한 조건을 만족하는 대표적인 사례이다. 메모이제이션(Memoization) 기법을 사용하면 효과적으로 소스코드를 구현할 수 있다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 한다.

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 떄 1을 반환)
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적이 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

print(fibo(99)) # 99번째 피보나치수 프린트

위의 소스코드는 메모이제이션을 이용하여 이미 구한 피보나치수를 다시 구하지 않고 결과값을 가져와 주는 코드이다.

이 처럼 재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down)방식이라고 말한다. 반면에 단순히 반목문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(Bottom-Up)방식이라고 말한다.

 

탑다운(메모이제이션) 방식은 '하향식'이라고도 하며, 보텀업 방식은 '상향식'이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블'이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다. 

 

※ 참고

다이나믹 프로그래밍을 위해 자주 사용되는 기법으로는 메모이제이션 기법이 있다.

 

다이나믹 프로그래밍과 동적 할당의 다이나믹은 같은 것인가?

- 프로그래밍에서의 다이나믹은 '프로그램이 실행되는 도중에'라는 의미이다. 예를 들어 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램 실행 중에 프로그램 실행에 필요한 메모리를 할당하는 기법이다.

다이나믹 프로그래밍에서의 '다이나믹'은 이런 의미가 아니다.

 

728x90
반응형