[알고리즘 공부] 다이나믹 프로그램

다이나믹 프로그래밍 (Dynamic Programming)

 

 이번에는 다이나믹 프로그래밍에 대해서 알아보도록 하겠습니다. 최적의 해를 구하기에 시간이 매우 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로 해결하기 어려운 문제입니다. 연산 속도의 한계와 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시키 때문입니다. 따라서 연산 속도 및 메모리를 최대한 활용할 수 있도록 알고리즘을 작성해야 하는 데, 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가 시킬 때, 사용하는 방식이 다이나믹 프로그래밍입니다. 

 

 이번 글에서는 다이나믹 프로그래밍의 고전적인 예제 중 하나인 '피보나치 수열'을 계산하는 코드를 통해서 살펴보도록 하겠습니다. 먼저, 피보나치 수열에서 n 번째 숫자는 n-1 번째와 n-2 숫자의 합입니다. 피보나치 수열의 첫 두 숫자는 보통 0과 1로 정의합니다. 즉 F(0) = 0, F(1) = 1이며, 그 이후의 숫자는 F(n) = F(n-1) + F(n-2)로 계산됩니다. 

 

 하지만 피보나치 수열의 점화식은 재귀 함수를 사용해 만들 수 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 계산할 수 없습니다. 이러한 문제는 다이나믹 프로그래밍을 사용하여 해결할 수 있지만 아래와 같은 조건을 만족할 때 사용할 수 있습니다. 

 

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

 그럼 피보나치 수열을 풀기 위해 다이나믹 프로그래밍에서 사용하는 두 방식을 소개하도록 하겠습니다. 

 

1. 탑다운 방식 : 재귀 호출과 메모이제이션(Memoization) 기법을 사용
2. 보텀업 방식 : 반복문과 결과를 저장할 때 배열(또는 리스트 사용) 

 두 방식 모두 동일한 결과를 제공하지만 탑다운 방식은 코드가 직관적이고 이해하기 쉬운 반면, 큰 입력 값에 대해서는 스택 오버플로우를 일으킬 수 있습니다. 그리고 보텀업 방식은 전체 결과를 저장해야 하므로 메모리 사용량이 더 클 수 있습니다. 

 

 아래 코드를 통해서 각 방식으로 피보나치 수열을 푼 과정을 살펴보겠습니다. 

 

# Top-Down

# 메모이제이션을 위한 딕셔너리 초기화
memo = {}

# 탑다운 다이나믹 프로그래밍을 이용한 피보나치 수 계산
def fibonacci_top_down(n):
    # 이미 계산된 값이면 메모에서 반환
    if n in memo:
        return memo[n]
    # 피보나치 기본 케이스
    if n <= 2:
        return 1
    # 재귀적으로 결과 계산 및 메모에 저장
    memo[n] = fibonacci_top_down(n - 1) + fibonacci_top_down(n - 2)
    return memo[n]

# 예제 사용
print(fibonacci_top_down(10))  # 55 출력

 

 

# Bottom-Up

# 보텀업 다이나믹 프로그래밍을 이용한 피보나치 수 계산
def fibonacci_bottom_up(n):
    # 첫 두 피보나치 수는 1
    if n <= 2:
        return 1
    fib_table = [0] * (n + 1)  # 결과 저장을 위한 테이블 초기화
    fib_table[1], fib_table[2] = 1, 1  # 초기값 설정
    for i in range(3, n + 1):
        fib_table[i] = fib_table[i - 1] + fib_table[i - 2]
    return fib_table[n]

# 예제 사용
print(fibonacci_bottom_up(10))  # 55 출력

---

마무리

 이번에도 아주 간단하게 다이나믹 프로그래밍 예제를 살펴보았습니다. 얼른 빨리 한 바퀴를 돌리고 후딱 많은 문제들을 풀어보면 좋겠지만 기초라는 것은 확실히 잡고가야하는 문제이기 때문에 오늘 하루도 인내하고 또 인내하면서 견뎌봅니다. 물론 기초를 모두 알고 있다고해서 모든 문제를 풀 수 있는 것은 아니지만, 적어도 어려운 유형의 문제를 만났을 때 어떤 알고리즘을 이용하여 풀 수 있는 지 정도는 알고 싶습니다. 하나씩 쌓여가는 코딩 테스트 글들을 보면서 조금만 참아보자라는 마인드로 견뎌내봅니다. 그럼, 이번 글은 여기서 마치도록 하겠습니다. 

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬