Dynamic Programming이 하는 일은? 경로의 최대점수만 찾기. 주사위 보드게임(3/3)
DP에 대해 다음 글에서 이어집니다. https://blog.naver.com/devramyun/223997836254
[20250906] Dynamic Programming이 하는 일은? 도달경로에서 최대점수가 되는 경우만 찾기. 주사위 보드게임(2/2) 너무 오래 잡고 있는데 안풀렸어서 gpt에 물었더니 gpt가 좋은 문제라고 해서 이렇게 남깁니다. 아래는 만… 너무 오래 잡고 있는데 안풀렸어서 gpt에 물었더니 gpt가 좋은 문제라고 해서 이렇게 남깁니다. 아래는 만…
다음 문제는 너무 오래 잡고 있는데 안풀렸어서 gpt에 물었더니 gpt가 좋은 문제라고 해서 이렇게 남깁니다.
아래는 만들다 그만둔 풀이.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
'''
(0~N-1)N개의 연속 네모들로 이뤄진 보드게임
배열A(크기N)에는 각 네모에 적힌 숫자가 있음.
게임 중에 해당 네모는 마킹됨.
게임시작:
0 위치에 pebble. 그리고 0위치만 마킹됨.
게임목표:
pebble을 N-1네모(끝)에 도달시키는 것.
각 턴:
6면 주사위 던짐. K=1~6.
K만큼 pebble을 이동시킴. (단, 갈 수 있다면)
위치 I = I + K
만약 다음 도달 위치가 범위를 넘어가면 못 가므로
주사위을 다시 던짐. 잘 던져질때까지..
pebble이 도달한 곳은 마킹함.
결국 마지막 턴을 거치면 N-1 위치에 있게 되는 것.
게임의 결과:
sum(모든 마킹된 위치의 숫자)
solution(A):
주어진 A에 대해서 게임을 했을 때 얻는 결과의 최대값을 구하는 로직.
방법: 모든 게임을 하는 경우의 수에 대해서 결과값들을 계산하고 가장 큰 결과값을 반환하면 됨.
예:
A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2
엣지케이스:
최소N=2 -> 예 [0,0]
'''
def solution(A):
# A가 board
skillset = {1, 2, 3, 4, 5, 6}
# 재귀적으로 진행하므로 바텀업 dp테이블
# 각 N개의 위치에 가장 최대점수를 가지고 도달했을 때의 점수
dp:list[int] = [A[0]] + [None]*(len(A)) # N개 + 1
print(dp)
# dp테이블 완성하기
for i in range(0, len(dp)): # 0부터 N-1 까지.
# 한 턴
for k in skillset:
# print(k)
# 가능한 이동이면 이동.
if i+k <= len(dp)-1: # 끝지점 N-1 까지
# print(i)
i = i + k
# print(k)
# print(i)
# print(dp[i])
# dp테이블에 점수기록, 단, 이미 있는 것보다 클 경우만 기록
if dp[i] is None or dp[i] < dp[i-k] + A[i]:
# print(dp[i-k])
dp[i] = dp[i-k]+A[i]
print(i, dp[i])
else:
pass
# 끝지점에서의 값
print(dp[-1])
# i = i + k
pass
1
2
3
4
5
6
7
8
9
10
11
def solution(A):
N = len(A)
dp = [-10**9] * N # 아주 작은 수로 초기화 (음수 방지용)
dp[0] = A[0]
for i in range(1, N):
# 직전 6칸 중 최댓값을 찾아서 현재 칸에 더함
dp[i] = max(dp[max(0, i-6):i]) + A[i]
return dp[-1]
1
2
3
A = [1, -2, 0, 9, -1, -2]
print(solution(A)) # 8
쉽게 안 풀렸던 이유가, 처음에 점화식을 잘못 세웠습니다. 바로 이전에 목표점에 도달하는 경로의 경우의 수 문제를 풀었어서, 이번에도 그럴 줄 알았는데요. 풀다가 뭔가 이상해서 조금씩 수정하면서 Max 점화식 쪽으로 구현이 되고는 있었는데 확신이 없었어서, 명확하게 점화식이 다른 문제라는 걸 알고 시작하는 편이 좋았을 것 같습니다.ㅎㅎ
개구리점프 경로 문제: https://codility.com/media/train/15-DynamicProgramming.pdf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def frog_ways(S, k):
"""
S: 점프 가능 거리 집합 (예: [1,2])
k: 목표 위치
return: k까지 도달하는 모든 경우의 수
"""
dp = [0] * (k+1)
dp[0] = 1 # 시작점: 1가지 방법
for j in range(1, k+1):
for s in S:
if j - s >= 0:
dp[j] += dp[j-s] # Σ (경우의 수는 다 더함)
return dp[k]
보드게임 최대점수 문제: https://app.codility.com/programmers/lessons/17-dynamic_programming/number_solitaire/
NumberSolitaire coding task - Learn to Code - Codility AVAILABLE LESSONS: Lesson 1 Iterations Lesson 2 Arrays Lesson 3 Time Complexity Lesson 4 Counting Elements Lesson 5 Prefix Sums Lesson 6 Sorting Lesson 7 Stacks and Queues Lesson 8 Leader Lesson 9 Maximum slice problem Lesson 10 Prime and composite numbers Lesson 11 Sieve of Eratosthenes Lesson 12 E… AVAILABLE LESSONS: Lesson 1 Iterations Lesson 2 Arrays Lesson 3 Time Complexity Lesson 4 Counting Elements Lesson 5 Prefix Sums Lesson 6 Sorting Lesson 7 Stacks and Queues Lesson 8 Leader Lesson 9 Maximum slice problem Lesson 10 Prime and composite numbers Lesson 11 Sieve of Eratosthenes Lesson 12 E…
개구리점프 문제 느낌으로 최대점수 문제도 풀면 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def dice_game(A):
"""
A: 보드 점수 배열
return: 끝까지 도달했을 때의 최대 점수
"""
N = len(A)
dp = [-10**9] * N
dp[0] = A[0]
jumps = [1,2,3,4,5,6]
for j in range(1, N):
best_prev = max(dp[j-s] for s in jumps if j-s >= 0)
dp[j] = best_prev + A[j] # max (최댓값만 선택)
return dp[-1]
알고리즘 공부
#DP, #다이나믹프로그래밍, #탑다운, #바텀업, #메모이제이션, #DP테이블채우기, #피보나치, #점화식, #재귀, #재귀함수, #알고리즘, #주사위보드게임, #최대점수