DP (Dynamic Programming)

오늘 쓸 주제는 DP, 즉 동적 계획법 이다.

공부하기전에 여러 글을 읽었었는데, 초보자가 제일 감을 잡기 어렵다고 했고, 감을 잡는데 시간도 오래걸린다고 했다. 실제로 이 글을 쓰는 지금 현재 나도 아직 감을 잡는중이고 그만큼 어려운 알고리즘인것 같다. 하지만 코딩테스트에 자주 출제되고 피해갈 수 없는 부분이다보니, 열심히 해야겠다!

 

• DP

동적 계획법은 두가지 조건을 만족해야 풀 수 있다.

1. Overlapping Subproblem : 겹치는 작은 부분 문제

큰문제와 작은 문제를 같은 방법으로 풀 수 있다. && 문제를 작은 문제로 쪼갤 수 있다.

2. Optimal Substructure : 최적의 부분구조

문제의 정답을 작은 문제의 정답에서 구할 수 있다.

 

예로 피보나치 수를 들어보겠다.

0,1,1,2,3,5,8,13,21....

피보나치 수는 재귀함수를 사용하여 쉽게 구현 할 수있다. 평소에 알던 재귀함수를 사용하면 문제가 생긴다. 예를들어, 5번째 피보나치 수를 구하라고 한다면, fibo(5)는 fibo(3) 과 fibo(4) 를 호출한다. 또, fibo(3) 은  fibo(1), fibo(2) 를, fibo(4) 는 fibo(2),fibo(3) 을 호출한다. 벌써 이거만 봐도 fibo(2)가 두번이나 호출 되었다. 이렇게 호출 될 때마다 매번 계산을 진행 한다면 이는 굉장한 낭비라고 할 수 있다.

이를 해결하기 위해 등장한 방법이 DP, 동적 계획법이다. 이미 계산했던 것은 특정 공간에 넣어두고 필요할때 꺼내서 쓰는 방식으로 구성되어 있다. 

 

• 메모이제이션(memoization)

위에서 말했던 방법이다. 이미 계산된 것은 특정 공간(주로 배열) 에 넣어두고 필요할때마다 꺼내서 쓰는 것이다. 메모한다는 것이 어원인거 같다. 나는 주로 배열을 사용한다. 물론 vector도 쓸 수 있다. 하지만 아직까지는 나는 배열에 더 익숙하기 때문에 배열을 애용했다.

 

메모이제이션을 사용해서 위의 예시였던 피보나치 수를 구현해보겠다.

int fibo(int n){
  if(n<=1)
    return n;
  else if(n>1){
    if(dp[n]!=0)
      return dp[n];
    dp[n]=dp[n-1]+dp[n-2];
    return dp[n];
  }
}

dp는 메모이제이션에 사용한 배열이다. 위처럼 dp에 저장된 값이 있다면(dp[n]!=0 ) 그 값을 리턴해줌으로써 그 값을 사용한다. 재귀를 이용하는 방식은 주로 top-down 방식이라고 한다. 

위와 다르게 반복문을 사용하는 방식은 bottom-up 이라고 부르고 코드는 다음과 같다.

int fibo(int n){
  dp[0]=0;
  dp[1]=1;
  for(int i=2;i<=n;i++){
    dp[i]=dp[i-2]+dp[i-1];
  }
  return dp[n];
}

나는 아직 재귀함수에 익숙치 않은 탓에 bottom-up 인 반복문을 많이 활용 했다.

 

• 점화식

동적 계획법에서 점화식은 매우 중요한 부분이다. 점화식을 구하여 문제를 풀어야 하기 때문이다.

보통 문제를 읽어보고, 구하고자 하는 값을 dp배열에 넣고 점화식을 작성한 후, 이를 코드로 그대로 구현한다.

 

• 팁 아닌 팁

여러 문제를 풀면서 느낀점이 있다.

첫째, 일단 종이에 뭐든 써보자!

종이에 뭐든 써보면서 점화식을 구하려고 노력해보자. 실제로 대부분의 문제를 풀 때, 손으로 직접 쓰면서 점화식을 구하고자 노력했고 그렇게 하지 않으면 잘 풀리지 않았다.

 

둘째, 마지막을 잘 보자!

dp문제는 작은 문제로 쪼개지는 게 특징이기 때문에, 마지막 단계를 이행 하지 않았을때를 기준으로 점화식을 세울 수 있는 경우가 매우많다. 마지막 단계를 집중해서 보자.