망할놈의 알고리즘 - DP편(0) : 개요

Ref : Introduction to ALGORITHMS, Third Edition, Thomas H. Cormen

※ 해당 게시글을 이해하기 위해서는 자료구조에 대한 기초적인 지식과 적당한 Python/CPP 능력이 필요합니다.

---

Dynamic Programming(이하 통칭 DP라 함)은 분할 정복 마냥 문제를 나눠서 푸는게 핵심입니다. 단지 분할 정복이랑 다른 점이 있다면 - 나눈 문제들이 답을 서로 공유한다는 점이죠. 그러니까 대충 정리하자면....

 

• DP는 Sub-Problem을 한번 풀과 결과를 데이터 테이블에 저장해 놓습니다.
• 결과적으로 해당 Sub-Problem을 다시 만났을 때 - 계산을 다시 할 필요가 없어집니다.

대표적인 DP의 사용례 : 피보나치 수

call fib(6)
  └─ fib(5)
      └─ fib(4)
          └─ fib(3)
              └─ fib(2)  -> base
              └─ fib(1)  -> base
            => memo[3] = 2   (저장!)
          └─ fib(2) -> base
        => memo[4] = 3       (저장!)
      └─ fib(3) -> memo HIT! (재귀 안 탐)
    => memo[5] = 5           (저장!)
  └─ fib(4) -> memo HIT!     (재귀 안 탐)
=> memo[6] = 8               (저장!)

 

위의 의사 코드를 보면 이해가 쉬울 겁니다. 피보나치를 일일이 계산하면 스택 지옥에 빠지겠지만.. 계산해 뒀을 때 캐시에 저장해 뒀다면 그냥 가져와서 쓰면 그만입니다. 이런식으로 "재활용"을 강조하는 측면이 바로 DP라고 생각하면 될 것 같습니다.

 

참고로 DP의 경우 일반적으로 최적화 문제들에 사용되고, 아래와 같은 단계를 밟습니다.

 

1. 최적해 구조의 특징을 잡아내기
2. 재귀(Recursive)적으로 최적해를 정의하기
3. 최적해를 계산하기, 대부분 Buttom-up의 경우로.
4. 계산된 결과를 바탕으로 최적해를 잡아내기.

여기까지만 보면 참 쉬워보입니다. 문제는 1차원 DP가 아니라 2차원 DP (문자열, 격자, LCS...)로 가면 머리가 조금 아파집니다. 나중에는 선택/비선택을 결정하는 DP도 나옵니다! 행렬 곱셈을 할때 DP를 쓰는건 덤입니다.....

 

DS는 A+맞아도 AL은 못하겠습니다 솔직히

 

해서 조만간 올라올 글에는 DP에 관한 푸념과 한탄과 코드가 잔뜩 올라올 예정입니다. 솔직히 공부 해도 GPT쨩이 더 잘하는데 (ㅠㅠ) 뭔 의미가 있나 싶지만 그래도 나름 개발자라는 놈이 공부를 해야되지 않겠습니까.