동적계획법 - 2 x n 타일 문제

동적 계획법 풀이는 제일 먼저 점화식을 찾아라.

ex) dp[n] = dp[n-1] + dp[n-2]

 

점화식을 찾는 방법은 수기로 직접 제일 작은 입력값을 넣어보면서, 특정 패턴 및 이전 값과 기존 값의 상관 관계를 파악하면 쉽게 찾을 수 있다.

 

점화식을 찾는 과정

 

2 x n 타일 문제 풀이 순서

1. 빈 리스트 만들기 (입력값에 따른)

 

int[] dp = new int[num + 1];

 

 

2. 초기값을 설정

 

dp[1] = 1;
dp[2] = 2;

 

 

3. 점화식 기반으로 계산값 적용하기

 

for (int i = 3; i <= num; i++) {
  dp[i] = dp[i - 1] + dp[i - 2];
}

 

 

4. 특정 입력값에 따른 계산값을 리스트에서 추출하기

 

return dp[num];

 

 

< 최종 코드 >

 

동적계획법 타뷸레이션 이용

 

 

동적계획법을 구현하는 기법에는 Top-down, Bottom-up 기법이 있다.

값을 캐시(Cache)에 메모(저장) 해놓고, 다시 그 값을 계산할 필요가 없이 풀이하는 것을
메모이제이션(Memoization)이라고 한다.

 

 

Top-down(하향식 풀이)은 큰 문제를 작은 문제로 쪼개면서 해결하고, 재귀로 구현하는 것을 말한다.

Bottom-up(상향식 풀이)은 작은 문제부터 차례대로 해결하고, 반복문으로 구현하는 것을 말한다.

 

 

메모이제이션을 이용한 풀이법은 다음과 같다.

 

동적계획법 메모이제이션 기법

 

 

Top-down과 Bottom-up의 시간복잡도 차이는 문제에 따라 다를 수 있다.

 

재귀로 구현하는 Top-down 기법은 Stack Overflow가 발생할 여지가 있기 때문에, Bottom-up이 더 좋다는 말도 있다.

두 경우로 모두 해결이 가능하기 때문에, 상황에 맞게 적절하게 사용하면 될 듯하다.

 

 

일반적인 동적 계획법 문제는 통상 코드 자체는 간결하므로,

가장 적은 경우의 수부터 계산을 해본 후, 패턴을 찾아, 점화식을 세우는 것이 핵심이다.

 

 

 

틀린 부분이 있다면, 언제는 댓글 남겨주세요. 피드백 환영합니다.