다이나믹 프로그래밍(동적계획법, Dynamic Programming) 을 이용한 도미노문제 해결방법

소개글

다이나믹 프로그래밍(동적계획법, Dynamic Programming) 을 이용하여 1*n, 2*1, 크기의 도미노들을 이용하여 1*n, 2*n, 3*n 형태의 공간(지도) 를 채우는 도미노 유형 문제들의 해결방법과 실행이 가능한 프로그램 소스가 포함되어 있고, 해결방법을 설명하는 리포트 입니다.
다이나믹 프로그래밍에 대해 공부하시는 분들, KOI, ACM-ICPC 및 정보경시대회를 준비하는 분들께 매우 유익한 리포트가 될 것입니다.

목차

1. 동적 프로그래밍
1.1 동적 프로그래밍의 정의
1.2 동적 프로그래밍의 성질

2. 동적계획법의 적용 예 - 도미노 쌓기 문제
2.1 Simple Tiling
2.2 Normal Tiling
2.3 Tiling
2.4 Tile Code
2.5 Tri Tiling

3. 결론

4. 참고문헌

본문내용

동적계획(動的計劃, 혹은 동적 프로그래밍, dynamic programming)은 어떤 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때, 이 알고리즘의 실행시간을 줄이는 방법이다. 수학자인 리처드 벨만이 1953년에 동적계획이라는 용어를 만들었다.
동적 계획법 혹은 동적 프로그래밍 (Dynamic Programming, 다이내믹 프로그래밍) 은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 말한다. 동적 프로그래밍의 아주 쉬운 예로 피보나치 수 구하기를 들 수 있다.
피보나치 수는 다음과 같이 정의된다.
f(n) = f(n-1)+f(n-2)
f(1) = f(2)＝１
즉, n 의 피보나치 수는 n-1 의 피보나치수와 n-2 의 피보나치 수를 포함하고 있다.
... (중략)...

앞선 정의에서 살펴본, 동적프로그래밍의 성질을 정의하자면 다음과 같다.
- 최적 부분구조(Optimal Sunstructure) 를 이룬다.
- 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생하는 문제의 경우 동적 프로그래밍을 적용하기 적합하다.
동적 프로그래밍을 구하는 방법은 탑다운(Top-Down) 방식과 바텀업(Bottom-up) 방식의 두 가지 방법이 있다. 피보나치 수 구하기의 예를 들어 보자. 만약 f(n)부터 f(1) 까지 위에서 아래로 계산을 해 나갈 때 Top-Down 이 되며, f(1)부터 시작하여 f(n) 까지 피보나치 수를 구해 나갈 경우 Bottom-up 이 된다.
2. 동적계획법의 적용 예 - 도미노 쌓기 문제
이제 동적계획법을 이용하여 풀 수 있는 실제 문제들에 대해서 살펴보기로 하자. 쉬운 문제부터 어려운 문제까지, 정보 올림피아드 및 대학생 프로그래밍 경시대회 수준의 문제들을 하나씩 살펴본다.

참고 자료

- 쉽게 배우는 알고리즘 (관계 중심의 사고법)
문영로 저, 한빛미디어