[알고리즘] 다이나믹 프로그래밍(Dynamic Programming)

 

출처: unsplash.com

 

다이나믹 프로그래밍(동적 계획법)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

 

알고리즘 설계 기법:

문제 해결을 위해 알고리즘을 설계하는 방법이나 접근 방식을 뜻한다.
설계 기법은 알고리즘을 개발하고 구현하는 데 사용되는 전략과 원칙을 뜻한다.

 

DP와 재귀 호출의 차이점

DP와 재귀 호출의 차이점을 알기 전에 하향식 접근법과 상향식 접근법이 무엇인지 알아야 한다.

1. 하향식(top-down) 접근법과 상향식(bottom-top) 접근법

하향식 접근 방식은 큰 문제를 작은 하위 문제로 쪼개서 해결하는 방법이다. 주로 재귀 호출을 할 때 사용된다.
상향식 접근 방식은 작은 문제들부터 시작해 작은 문제들의 결과를 이용해 점점 큰 문제의 결과를 구하는 방법.

 

2. 메모이제이션(Memoization)

메모이제이션은 중복되는 계산 결과를 저장하는 메모리 기법인 메모이제이션을 사용한다. 이를 통해 이전의 계산값을 저장하고 필요에 따라 해당 값을 불러와 재사용한다. 이 방법은 중복 계산을 방지하고 계산 속도를 향상시킬 수 있다.

 

결론

다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용한다.
그래서 DP가 아닌 기억하며 풀기라고 불리기도 한다.

 

 

DP를 왜 써야 할까?

사실 DP는 재귀 호출과 매우 유사하다. 하지만 두 방법의 큰 차이점은 이전에 생성된 데이터를 재활용하느냐 못하느냐의 차이이다.

단순 재귀는 이전의 데이터를 재활용하지 못하기 때문에 큰 문제를 구하기 위한 작은 문제가 여러 번 반복되어서 비효율적인 계산이 될 수 있다.

 

예를 들어 피보나치 수열을 구하고자 한다. 재귀로 작성하려면 다음과 같이 작성할 수 있다.

언어: Kotlin

private fun fibonacci(num: Int): Int {
    if (num == 2 || num == 1) {
        resursive++
        return 1
    } else return fibonacci(num - 1) + fibonacci(num - 2)
}

num을 5라고 가정하고 재귀 함수를 호출한다.

그러면 처음에 5를 받아와 4+3을 더하게 된다. 그리고 4를 받아온 함수에서 3+2를, 3을 받아온 함수에서 2+1을 하게 되는데 이전의 데이터를 재사용하지 못해 똑같은 값을 다시 구하는 모습이다.

피보나치 수열 재귀 호출 트리

같은 색의 데이터를 보면 데이터를 1번 구했는데도 재사용하지 못하고 데이터를 생성하는 모습이다.

num - 1에서 구한 값을 num - 2를 해 다시 구하게 되는 과정을 반복한다.

만약 num이 5가 아니라 100이라고 하면 함수의 호출 횟수는 기하급수적으로 증가하게 된다.

 

한편 작은 문제의 결과를 저장해 두고 재사용하면 어떻게 될까? 앞에서 계산한 데이터를 그대로 가져와 재활용하기 때문에 다시 반복할 필요 없이 5번째 피보나치 수를 구할 수 있다.

 

불필요한 데이터 호출 없이 3번의 반복만으로 5번째 피보나치 수열 데이터를 알아낼 수 있다.

 

 

언제 DP를 써야 할까?

DP를 사용하기 위해서는 2가지의 조건을 만족해야 한다.

1. 중복되는 부분 문제

DP는 기본적으로 큰 문제를 작은 문제로 나누고 작은 문제 값을 재활용해 큰 문제의 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

 

2. 최적 부분 구조

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용이 가능하다.

예를 들어 A와 B 정거장의 최단 경로를 구하고자 한다 A, B 정거장 사이에는 X 정거장이 있다.

A -> X로의 최단 경로가 AX2이고, X -> B의 최단 경로가 BX2일 때, A -> B의 최단 경로는 AX2 - BX2이다. 다른 경로를 사용한다고 해서 절대로 최단 경로는 변하지 않는다.

 

위에서 예시로 들었던 피보나치 수열도 이전의 계산 값(부분 문제의 결과)을 통해 답(전체 문제의 결과)을 구할 수 있기 때문에 최적 부분 구조 만족으로 DP로 풀 수 있다.

 

 

DP로 문제 해결하기

DP는 특정한 경우에만 사용하는 알고리즘이 아니라 하나의 방법론이기 때문에 다양한 문제해결에 쓰일 수 있다. 그래서 DP를 적용할 수 있는 문제인지 알아내는 것부터 코드로 구현하는 과정까지 난이도가 쉬운 것부터 어려운 것까지 다양하다.

일반적으로 DP를 사용하기 전에 다음과 같은 과정이 존재한다.

 

1. DP로 풀 수 있는 문제인지 확인(DP 사용 조건 확인)
2. 문제의 변수 파악
3. 변수 간의 관계식 만들기
4. 메모하기(변수의 값에 따른 결과를 저장)
5. 기저 상태 파악하기(가장 작은 문제의 상태 파악)
6. 구현하기

 

구현 방법

1. Bottom-up(반복문 사용)

작은 문제부터 차례대로 해결하여 전체 문제를 해결하는 방식이다.

이를 위해 반복문을 사용해 부분 문제들을 해결하고 결과를 배열에 저장한다.

일반적으로 더 직관적이고 이해하기 쉽다. 또한 모든 작은 부분 문제를 해결하므로 최적 부분 구조를 보장한다.

2. Top-down(재귀 사용)

큰 문제를 작은 부분의 문제로 나누어 해결하는 방식이다.

이를 위해 재귀 함수를 사용해 문제를 작은 부분으로 쪼개고, 중복 계산을 피하기 위해 이전에 계산한 값을 저장하는 메모이제이션(Memoization)을 활용한다.

재귀 호출은 구현이 더 간단할 수 있다. 또한 필요한 부분 문제만 해결하므로 계산 시간을 절약할 수 있다.
하지만 재귀 호출 오버헤드가 발생할 수 있으며, 모든 작은 부분 호출에 대한 문제를 해결하지 않을 경우 최적 부분 구조를 보장하지 못한다.

 

 

DP 문제 풀어보기

풀어볼 문제는 알고리즘 수업 - 피보나치 수 1이다.

https://www.acmicpc.net/problem/24416

 

문제의 요구사항

 

피보나치 수열을 구하는 데 재귀 호출이 있고 반복문 사용 방법이 있을 때, 사진의 2개의 코드에서 코드 1(2)라고 주석 쳐져 있는 부분이 몇 번 실행됐는지 확인해서 출력한다.

 

DP로 풀 수 있는 문제인지 확인한다.

1. DP로 풀 수 있는 문제인가?
   => 피보나치 수열은 대표적인 최적 부분 구조 만족으로 DP로 해결 가능하다.
2. 문제의 변수 파악
   => 위 문제의 변수는 n번째 피보나치 데이터를 나타내는 n이다.
3. 변수 간 관계식 만들기
   => 하위의 데이터들을 이용해 상위의 데이터를 만들기 위한 관계식은 f(n) = f(n-1) + f(n-2)이다.
4. 메모하기
   => 반복문을 이용해 피보나치 수를 구할 때 list에 이전에 해결한 문제(값)를 저장하고 그것을 재사용한다.
5. 기저 상태 파악
   => 피보나치 수의 가장 작은 문제의 상태는 피보나치 수의 0번째, 1번째 데이터인 1, 1이다.
6. 구현하기
   => 다음과 같이 코드로 구현할 수 있다.

(스포 주의) 언어: Kotlin

import java.util.Scanner

private var resursive = 0   // 재귀 함수 카운트
private var loop = 0        // 반복문 카운트
fun main() = with(Scanner(System.`in`)) {
    val number = nextInt()

    fibonacci(number)   // 재귀 호출

    // 반복문
    val fibonacciList = mutableListOf(1, 1)
    for (i in 3 .. number) {
        fibonacciList.add(fibonacciList[i-2] + fibonacciList[i-3])
        loop++
    }

    println("$resursive $loop")
}

private fun fibonacci(num: Int): Int {
    if (num == 2 || num == 1) {
        resursive++
        return 1
    } else return fibonacci(num - 1) + fibonacci(num - 2)
}

반복문 코드를 보면 fibonacciList에 작은 데이터(n-1, n-2 번째 값의 합)를 집어넣어 메모하기를 잘 준수했다.

구현은 반복문(bottom-up)과 재귀(top-down) 방식 모두를 사용했다.

 

 

정리

다이나믹 프로그래밍에 대해 자세히 공부할 수 있는 기회였다.

다이나믹 프로그래밍 방법에 대해 알게 되었으니 이제는 문제를 풀면서 손에 익히는 과정만 남았다.

DP의 과정을 알게 되었다.

 

참고한 블로그

https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적계획법(Dynamic Programming)

https://hongjw1938.tistory.com/47

알고리즘 - Dynamic Programming(동적 계획법)