[DP] 피보나치 수열과 예제로 알아보는 DP

* 복습 겸 기록을 위해 작성한 포스트 입니다.

 

1. DP란, 결국

완전탐색의 일종이다. 또한

점화식을 만들 수 있어야 한다.

N번째 값에 대한 어떠한 연산이 N-1 값에 대한 동일한 연산, N-2 값에 대한 동일한 연산으로 나뉠 수 있어야 한다.

어떠한 연산을 함수 f(N) 이라고 하면, f(N) = a1 * f(N-1) + a2 * f(N-2) + ... (for 임의의 상수 a1, a2,...) 형태로 표현되어야 한다.

이렇게 생각해볼 수 있는 문제들을 풀때 Dynamic Programming 기법을 사용하는 것이다.

 

 

2. DP의 조건

• 1. 참조 투명성을 가져야 한다.
• 2. 겹치는 부분 문제(연산)가 존재해야 한다.
• 3. 최적 부분 구조를 가지고 있어야 한다.

 

1번 조건인 참조 투명성은, 문제를 해결할 때 처음에 주어진 입력 외에 다른 값에 영향을 받지 않아야하는 조건이다.

보통의 Online Judge에서는 예제 입력 외에 중간에 다른 입력이 들어오지 않기 때문에, 신경쓰지 않아도 되는 조건이다.

 

2번 조건은 (메모이제이션을 통해 최적화를 할 수 있는) 겹치는 부분 문제가 존재해야 한다는 것이다.

조건인 이유? 겹치는 부분문제가 있어야 이를 최적화하여 수행시간을 줄일 수 있기 때문이다.

보통 최적화는 부분 문제에 대한 연산 값을 추가 저장공간에 저장(메모이제이션)하여 이뤄낸다.

fibo(n) = fibo(n-1) + fibo(n-2); fibo(0) = fibo(1) = 1; 인 피보나치 수열에서 f(5)를 구하면,

f(5) = f(4) + f(3) 이고, f(4)는 다시 f(3) + (2)로 전개할 수 있는데, 이를 한번에 써보면

f(5) = f(3) + f(2) + f(3) 이 된다. f(3)에 대한 연산을 두 번 진행해야 값을 구할 수 있게 되는데, 처음에 f(3)에 대한 연산을 할 때 이 값을 기억해두고 차후 f(3)의 호출이 발생되면 배열에서 값만 가져와( O(1) ) 연산에 사용하는 것이다.

 

3번 조건은, 특정 상태에서의 해가 결국 전체에서도 최적의 해임이 보장되어야 한다는 의미이다. 그리디 알고리즘을 떠올리면 된다. 모든 상태에서의 연산 조건이 똑같아야 한다는 의미이다.

 

 

그래서?

문제를 보고,

이거 완전탐색 문제인데?

근데 경우의 수가 너무 많아서 딱 봐도 시간 초과 날 거 같은데?

음... memoization을 통해 시간을 줄일 수 있을 거 같은데?

그럼 DP를 써보자.

 

사실 엄밀하게, DP는 문제 구조가 DAG형태로 되어있어야 사용할 수 있다.

어려운 DP문제는 문제 구조를 DAG형태로 전처리해야 풀리도록 만들어 둔다.

cyclic, undirected(양방향) -> DAG

 

 

 

 

3. 피보나치 수열 예제

{"fibo 1: 재귀만 사용,  fibo 2,3: DP 사용"}

 

 

3-1. 재귀만 사용했을 때 피보나치 함수의 호출 횟수

피보나치 수열의 n 번째 값을 출력하라 하면 떠올릴 수 있는 일반적인 풀이이다

 

사실, 수열의 첫 번째 원소부터 더해가는 직관이랑 정 반대에서 출발해야 해서 이해하기 쉽지 않았다.

 

그런데 이 정반대된다는 직관이 코드 이해에 정말 중요한 것 같다.

n 번째 항의 최적해를 구하기 위해서

base condition(기저 조건) ( 위 코드에선 if( n <= 1 ) return 1;) 이 쌓이고 쌓여 결국

n 번째 항의 최적해를 만들어 낸다는 믿음(직관)이 있어야 DP같은 재귀적 구조를 이해할 수 있다.

 

수학적 귀납법을 떠올리자.

 

(6번째 피보나치수열을 구해보기 위해 함수 인자로 6넣고, 5로 분할하고 4로 분할하고 이렇게 생각하지 말고

결국 내 재귀함수 조건에 의해 base condition에서의 상태값들이 5번째 값을 만들어 낸다는 믿음)

 

 

3-2. DP를 이용한(memoization 기법을 이용한) 피보나치 함수의 호출 횟수

피보나치 함수는 초기에 전달한 n 외에 다른 입력에 영향받지 않는다. 1번조건 만족

 

앞서 적었듯이, 반복되는 부분 문제가 존재한다( f(5)를 구할 때 f(3)을 두 번 구했어야 하므로 f(3)연산 두 번 중복 ). 중복되는 부분문제가 있어서 2번조건 만족

 

각 부분 함수의 덧셈 연산은 최적이고, 최종 전체 연산에서도 최적인 함수이다

f(5) = f(4) + f(3)

f(5) = f(3) + f(2) + f(2) + f(1)

f(5) = f(2) + f(1) + f(2) + f(2) + f(1), (결국 마지막도 전부 덧셈 연산)

3번 조건 만족

 

따라서 중복되는 부분을 fibo[N] 배열로 메모이제이션 하면

int fibo2(int n) {
	// 출력용
	cnt2++;

	// base condition
	if (n <= 1) return 1;

	if (fibonacci[n - 1] != -1) {
		if (fibonacci[n - 2] != -1) {
			
			// memoization
			return fibonacci[n] = fibonacci[n - 1] + fibonacci[n - 2];
		}
		else {
			// memoization
			return fibonacci[n] = fibonacci[n - 1] + fibo2(n - 2);
		}
	}
	else {
		if (fibonacci[n - 1] != -1) {
			// memoization
			return fibonacci[n] = fibonacci[n - 1] + fibonacci[n - 2];
		}
		else {
			// memoization
			return fibonacci[n] = fibo2(n - 1) + fibonacci[n - 2];
		}
	}
}

이렇게, 하위 피보나치 수열이 배열에 존재하면 그 값을 가져와서 사용하게끔 만들었다.

피보나치 수 6에 대해 연산횟수는 재귀만 사용했을 때 15에서 4로 획기적으로 줄어들게 되었다.

 

보통 DP로 문제를 풀었던 사람의 코드를 보면 위처럼 중첩 조건문이 오밀조밀하게 짜여있었는데 이제는 왜 그런지 알게 되었다. 함수를 점화식으로 표현했을 때, 나뉜 식들 각각에 대한 메모이제이션 값이 존재하는지 아닌지 확인한 후 그에 맞는 처리를 해야하기 때문이었다.

 

근데 보기에 너무 지저분하다. 레퍼런스 변수, ~ 비트연산자 + 메모이제이션 배열 초기화를 이용해 좀 더 깔끔하게 만들어보자.

 

3-3. DP 피보나치 함수 코딩 최적화

아래 코드로, 메모이제이션 할 배열을 전부 -1로 초기화한다.

-1을 unsigned integer에 저장했을 때, 32비트(4바이트) 전부 1로 채워져있는 형태를 띈다.

 

 

memset(fibonacci, -1, sizeof(fibonacci));

 

-1에 대해, ' ~ ' 비트연산을 하면, 모든 부호가 반대로 바뀌어 전부 0이 되게 된다.

이는 조건식에서 false를 의미한다. 이를 기억하고 아래를 보자.

잘 이용하면 fibonacci[n-1] == -1 코드를 ~fibonacci[n-1]로 줄여 생각할 수 있다.

 

n-1값에 대해 메모이제이션을 하면, 배열의 n-1항에 다른 값이 덮어씌워지게 된다. -1에서 변한 것이다.

-1 그상태 그대로였다면 ~fibonacci[n-1] 은 조건식 내부에서 false state이다.

그런데 값이 조금이라도 변했다면 그 값에 대한 비트에 0이 한 개 이상 들어가게 되고, ~(변한 값) 은 1을 한 개 이상 포함한 비트 형태로 표현할 수 있다.

 

비트 형태의 수는 전부 0이 아닌 이상 조건식 내부에서 true state를 가진다.

 

따라서 if(~fibonacci[n-1]) 코드는 n-1항에 메모이제이션이 되었을 때(그래서 n-1항 값이 변했을 때) 내부 body로 진입할 수 있게 하는 코드이다.

 

-----------------------------------------------------------------

메모이제이션을 위해 변수를 선언할 때, int& 형태의 레퍼런스 형 자료를 선언해서 배열 값과 연결시킨다(정확히는 그 칸의 시작하는 주소). 그러면 int& 자료를 변경하면서 return을 해주면, 메모이제이션이 되면서 함수도 return 되는 동시에 두 가지 역할을 하는 코드를 짤 수 있다.

 

 

아래 코드가 그 결과이다. 보기 좀 더 깔끔해 진 것 같다.

// fibo2 코드 줄이기, 반복되는 코드 줄이기
int fibo3(int n) {
	cnt3++;
	// 1. base condition 은 똑같음
	if (n <= 1) return 1;

	//// 2. memoization - 한 번이라도 값이 할당 되었다면(-1이 아니게 됨)
	int& n_1 = fibonacci[n - 1];
	int& n_2 = fibonacci[n - 2];
	if (~n_1) {
		if(~n_2) return n_1 + n_2;
		else {
			n_2 = fibo3(n - 2);
			return n_1 + n_2;
		}
	}
	else {
		if (n_2) {
			n_1 = fibo3(n - 1);
			return n_1 + n_2;
		}
		else {
			n_1 = fibo3(n - 1);
			n_2 = fibo3(n - 2);
			return n_1 + n_2;
		}
	}
}

 

 

4. BOJ 2240 - 자두나무

어렵다

2240번: 자두나무

 

직관적으로 생각하지 말고, 문제를 분석해보자  (나 자신에게 하는 쓴소리)

 

• 처음에 자두를 받아먹기 위해, 움직이는 선택 - 해당 항에서 최적의 선택이
  • 이후의 최적의 결과를 보장하지 않는다
    • 처음부터 그리디는 아니다
• 그래서 모든 케이스를 다 봐야 한다
  • 완전탐색을 사용해야 한다
  • 자두나무는 2가지 이므로, 자두가 떨어지는 시간 동안 각 단위시간 1에 대해 2가지 선택을 할 수 있다
    • 그러나 이런 식으로 계산할 경우 경우의 수가 최대 2^1000 까지 올라간다
      • 경우의 수가 너무 많네??
      • 어!! DP 한번 써볼까?
        • 중복되는 부분 문제가 있나?
        • (여기서부터 머리가 아팠다. 중복되는 부분 문제를 내 직관으로 찾을 수가 없었다.)
        • (그래서 그냥 받아들이기로 했다.)
        • 문제에 영향을 주는 상태값들인 나무 번호, 자두가 떨어지는 시간, 나무를 받는 위치 이렇게 총 3개의 변수를 메모이제이션 하기 위해
          • dp[ tree_Index ][ time ][place] 이렇게 3차원 자료구조를 생성하면 된다.
        • 이제 완전탐색 로직을 기반으로, 메모이제이션 기법을 응용해 케이스를 줄여나가면 된다.

 

 

Ref.

[알고리즘 강의] 7주차. DP, 동적계획법,.. : 네이버블로그 (naver.com)

[알고리즘 강의] 7주차. DP, 동적계획법, 다이나믹프로그래밍