[PS] 동적 프로그래밍(DP)

Hood·2025년 1월 4일

dynamic programming ps

PS

목록 보기

12/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

동적 프로그래밍

동적 프로그래밍(Dynamic Programming, DP)은
큰 문제를 작은 문제로 나누어 해결하되,
이미 계산한 결과를 저장해 두고 다시 활용하는 방식의 알고리즘입니다.

즉, 같은 계산을 여러 번 반복하지 않도록
이전에 구한 값을 메모리 공간에 저장해 두고 필요할 때 다시 사용하는 것이 핵심입니다.

이러한 방식은 특히 중복되는 부분 문제가 존재하는 경우 매우 효과적입니다.

Memoization이란?

Memoization은 DP를 구현하는 대표적인 방법 중 하나입니다.
한 번 구한 결과를 메모리에 저장해 두고,
같은 계산이 다시 필요할 때 저장해 둔 값을 그대로 사용하는 기법입니다.

예를 들어 f(5)를 구할 때 f(4)와 f(3)이 필요하고,
다시 f(4)를 구할 때 또 f(3)이 필요하다면
같은 값을 여러 번 계산하게 됩니다.

이럴 때 한 번 구한 f(3)의 결과를 저장해 두면
다음부터는 다시 계산하지 않고 바로 가져올 수 있습니다.

DP를 구현하는 두 가지 방식

DP는 보통 다음 두 가지 방식으로 구현합니다.

1. Top-Down 방식

큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하는 방식입니다.
필요한 값만 계산하면서 내려가는 방식이며,
보통 재귀 함수 + Memoization 조합으로 구현합니다.

2. Bottom-Up 방식

가장 작은 문제부터 차례대로 값을 구해 나가는 방식입니다.
보통 반복문을 사용하여 DP 테이블을 채워 나갑니다.

즉, 정리하면 다음과 같습니다.

Top-Down: 재귀적으로 내려가며 필요한 값을 계산
Bottom-Up: 작은 값부터 차례대로 테이블 채우기

예를 들어

DP를 설명할 때 가장 자주 등장하는 예시 중 하나가 바로 피보나치 수열입니다.

피보나치 수열이란?

피보나치 수열은 앞의 두 항을 더해 다음 항을 만드는 수열입니다.

점화식으로 나타내면 다음과 같습니다.

a_n = a_{n-1} + a_{n-2} \quad (n \geq 2)

보통 피보나치 수열은 다음과 같이 시작합니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 \dots

즉,

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

로 정의할 수 있습니다.

여기서 말하는 점화식이란,
현재 항이 이전 항들과 어떤 관계를 가지는지를 나타내는 식입니다.

재귀로 구현해 보면

피보나치 수열은 재귀 함수로 매우 직관적으로 표현할 수 있습니다.

fun main() {
    print(fibo(5))
}

fun fibo(n: Int): Int {
    if (n == 0) return 0
    if (n == 1) return 1

    return fibo(n - 1) + fibo(n - 2)
}

이 코드는 정의 자체는 매우 간단합니다.
하지만 이렇게만 구현하면 비효율적인 문제가 생깁니다.

재귀 풀이의 단점

단순 재귀로 피보나치 수열을 구현하면 같은 값을 여러 번 다시 계산하게 됩니다.

예를 들어 fibo(5)를 구할 때는 fibo(4)와 fibo(3)을 호출하고,
fibo(4)는 다시 fibo(3)과 fibo(2)를 호출합니다.

즉, fibo(3) 같은 값이 여러 번 반복 계산됩니다.

이 방식의 단점은 크게 두 가지입니다.

중복 계산이 많습니다.
n이 커질수록 호출 횟수가 급격히 증가합니다.

사진 출처

이러한 단순 재귀 방식은 시간 복잡도가 대략

O(2^n)

수준으로 증가하게 됩니다.
그래서 n이 커지면 매우 비효율적입니다.

DP로 바꿔 풀어보면?

이런 비효율을 줄이기 위해 DP를 사용할 수 있습니다.
이미 계산한 값을 저장해 두고 다시 사용하는 방식으로 중복 계산을 없앨 수 있기 때문입니다.

가장 간단한 방법은 DP 테이블을 만들어 작은 값부터 차례대로 채우는 것입니다.

fun main() {
    val dp = IntArray(6)

    dp[0] = 0
    dp[1] = 1

    for (i in 2..5) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    print(dp[5])
}

위 코드는 dp[i]에 i번째 피보나치 수를 저장합니다.

즉,

dp[0] = 0
dp[1] = 1
dp[2] = dp[1] + dp[0]
dp[3] = dp[2] + dp[1]

처럼 작은 문제부터 차례대로 값을 채워 나갑니다.

이 코드가 의미하는 것

DP는 중간 계산 결과를 테이블에 저장해 두기 때문에
같은 값을 다시 계산하지 않아도 됩니다.

따라서 단순 재귀에서 반복되던 중복 호출이 사라지고,
전체 시간 복잡도는

O(n)

으로 줄어듭니다.

여기서 중요한 점은,
위 예시는 Top-Down 방식이 아니라 Bottom-Up 방식이라는 것입니다.

왜냐하면 재귀 호출로 필요한 문제를 내려가며 계산한 것이 아니라,
반복문을 이용해 작은 값부터 차례대로 채워 나갔기 때문입니다.

또한 엄밀히 말하면 이 코드는 Memoization보다는
Tabulation(테이블 채우기) 방식에 더 가깝습니다.

정리하면 다음과 같습니다.

재귀 + 저장 → Top-Down + Memoization
반복문 + 테이블 채우기 → Bottom-Up + Tabulation

DP는 언제 사용할까?

DP는 보통 다음과 같은 특징이 보일 때 시도해 볼 수 있습니다.

큰 문제가 작은 문제로 나누어질 수 있는 경우
같은 부분 문제가 여러 번 반복되는 경우
작은 문제의 답으로 큰 문제를 만들 수 있는 경우

특히 점화식을 세울 수 있는 문제라면
DP로 접근할 수 있는 가능성이 높습니다.

예를 들어,

피보나치 수열
계단 오르기
1로 만들기
최장 증가 부분 수열
배낭 문제

등이 대표적인 DP 문제입니다.

📌 결론

동적 프로그래밍은
이미 계산한 값을 저장해 두고 다시 활용하여
중복 계산을 줄이는 알고리즘입니다.

정리해 보면 다음과 같습니다.

DP는 큰 문제를 작은 문제로 나누어 해결합니다.
이미 구한 값을 저장해 중복 계산을 막습니다.
Memoization은 저장한 값을 다시 사용하는 방식입니다.
구현 방식은 Top-Down과 Bottom-Up으로 나눌 수 있습니다.
피보나치 수열처럼 같은 계산이 반복되는 문제에서 매우 효과적입니다.

DP는 처음 접하면 어렵게 느껴질 수 있지만,
핵심은 결국 “같은 계산을 여러 번 하지 않도록 하자”는 아이디어입니다.
따라서 문제를 보았을 때 점화식을 세울 수 있는지,
그리고 이전 결과를 재사용할 수 있는지를 먼저 떠올려 보는 것이 중요합니다.

Hood

달을 향해 쏴라, 빗나가도 별이 될 테니 👊

이전 포스트

[PS] Greedy (탐욕법)

다음 포스트