당신은 알고 있는가 자료구조 삼대장 에 대해서...

왼쪽부터 Dynamic programming, DFS(깊이 우선 탐색), Backtracking

제 마음대로 정한 삼대장입니다. 오해 없길 바랍니다.

daily 자료구조 공부를 하는 도중에 위에서 등장했던 삼대장 중 하나가 등장했다..
Dynamic programming, (오이 그놈은 우리들 중 최약체라구!)

youtube 강의 코드 없는 프로그래밍을 보면서 공부를 하고 있었지만 이 자료구조의 목적과 원리에 대한 이야기 부족한 채로 수학 공식 쓰듯이 쓰다보니 막연하게 '아 어렵다, 어떻게 이렇게 생각하지' 라는 생각만 하고 끝내버리게 된 듯 해서 Dynamic programming이 무엇인지 정리하기 위한 글이다.

잘못된 정보에 대한 피드백은 언제나 댓글로 환영입니다!

멋들어진 이름에 가려진 원리

다이나믹 프로그래밍~ 이라는 이름에서 이 자료구조가 어떤 원리를 가지고 계산을 하는지 유추하기란 어렵다. 유추가 어려운게 당연한게 다이나믹 프로그래밍이라는 뜻은 아무~~ 관련 없기 때문이다.

그럼 다이나믹프로그램은 몬데.. 라는 생각으로 다이나믹프로그램을 공부해본 결과 내가 내린 결론은 다이나믹프로그램의 이름은 다이나믹 프로그램보다는 1)기억하며 풀기 라는 이름이 더 어울릴 것 같다.

내가 DP를 풀면서 생각했던 두 가지 키워드는, SubProblem(문제 쪼개기) , Memoization(기억해두기) 이다.


2)

피보나치 수열 예시

피보나치 수열은 1, 1, 2, 3, 5, 8 ... 으로 f(n) = f(n-1) + f(n-2) 의 점화식을 만족하는 수열을 뜻한다. 여기서 점화식을 이용해서 SubProblem(문제 쪼개기) 를 할수 있다.

fib(0) = 1
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) when n > 1

f 라는 함수가 재귀 함수라고 생각을 하면 f(2) 를 구하기위해서는 f(0) 과 f(1) 의 return 값을 이용하면 되는 것이고 계산한 값을 이용해서 f(3) = f(2) + f(1) 역시 계산할 수 있게 된다.

하지만 우리의 기억하며 풀기 방법은 여기서 그치면 굉장히 비효율적이게 된다.


2)

위의 사진에서 처럼 fib(5)를 풀기위해 재귀적 방법으로 풀게되면 fib(1) 함수를 5번이나 부르게된다. 그렇기 때문에 핵심적인 방법이 다른 곳에 fib(1)의 해답을 기억해놓고 다시 계산을 하지않고 그 답을 가져다 쓰는 것이다.

subProblem 의 답을 기억해놔야하기때문에 대부분 dp는 배열에 답을 저장해 두고 빼서 쓴다.

top-down 과 bottom-up

여기서 부터는 방법론에 대한 설명이다.

top-down

구현 부분에서 가장 헷갈렸던 부분이 top-down 부분이다.

const fib_dp = (n) => {
  if(n>2){
    fib_dp(n-1) + fib_dp(n-2)
  }else{
   return 1 
  }
}

top-down 을 구현하다보면 메모리제이션이 핵심이라는 것을 망각하고 재귀를 구현하는데 너무 힘쓰다 보니 중복 계산을 또 하는 실수를 범하기 쉬웠다. (시간복잡도가 엄청나졌다..)

그렇기 때문에 top-down 방법에서도 중요한건 기억하면서 푸는 것이고 top-down 에서 저장해두는건 함수 자체를 저장해두는 것이다.


예를 들어 fib(5) = fib(4) + fib(3) 부터 아래로 쭉쭉 내려간다면 fib(4) + fib(3) 자체를 arr[5] 에 저장해두면 나중에 fib(1) 이 호출되고 전부 계산이 될것이다.

const fib_array = [0,1];
const fib_dp = (n) => {
if (n < fib_array.length) return fib_array[n]
else {
   const fib = fib_dp(n-1) + fib_dp(n-2)
   fib_array.push(fib)
   return fib
}
}

bottom-up

말그대로 바닥에서 올라오는 것이다. 작은 문제부터 시작해서 작은 문제를 점점 쌓아 큰 문제를 푸는 것이다. fib(1) + fib(0) = fib(2) 를 계산해서 fib(2)를 db 배열에 저장하고 답이 db array 에 저장된 subProblem 이라면 그대로 가져와서 fib(3) = db[2] + db[1] 로 계산하는 것이다.

숫자를 저장하는 공간이 계속 필요한 대신 O(n)의 시간 복잡도로 구할 수 있다.

const fib_dp_bottom = (n) => {
    if (n===0) return 0;
    else if(n===1)return 1;
    let fib_array = [0,1];
     for(let i =2; i<n+1; i++){
        fib_array.push(fib_array[i-1] + fib_array[i-2])
     }
     return fib_array[n]
    }

정리

• Dynamic programming 은 Problem 을 subproblem 으로 나누고 subproblem 을 저장하여 중복 계산이 발생하지 않도록 하는 자료구조 방법이다.

• 사실, 코딩테스트 문제에서 쓸 수 있을지는 모르겠다. 진짜 리얼 수학문제처럼 문제 마다 점화식(SubProblem) 으로 나누는 아이디어 자체가 다양해서 생각해내기 어렵다. 똑똑한사람들만 쓰는 자료구조라는 말도 있다. 단순한 문제들로 여러번 경험하다보면 노하우가 생길지도 모른다.

1) 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 번역한 말이다.
2) 출처 : <파이썬 알고리즘 인터뷰>