Dynamic Programming (4)

금화 모으기

start에서 exit까지 이동하려 한다. 오른쪽이나 위쪽 방향으로만 이동할 수 있을 때, 모을 수 있는 금화의 최대 개수를 구하는 문제

다 따져볼 수도 있지만 그러면 오래 걸린다.

부분 문제

(i, j)번째 칸에 도착하려면 (i-1, j)나 (i, j-1)에서 오기 때문이다. 최단거리로 이동한다 가정했으므로 (i-1, j)나 (i, j-1)에서 오는 경우가 겹치지 않는다. 그래서 따로 구한 후 max로 더 큰 값을 택하면 된다.

동전 거스름돈

• N원의 거스름돈을 돌려줄 때, 동전의 개수가 최소가 되도록 거스름돈을 돌려주는 방법을 구하는 문제
• 동전의 종류에는 1원, 4원, 6원이 있음

예를 들어 8원을 거슬러 준다고 하자.

먼저 greedy하게 접근해, 가장 큰 단위의 동전을 먼저 사용한다고 해보자. 그럼 6원, 1원, 1원으로 거슬러 주므로 동전의 개수는 3이다.

그러나 실제로는 4원짜리 동전 두 개로도 거스름돈을 줄 수 있으므로 , 그리디 방법으로는 정답을 구하기 어렵다는 것을 알 수 있다. 그럼 이제 DP로 해결해보자.

Recursion (Top-down)

세 가지 동전 각각을 택해 재귀적으로 해결할 수 있다.

1원짜리 동전 한 개 + 7원에 대한 최적해
4원짜리 동전 한 개 + 4원에 대한 최적해
6원짜리 동전 한 개 + 2원에 대한 최적해

7원에 대한 최적해는 다시 1, 4, 6원짜리 동전을 선택하고 나머지 액수에 대한 최적해를 구함

풀 수 있지만 중복 계산을 너무 많이 하게 된다. Avoid re-computing solutions for these subproblems!

DP Approach (Bottom-up)

• 1원에 대한 최적해 → (선택) 2원에 대한 최적해 → (선택) 3원에 대한 최적해 → (선택) 4원에 대한 최적해 → (선택) …
• C[j]: j원을 거슬러 줄 때의 최적해

프리랜서의 일정 정하기

전에 백준에서 끙끙대면서 푼 회의 문제 프리랜서에게 10일간의 작업에 대한 요청이 있고, 하나의 작업을 하는 동안 다른 작업은 할 수 없다고 할 때, 주어진 일정에서 수당의 합이 가장 크도록 작업을 선택하는 문제

Greedy하게 푼다면 수당이 제일 많은 T3을 선택해야 하지만 , T3이 다른 모든 일정과 겹치기 때문에 다른 일정을 선택할 수가 없다. 하지만 T1+T7을 선택하면 더 많은 수당을 받을 수 있다.

Job들을 끝나는 순서대로 보자. 끝나는 시각마다 그때까지의 최대 금액을 계산하는 것이다.

위의 예시에서는 t=3일 때의 최대 금액은 15, t=4는 20, t=5일 때는 30이다.

t=6일 때는 T9가 끝나므로 여러 가지 케이스가 생기는데, 어떻게 하면 좋을까?

• 신청 작업이 1개일 경우 무조건 선택
• 신청 작업이 2개일 경우
  • 겹친다면 더 많은 돈을 지불하는 직업을,
  • 겹치지 않는다면 두 작업을 모두 선택

부분 문제

각 작업이 마치는 시간을 key로 하여 전체 작업을 다시 정렬하고 순서대로 번호를 붙임. 즉, 전체 작업 중 j번째로 미치는 작업임

OPT(j): 1부터 j까지의 작업에 대한 최적의 해

• OPT가 작업 j를 선택하지 않는 경우: OPT(j) = OPT(j-1)
• OPT가 작업 j를 선택함: OPT(j) = w(j) + OPT(p(j))
  • p(j)는 작업 j와 겹치지 않고 p(j) < j인 작업들 가운데 맨 마지막 작업
  • W(j는 작업 j를 수행했을 때 받은 돈 액수
• OPT(j) = max { OPT(j-1), w(j) + OPT(p(j)) }

집합에서 k개 선택하기

N개의 원소로 구성된 집합 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}에서 서로 다른 k개를 순서 없이 선택하는 방법의 수를 구하는 문제

DP

• 만약 답이 존재한다면 그 답은 경우들로 나눠지는지 생각해보자,
• 크기 4의 부분집합 {a, b, c, d}이 있다면 그것은 두 가지로 나눠볼 수 있다.
  • a를 포함하는 것
  • a를 포함하지 않는 것

n’(<n)에서 서로 다른 k’(k<n)개를 선택하는 부분 집합들의 개수를 구하는 문제들에 대해 답을 알고 있다고 하자. 그러면 n개에서 선택한 크기 k개의 부분 집합은 두 가지 경우에 속한다.

• case 1: a를 포함하는 부분집합들
  • a를 제외한 n-1개에서 k-1개를 선택한 부분집합들에 a를 추가
• case 2: a를 포함하지 않는 부분집합들
  • a를 제외한 n-1개에서 k개를 선택한 부분 집합들

전체 답은 case 1 + case 2 –> C(n, k) = C(n-1, k-1) + C(n, n-k)

이항계수 구하는 공식: nCk = n! / (k! (n-k)!)

그러나 n!이나 k!은 계산량이 많기 때문에 실제로 C(n, k) = C(n-1, k-1) + C(n, n-k)은 다음과 같이 계산한다.

C(n, k) = 
C(n-1, k-1) + C(n-1, k) (0 < k < n)
or
1 (if k == 0 or k == n)

완전 정보 게임 (NIM Game)

• 완전 정보 게임
  • 게임의 정보가 참가자 모두에게 공개된 게임
  • 숨어있는 정보가 없음
  • 누가 먼저 하느냐에 따라 승부가 이미 결정되어 있음
  • 바둑, 오목, 체스 등
• 불완전 정보 게임
  • 정보가 확률적으로 주어짐
  • 모든 정보가 공개되어 있지는 않음
  • 화투, 포커, 스포츠 베팅 등

바둑돌 가져가기 (1)

바둑돌이 K개 있다. 두 사람이 번갈아가면 자신의 차례에 1개, 2개의 돌을 가져갈 수 있다. 자신의 차례에 동작을 할 ㅜ없으면 그 사람이 진다. 이기는 방법이 있는 사람과 그 사람이 이기는 방법을 구하시오.

부분 문제

D(i): 돌의 개수가 i개일 때 상대방이 어떤 수를 써도 이기는 방법이 있는 경우 W(win)으로, 그렇지 않은 경우는 L(lose)

0을 받으면 이길 방법이 없으므로 lose이다. 돌의 개수가 1인 경우, 내가 그 돌을 가져가 버리면 상대방은 돌의 개수가 0이므로 진다. 따라서 돌이 하나인 경우는 W이다. 2에서 하나를 가져가면 상대방이 이길 수도 있지만, 둘 다 가져가면 상대방이 절대 이길 수 없기 떄문에 내가 이긴다.

i==3일 때는, 내가 하나를 가져가도 상대방이 W이고 내가 두 개를 가져가도 상대방이 W이므로 나는 L이다.
즉, i-1, i-2가 모두 W이면 자신은 L이다.

이런 식으로 9회까지 진행한 결과는 아래와 같다. | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |–|–|–|–|–|–|–|–|–|–| | L | W | W | L | W | W | L | W | W | L |

–> 3의 배수에서만 L임을 알 수 있다.

바둑돌 가져가기 (2)

바둑돌이 K개 있다. 두 사람이 번갈아가며 자신의 차례에 1개, 3개, 4개의 돌을 가져갈 수 있다. 자신의 차례에 동작을 할 수 없으면 그 사람이 진다. 이기는 방법이 있는 사람과 그 사람이 이기는 방법을 구하시오.

부분문제

D(i): 돌의 개수가 i개일 때 상대방이 어떤 수를 써도 이기는 방법이 있는 경우 W(win)으로, 그렇지 않은 경우는 L(lose)

바둑돌 가져가기 (3)

바둑돌이 K개 있다. 두 사람이 번갈아가며 자신의 차례에 1개, 3개, 4개의 돌을 가져갈 수 있다. 단, 앞사람이 가져간 개수의 돌은 가져갈 수 없다(따라하기 금지). 자신의 차례에 동작을 할 수 없으면 그 사람이 진다. 이기는 방법이 있는 사람과 그 사람이 이기는 방법을 구하시오.

-1: 직전에 한 칸 내려온 경우. 따라하기 금지니까 -3일 때 세 칸 이동한 값이랑 -5에서 다섯 칸 이동한 값 중 L이 하나라도 있으면 W, 모두 W인 경우 L이다.

바둑돌 가져가기 (4)

바둑돌이 K개 있다. 두 사람이 번갈아가며 자신의 차례에 (1, 1), (3, 2), (2, 0)개의 (흰돌, 검은돌)을 가져갈 수 있다. 자신의 차례에 동작을 할 수 없으면 그 사람이 진다. 이기는 방법이 있는 사람과 그 사람이 이기는 방법을 구하시오.