[Algorithm/Swift] 동적계획법(DP)

 

📚

 

알고리즘 문제를 풀다가 기록해둬야 할 것 같아서

오랜만에 글 끄적끄적 📝

 

 

---

 

동적 계획법(DP; Dynamic Programming)이란 ?

큰 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법으로, 주어진 문제를 여러 개의 하위 문제로 분할하고 각 하위 문제의 결과를 저장하여 저장한 값을 이용해 상위 문제를 점진적으로 해결하는 방식을 사용한다.

 

DP는 중복되는 하위 문제들이 존재할 때 효과적으로 사용된다. 동일한 하위 문제가 여러 번 반복해서 계산되는 경우, DP는 이전에 계산한 값을 저장해 두었다가 재사용함으로써 중복 계산을 피할 수 있다. 이를 "Memoization"이라고도 부른다.

💡 메모이제이션(Memoization)은 이전에 계산한 값을 메모리에 저장하는 방식으로 중복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 최적화 기법이다.

 

정리하면, DP는 Dynamic Table이나 Memoization을 통해 중복 계산을 피하고, 하위 문제의 최적해를 구하여 전체 문제의 최적해를 도출하는 방식으로 사용된다. 대표적인 예로는 피보나치 수열, 최장 공통 부분 수열(LCS), 최단 경로 문제 등이 있다.

 

 

동적 계획법의 특성

☝🏻 최적 부분 구조 (Optimal Substructure) : 큰 문제의 최적해가 작은 문제의 최적해로부터 구해질 수 있는 성질

✌🏻 중복되는 하위 문제 (Overlapping Subproblems) : 작은 문제들이 반복적으로 발생하는 형태를 가지는 것

 

 

동적 계획법의 구현 방식

☝🏻 상향식 동적 계획법 (Bottom-up 동적 계획법)

✌🏻 하향식 동적 계획법 (Top-down 동적 계획법)

 

🤔 위 개념으로만 봤을 땐 작은 하위 문제들을 통해 상위 문제를 해결한다고 해서 상향식 기법이구나,, 라고 생각했다. 그런데 기본 개념이 하위 문제로부터 상위 문제를 해결하는 것이므로, 상향식 뿐만 아니라 하향식 기법에도 적용될 수 있었다. 잘못 생각함 ㅎㅅㅎ

 

 

상향식 동적 계획법 (Bottom-up 동적 계획법)

작은 하위 문제부터 시작하여 필요한 값을 계산하고 저장하는 방식.

작은 문제부터 큰 문제로 진행하며, 이전에 계산한 값들을 활용하여 점진적으로 최적해를 구한다. 재귀적인 호출 없이 반복문을 사용하여 계산하기 때문에 효율적인 방식임 !! 반복문을 통해 작은 연산 단위를 실행하고 그 결과를 Dynamic Table에 저장하여 사용한다. 보통 배열이나 테이블을 사용하여 계산 결과를 저장하며, 최종적으로 원하는 문제의 해를 구할 수 있다.

💡 Dynamic Table은 부분해의 결과를 임시적으로 저장하는 배열을 말한다.

 

 

하향식 동적 계획법 (Top-down 동적 계획법)

큰 문제를 작은 하위 문제로 분할하고, 재귀적으로 하위 문제를 호출하여 해결하는 방식.

이 때, Memoization을 사용하여 이전에 계산한 값을 저장하고 재사용함으로써 중복 계산을 피한다 ‼️ 재귀 호출을 사용하기 때문에 구현이 간단하고 직관적이지만, 재귀 호출에 따른 오버헤드가 있을 수 있다. 그렇기 때문에 재귀 호출을 최적화하기 위해 Memoization을 사용하는 것이 일반적.

 

💡 결론적으로, 동적 계획법은 하향식과 상향식 모두 해당될 수 있고, 두 방식은 동적 계획법의 핵심 아이디어를 활용해서 중복 계산을 피하고 최적 부분 구조를 활용하는 것에 차이가 있을 뿐임 !!! 그치만,, 처리할 데이터의 양이 많아지면 Stack의 범위를 초과한 재귀 호출로 인해 문제가 발생할 수 있다. 해결 가능한 방법은 존재하나 되도록 상향식 DP를 통해 작성하는 것이 좋다고 함 ~ ㅎ

 

개념을 익혔으니 그럼 어떻게 코드로 알고리즘을 짜는지 보자구요 !!!

아래 예시 코드는 n번째 피보나치 수열의 숫자를 출력하는 함수들입니다람쥐 🐿️ ( 주의 : 0번째가 존재함 !! )

 

 

상향식 동적 계획법으로 피보나치 수열 알고리즘 구현

func fibonacciBottomUp(_ n: Int) -> Int {
    var fibo = Array(repeating: 0, count: n + 1)
    fibo[0] = 0; fibo[1] = 1
    
    if n <= 1 { return fibo[n] }
    for i in 2...n { fibo[i] = fibo[i - 1] + fibo[i - 2] }
  
    return fibo[n]
}

print(fibonacciBottomUp(10))
// 출력 : 55
// fibo : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

 

하향식 동적 계획법으로 피보나치 수열 알고리즘 구현

var fiboMemo = [Int: Int]()

func fibonacciTopDown(_ n: Int) -> Int {
    if n <= 1 {
        fiboMemo[n] = n
        return n
    }
    if let memo = fiboMemo[n] { return memo } // 이미 계산하여 저장해두었다면 그 값을 반환 - 메모이제이션
    fiboMemo[n] = fibonacciTopDown(n - 1) + fibonacciTopDown(n - 2)

    return fiboMemo[n] ?? 0
}

print(fibonacciTopDown(10))
// 출력 : 55
// fiboMemo : [6: 8, 7: 13, 3: 2, 8: 21, 9: 34, 10: 55, 1: 1, 0: 0, 5: 5, 4: 3, 2: 1]

메모이제이션 배열의 크기를 정해두기 싫어서 딕셔너리로 구성하였음 ㅎㅅㅎ

 

 

---

 

이항계수 문제를 풀다가 DP를 적용하고자,, 공부하게 되면서 기록을 했다 😇

DP를 적용하기 위해선 최적 부분 구조 성립 확인 후에 점화식 도출이 중요한 것 같다..

DP... 너 이 자식 날 못 자게 하다니 !!! 흙흙