[Kotlin] 알고리즘 - 동적 계획법(DP, Dynamic Programming)

동적 계획법(DP, Dynamic Programming)

큰 문제를 작은 문제로 나누고, 작은 문제들을 풀이하여 나온 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법

복잡한 문제를 간단한 문제들로 나누어 푸는 방법

조건

최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.

부분 반복 문제 (Overlapping Subproblem)

• 동일한 작은 문제들이 반복적으로 나온다.

핵심 기술

메모이제이션(Memoization)

• 동일한 계산을 반복해야 하는 경우, 이전에 계산한 값을 메모리(캐시)에 저장해두었다가 재사용하여 중복 계산을 제거한다.
• 메모리 공간을 사용하여 전체적인 실행 속도를 빠르게 한다.
• 결과가 필요해질 때마다 계산한다(Lazy-Evaluation).
• 피보나치 수열 계산, 최단 경로 탐색, 조합 및 순열 계산과 같은 다양한 계산 작업에 사용된다.

테뷸레이션(Tabulation)

• 작은 문제부터 풀어나가며 결과를 배열 또는 테이블에 저장하고, 저장된 값을 재활용하여 큰 문제를 풀어나간다.
• 필요하지 않은 값도 미리 계산해둔다(Eager-Evaluation).
• 최적화 문제나 최단 경로 문제와 같은 문제에서 유용하다.

하향식 접근 방식 (Top-Down)

위에서 아래로 접근하는 방법으로 메모이제이션을 사용한다.

큰 문제를 작은 문제로 나누어가며 풀어가는 방식

재귀 호출을 사용하여 결과값을 전이시켜 재활용한다. 스택 오버플로가 발생할 수 있다.

fun fibHelper(n: Int): Int {
    return fibonacci(n, IntArray(n + 1))
}

fun fibonacci(n: Int, dp: IntArray): Int {
    if (n < 2) return n
    if (dp[n] == 0) dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp)
    return dp[n]
}

상향식 접근 방식 (Bottom-Up)

아래에서 위로 접근하는 방법으로 테뷸레이션을 사용한다.

작은 문제부터 해결하여 점차 큰 문제를 풀어가는 방식

반복문을 통해 점화식으로 배열을 0부터 하나씩 값을 구해가며 저장된 값을 재활용한다.

fun fibonacci(n: Int): Int {
    val dp = IntArray(n + 2)
    dp[1] = 1
    for (i in 2..n)
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

재귀 vs 동적 계획법

동적 계획법과 재귀의 차이는 피보나치 수열 계산으로 비교해볼 수 있다.

재귀 같은 경우 동일한 작은 문제들을 반복 수행하여 계산하는데, n이 커질수록 중복 계산하는 횟수가 많아지는 단점이 있다.

/**
 * 재귀로 피보나치 수열 계산 구현
 */
fun fibonacci(n: Int): Int {
    if (n < 2) return n
    return fibonacci(n - 1) + fibonacci(n - 2)
}

재귀 호출 트리 구조

반면에 동적 계획법은 계산 결과값을 저장하여 재사용하기 때문에 중복 계산을 하지 않는다.

동적 계획법 트리 구조(호출-실선, 재사용-점선)

Reference

https://www.spiceworks.com/tech/devops/articles/what-is-dynamic-programming/

https://didu-story.tistory.com/220

https://hongjw1938.tistory.com/47

https://code-lab1.tistory.com/7

https://freedeveloper.tistory.com/276

https://goo-gy.github.io/2019-12-09-memoization

https://stackoverflow.com/questions/6469437/what-is-the-difference-between-caching-and-memoization

https://velog.io/@nninnnin7/Dynamic-programming-1

https://hyeinisfree.tistory.com/25

https://dltjrals2.github.io/algorithm/algorithm-dynamic-programming

https://www.hanbit.co.kr/media/channel/view.html?cms_code=CMS4008657032

https://devsub.tistory.com/2

https://comdoc.tistory.com/entry/33-피보나치-수열과-동적-프로그래밍

[Kotlin] 알고리즘 - 나머지 연산 분배 법칙 - Dico

모듈러 산순 분배 법칙

dico.me