[딩코딩코 2025 코딩테스트 필수 알고리즘] - 19. Dynamic Programming

본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.
코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요
👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기
본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.

---

피보나치 수열

동적 계획법에 들어가기 전에 피보나치 문제를 풀어보면서 필요성을 느껴보자.

피보나치 수열이란?

수학에서, 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1,1,2,3,5,8 이다.

피보나치 수열 구현

n 번째 피보나치 수를 Fibo(n) 이라고 표현하면, Fibo(1) 은 1이고, Fibo(2) 도 1이다.

그러면 아래와 같이 표현 가능하다.

Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 = 2 Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3 Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5 Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 .....

이런 구조를 보면 재귀함수로 구현할 수 있다.

input = 20

def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)

print(fibo_recursion(input))  # 6765

만든 피보나치 함수의 input 을 100으로 바꾸면 연산이 너무 오래 걸린다.

왜냐하면 이미 시켰던 작업을 다른 곳에서 다시 새롭게 하고 있다. 이렇게 하지 않으려면, 이미 했던 일을 기록하고 있어야 한다.

---

동적 계획법

동적 계획법이란?

동적 계획법이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

즉, 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다.

피보나치 수열 - 동적 계획법 구현

구현하는 방법은 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키고, 결과를 기록하고 이용하면 된다.

용어 정리를 해보자.

• 메모이제이션(Memoization) : 결과를 기록
• 겹치는 부분 문제(Overlapping Subproblem) : 문제를 쪼갤 수 있는 구조

재귀함수를 동적 계획법의 메모이제이션이라는 방법을 통해 구현해보자.

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1),Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.

위 방법을 가지고 코드로 구현해보자.

input = 50

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}

def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo

print(fibo_dynamic_programming(input, memo))