DP 동적 프로그래밍 설명 + 예제(타일링 문제)

하나의 문제를 한번만 풀도록하는 알고리즘

 

동적 프로그래밍은 다음의 가정 하에 사용가능합니다.

 

1번가정 -> 큰 문제를 작은 문제로 나눌 수 있다.

2번가정 -> 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

즉,  쉽ㄱ ㅔ말해 크고 어려운 문제가 있으면 그것을 잘게 나누어 해결한 후에 나중에 전체답을 구하는것

But!!

Memoization 이 사용된다는 점이 분할정복(Divide and Conquer 방법)과는 다릅니다.

이미 계산된 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야할 때는 저장된 값을 단순히 반환만 하면됨

 

#include <stdio.h>

int d(int x){
	if(x==1) return 1;
    if(x==2) return 1;
    
    return d(x-1) + d(x-2);
}

int main()
{
	printf("%d",d(10));
}

위는 잘 실행이 됩니다.

#include <stdio.h>

int d(int x){
	if(x==1) return 1;
    if(x==2) return 1;
    
    return d(x-1) + d(x-2);
}

int main()
{
	printf("%d",d(50));
}

이것은 잘 실행이 안됩니다. CPU가 계속 돌아 갈 것.

-> 이를 위해 메모이제이션 기법을 활용하자!

#include <stdio.h>

int d[100];

int fibonacci(int x){
	if(x == 1 ) return 1;
    if(x == 2 ) return 2;
    
    if(d[x]!=0)
    	return d[x];
    return d[x] = fibonacci(x-1)+fibonacci(x-2);

}



int main()
{
	printf("%d',fibonacci(30));
}

이는 이미 계산된 결과는 배열 d에 저장됨

그러므로 한번 구한 값은 다시는 구하는 일 X

---

2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.