[DP] Dynamic Programming 알고리즘 알아보기

 

오늘은 거두절미하고, DP(Dynamic Programming) 알고리즘에 대해서 알아보고자 한다.

여기서 설명하는 DP 알고리즘은 동적 할당과는 다른 개념이므로, 착각하지 말자

동적할당은 메모리 공간에 동적으로 (런타임에) 변수 공간을 할당한다는 개념이며,

동적이라는 것 자체가 프로그램이 실행되는 런타임에 발생한다는 것을 이해하면 된다.

 

DP 알고리즘을 설명할 때 주로 피보나치 수열을 예시로 들곤 한다.

피보나치 수열은 특정 점화식으로 반복되는 수열을 의미한다.

점화식은 아래와 같다.

 

F(n) = F(n-1) + F(n-2), 단 F(0) = 0, F(1) = 1

 

이러한 피보나치 수열을 코드로 구현한다면 어떨까?

 

# 재귀를 사용한 피보나치 수열 구현
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

 

코드는 매우 간단하게 구현할 수 있다.

 

하지만, 만약 피보나치 수열의 1000번째 숫자를 알아내고자 한다면, 

위 코드로는 얼마나 걸릴까?

 

해당 코드는 O(2^n)이라는 시간복잡도를 갖고 있다.

따라서 현 컴퓨터 구조로는 우리의 수명이 다할 때까지도 계산을 마칠 수 없을 것이다.

 

이러한 경우에 사용되는게 DP 알고리즘이다.

DP알고리즘을 적용할 수 있는 문제의 특징을 2가지가 있다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제로 구한 정답은 그것을 포함하는 큰 문제에서도 정답이 달라지지 않는다.

 

피보나치 수열이 위 조건을 만족하는 대표적인 문제이다.

이 문제를 Memoization(메모이제이션) 기법을 활용하여 해결해보자.

(메모이제이션 기법은 저장한 정보를 그대로 가져와서 사용한다는 점에서 caching 이라고도 불린다.)

 

# 메모이제이션을 사용한 피보나치 수열 구현 (Top-Down 방식)
memo = {}

def fibonacci_memo(n):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
    return memo[n]

 

위 코드로 수행하면 O(N)의 시간복잡도로 문제를 빠르게 해결할 수 있음을 알 수있다.

이렇게 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어서

문제를 효육적으로 해결하는 알고리즘 기법이다.

 

여기서 추가적으로 재귀함수 방식으로 DP를 구현하게 된다면, 

컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 오버헤드가 발생할 수 있다.

 

따라서 재귀함수 대신에 반복문으로 구현하게 된다면 오버헤드를 줄일 수 있다.

 

## 반복문으로 구현한 피보나치 ##

# 반복문을 사용한 피보나치 수열 구현 (Bottom-Up 방식)
def fibonacci_iterative(n):
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

 

이 방식은 스택 오버헤드를 피할 수 있으며, 같은 시간복잡도 O(n)으로 문제를 해결할 수 있다.

이처럼 동적 계획법에는 두 가지 접근 방식이 있다:

• Top-Down 방식: 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하는 방식. 메모이제이션을 통해 중복 계산을 줄인다.
• Bottom-Up 방식: 작은 문제부터 시작해 차례로 답을 쌓아올려 큰 문제를 해결하는 방식. 반복문을 사용해 구현한다.

동적 계획법은 큰 문제를 작게 나누고,

작은 문제를 한 번만 풀어 중복 계산을 방지함으로써 효율적으로 문제를 해결하는 알고리즘 기법이다.

 

다음 번에는 DP를 적용할 수 있는 더 다양한 문제와 그 해결 방법에 대해 살펴보자.