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

Presentation on theme: "Dynamic Programming Donghuna Daejeon Samsung Software Membership Republic of Korea 2. Aug. 2012."— Presentation transcript:

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

2 DonghunaDynamic Programming2 Donghuna http://www.donghuna.com donghuna@hotmail.com 010.6289.0892 Korea University of Technology and Education

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

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

5 Introduction DonghunaDynamic Programming5 “What is DP???”

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

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

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

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

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

11 DonghunaDynamic Programming11 재귀 다이나믹 base

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

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

14 DonghunaDynamic Programming14

15 DonghunaDynamic Programming15

16 DonghunaDynamic Programming16

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

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

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

20 DonghunaDynamic Programming20

21 DonghunaDynamic Programming21

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

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

24 DonghunaDynamic Programming24 1 2... 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

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

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

27 DonghunaDynamic Programming27

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

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

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

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

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

33 DonghunaDynamic Programming33 과정을 보면, 1 2 3 4

34 DonghunaDynamic Programming34

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

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

37 DonghunaDynamic Programming37

38 DonghunaDynamic Programming38 큐 앤 에이