Dynamic Programming Donghuna Daejeon Samsung Software Membership Republic of Korea 2. Aug. 2012

DonghunaDynamic Programming2 Donghuna Korea University of Technology and Education

Dynamic Programming3Donghuna “ 아는 만큼 보인다.”

DonghunaDynamic Programming4 Introduction 계단 오르기 거스름돈 문제 Subset 숫자 삼각형 문제 1 문제 2 Outline

Introduction DonghunaDynamic Programming5 “What is DP???”

DonghunaDynamic Programming6 Introduction 1, 2, 3, 4, ….. 이를 식으로 정의 하는 방법 두가지 1. 일반항으로 2. 귀납적으로

DonghunaDynamic Programming7 일반항 귀납적 (base) (memoization)

DonghunaDynamic Programming8 귀납적으로 정의 된 경우 에는 수열이 복잡하더라도 명확하게 나타낼 수 있음 장점 귀납적으로 정의된 경우 Divide and conquer 나 Dynamic programming 으로 구현 가능

DonghunaDynamic Programming9 Divide and conquer 와 Dynamic programming 의 차이점은 ? Divide and conquer 는 쪼개진 부분의 값을 가지고 있지 않다. Dynamic programming 은 쪼개진 부분의 값을 기억해 낸다.

DonghunaDynamic Programming10 재귀 다이나믹 답 ( 재귀함수 ) 베이스 답 ( 점화식 ) 베이스

DonghunaDynamic Programming11 재귀 다이나믹 base

DonghunaDynamic Programming12 물 좋고 정자 좋은 곳은 없다. 속도는 월등히 빠르지만 태초에 메모리를 많이 사용한다는 단점이 있음.

DonghunaDynamic Programming13 계단을 올라갈 때 한번에 한칸 올라가는 방법과 두칸 올라가는 방법이 있다고 가정한 다. 그럼 3 번째 칸에 올라가는 가능한 가지 수는 아래와 같이 3 가지가 있다. 한칸 + 한칸 + 한칸 두칸 + 한칸 한칸 + 두칸 그럼 7 번째 칸에 올라가는 가능한 가지 수는 ? ( 힌트 : 작은 것부터 해결하라 ) 계단 오르기

DonghunaDynamic Programming14

DonghunaDynamic Programming15

DonghunaDynamic Programming16

DonghunaDynamic Programming17 동전의 종류가 1, 5, 10 원 일 때, 동전의 종류가 1, 7, 9 원 일 떄 자판기에서 거스름돈 21 원을 최소 동전 개수로 거슬러 주는 방법 첫 번째 경우에선 액수가 큰 동전부터 10 원 2 개와 1 원 1 개를 주면 된다 두 번째 경우에서 액수가 큰 동전부터 주면 9 원 2 개와 1 원 3 개를 주게 된다. 하지만 답은 7 원 3 개를 줘야 한다. 왜 이런 차이가 나는가 ? 거스름돈 문제

DonghunaDynamic Programming18 동전의 액수 크기대로 정렬했을 때 인접한 두 동전의 액수가 배수가 될 때는 액 수가 큰 동전부터 거슬러주면 된다. 예를 들면 1, 5, 10, 30, 60 하지만 1, 7, 9 에서는 7 과 9 사이에 배수 관계가 아니므로 9 원을 먼저 거슬러 주 는 게 최적의 답이 아닐 수 있다.

DonghunaDynamic Programming19 거스름돈 n 을 최소 동전 개수로 거슬러 주는 문제를 쪼개보자. 점화식을 세워보자

DonghunaDynamic Programming20

DonghunaDynamic Programming21

DonghunaDynamic Programming22 ‘ 거스름돈 문제 ’ 는 ‘ 계단 오르기 문제 ’ 와 근본적으로 같다. 원래 ‘ 거스름돈 문제 ’ 는 동전 종류가 1, 7, 9 원 일 떄 자판기에서 거스름돈 21 원을 최소 동전 개수로 거슬러 주는 방법. 이것을 ‘ 계단 오르기 문제 ’ 로 바꿔보면, 한번에 ‘ 한칸 ’, ‘ 일곱칸 ’, ‘ 아홉칸 ’ 올라가는 방법이 있을 때, 21 번째 칸에 최소한의 계단을 밟고 올라가는 방법

DonghunaDynamic Programming23 “ 주어진 문제가 공식에 적용되는 문제인가 ?” 를 알아내기 어렵다. 쪼개서 작은 것부터 해결. 점화식을 만들면 풀 수 있다.

DonghunaDynamic Programming N 에서 합이 같은 두 집합으로 나누는게 문 제이다. N 이 3 인 경우 다음과 같은 한 가지 방법 이 존재하고 1 2, 3 N 이 7 이면, 4 가지 방법이 있다. 1,6,7 and 2,3,4,5 2,5,7 and 1,3,4,6 3,4,7 and 1,2,5,6 1,2,4,7 and 3,5,6 N 이 주어질 때 합이 같은 두 집합으로 만들 수 있 는 방법의 수를 구하는게 문제이다. 제한 시간은 1 초이다. 입력형식 정수 N( 1 <= N <= 39) 이 입력된다. 출력형식 만들 수 있는 방법의 수를 출력한다. 만들 수 있는 방법이 없으면 0 을 출력한다. 입출력 예 입력 7 출력 4 출처 :usaco Subset

DonghunaDynamic Programming25 ( 예시 ) A = { 1, 2, 3} 집합 A 의 부분 집합 중 원소 3 을 포함하는 부분 집합은 어떻게 구할 수 있을까 요 ? 답 ) A = {1, 2} 의 부분 집합 {} 1 2 1,2 에서 각각에 3 을 더한 4 개가 됩니다. {} ,2 + 3 이 와 같은 방법으로 확장이 이루어 집니다.

DonghunaDynamic Programming26 시작 상태 원소 2 가 적용된 상태 원소 1 이 적용된 상태 반복 적용되는 것을 막기 위해 뒤에서 앞으로 검사 원소 3 을 적용하는 과정

DonghunaDynamic Programming27

탐욕알고리즘 DonghunaDynamic Programming28 은 이제 그만

DonghunaDynamic Programming29 숫자 삼각형이 존재할 때 꼭대기 (top) 에서 아래 (bottom) 로 내려올 때 합이 가장 큰 값을 구하는 게 문제이다. 단, 대각선 오른쪽 혹은 왼쪽으로 갈수 있다 로 내려오는 게 30 으로 가장 큰 합이다 입력 입력의 첫 줄은 층의 수 R (1 <= R <= 1000) 이 주어진다. 다음 줄 부 터는 각 층에 해당 하는 숫자가 주어진다. 각 숫자는 100 보다 크지 않는 양의 정수이다. 출력 오른쪽, 왼쪽 아래 대각선으로 이동하면서 제일 아래층에 도달 할 때 의 합을 출력한다. 입출력 예 입력 출력 30 출처 :ioi 기출 숫자 삼각형

DonghunaDynamic Programming30 0. 그리디로 접근 예를 들어 숫자 삼각형이 아래와 같다면 현재 갈수 있는 곳에서 최선을 택하면 (greedy method) (2+5+3=10) 해서 10 하지만 이 방법은 정답이 아니고 (2+4+5=11) 가 정답입니다.

DonghunaDynamic Programming31 1. top-down 풀이 top-down 방식은 확장 방식을 위에서 아래로 확장해 나가는 방식 입니다. 확장 방식은 step1. 제일 위층만 있는 경우 그냥 2 입니다. step2. 밑에 층을 포함하는 경우 5 는 2 에서, 4 도 2 에서 올수 있는 방법 밖에 없 으므로 7, 7 입니다. step3. 밑에 층을 포함하는 경우 답은 제일 아래층에서의 최대 값 입니다.

DonghunaDynamic Programming32 2. bottom up 풀이 위층에서 아래 층으로 내려올 때는 2 에서 5 를 선택해야 할지, 4 를 선택해야할 지를 결정할 수 없습니다. 하지만 밑에서 위로 접근하면 결정적으로 선택할 수 있습니다.

DonghunaDynamic Programming33 과정을 보면,

DonghunaDynamic Programming34

DonghunaDynamic Programming35 N * N 크기의 맵이 있다. 이 맵에는 미네랄이 군데군데 매장되어 있어서 당신은 SCV 를 이용해 이 미네랄을 채취하려고 한 다. SCV 는 (1,1) 의 위치에서 출발하여 (N,N) 까지 이동하는데, 이 SCV 는 고물이라 오른쪽 또는 아래쪽으로 밖에 움직이지 못 한다. 이 SCV 는 무한한 양의 미네랄을 가지고 있을 수 있다고 가정하자. 이 SCV 를 이용해서 최대한 많이 미네랄을 얻도 록 하는 프로그램을 작성하시오. 입력 방법 첫 줄에는 맵의 크기 N ( 3 <= N <= 100) 이 주어진다. 둘째줄부터는 주어진 지도가 N 줄 만큼 입력된다. ( 단, 0 은 미네랄 없음, 1 은 미네랄 있음을 의미한다.) 출력 방법 SCV 가 채취할 수 있는 최대 미네랄 양을 출력한다. 입출력 예 입력 출력 6 문제 1.

DonghunaDynamic Programming36 1 로 채워진 2*2 이상의 정사각형 수를 찾는 것이 문제이다. 중복이 가능한다. 예를 들어, 크기가 3 인 행열에서 *2 이상인 인 행열의 개수는 2*2 행열 2 개뿐이다. 입력 입력의 첫째 줄은 주어진 정방행렬의 크기 N (2 <= N <= 250) 이 주어진다. 다음 N 줄에는 각 N 개의 0 혹은 1 이 주어진다. 출력 가장 작은 정사각형 부터 정렬해서 출력한다. 각 줄당 첫번째 수 는 정사각형의 크기이고 다음 줄은 개수이다. 만약 존재하는 정사각형이 없으면 0 을 출력한다. 입출력 예 입력 출력 출처 : usaco 문제 2.

DonghunaDynamic Programming37

DonghunaDynamic Programming38 큐 앤 에이