DP Dynamic Programming 동적 계획법 알고리즘과 예제

포스팅에서 다룰 DP; Dynamic Programming 동적 계획법 알고리즘은 큰 문제를 여러 개의 작은 문제들로 나누어 푸는 방법으로 최적화 문제를 해결하고 프로그램의 전체적인 실행 속도와 성능을 향상할 수 있는 중요한 알고리즘입니다. 예제를 사용한 구현 방식까지 알아보겠습니다.

 

DP; Dynamic Programming 동적 계획법이란?

동적 계획법 Dynmic Programming 알고리즘 :

크기가 크거나 복잡한 문제를 효율적으로 풀기 위해 작거나 간단한 여러 개의 문제로 나눠서 푸는 방법으로, 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘입니다.

 

입력 크기가 작은 부분 문제들을 해결한 후에 그 해 들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘 설계 기법으로 프로그램 성능의 향상을 기대할 수 있습니다.

 

피보나치 수를 구하는 함수에 DP 알고리즘 적용하기

더 쉬운 이해를 위해 피보나치수열을 구하는 함수를 예시로 활용하여 예제를 보여드리겠습니다.

피보나치수열 알고리즘의 경우에는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있는 최적 부분 구조로 이루어져 있어 DP 알고리즘을 적용하기 좋은 예제입니다.

 

 

 

 

1. 문제를 부분 문제로 분할한다.
   • Fibonacci(0) = 0, Fibonacci(1) = 1
   • Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)  (n>=2)
2. 가장 작은 부분 문제부터 해를 구한다.
3. 부분 문제들의 해를 테이블에 저장하고 이를 이용하여 상위 문제의 해를 구한다.

인덱스	[0]	[1]	[2]	[3]	[4]	[5]	. . .	[n]
값	0	1	1	2	3	5	. . .	fibo(n)

 

메모이제이션(memoization)은 위 과정의 3번과 같이 부분 문제들의 해를 메모리에 저장하는 기법으로 동적 계획법 알고리즘에서 핵심이 되는 기술이므로 중요한 개념입니다.

아래에 메모이제이션 포스팅을 첨부하도록 할 테니 꼭 한 번 읽어보시길 바랍니다.

 

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

 

Dynamic Programming 알고리즘 구현 방식 (feat. Python)

#1 recursive 방식

함수의 호출을 이용한 재귀적 방법입니다.

재귀적 구조는 엄청난 중복 호출이 발생할 수 있으므로 내부에 시스템 호출 스택을 사용하는 overhead가 발생할 수 있습니다.

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

 

 

#2 iterative 방식

반복문을 이용한 반복적 방법입니다.

Memoization을 반복적 구조에 사용하여 DP 알고리즘을 구현하는 것이 위의 재귀적 구조에 비해 실행 속도와 성능 면에서 보다 효율적입니다.

반복문을 이용하여 작은 값부터 상위로 값을 구해 나갑니다.

def fibo2(n):
    f = [0, 1]
    for i in range(2, n + 1):
        f.append(f[i - 1] + f[i - 2])

    return f[n]

---

이번 포스팅에서는 fibonacci 수열 알고리즘을 예제로 하여 파이썬을 활용해 Dynamic Programming 알고리즘과 구현에 대하여 알아보았습니다. 메모이제이션도 동적 계획법 알고리즘의 핵심 기법이므로 꼭 알고 가시길 바랍니다.