DP 실수 모음

먼저 AtCoder의 문제를 보자. 가장 기본적인 피보나치 계열 문제다.

A - Frog 1 (atcoder.jp)

A - Frog 1

첫 계단부터 마지막 계단까지(높이는 단조증가하지 않음) 1칸 혹은 2칸씩 걸을 수 있을때 최소의 이동거리(변위)의 합은? 여기서 이동거리는 이동하는 계단 사이의 높이의 차(절대값)을 말한다. bottom-up 방식을 택했다.

코드 1. 맨 앞의 N은 계단의 갯수를, h는 계단의 높이들을 저장한 배열이다. 오답(WA).

N = int(input())  #4
h = list(map(int, input().split()))  #10 30 40 20
dp = [0] * N
for i in range(N):
  if i == 1:
    dp[i] = abs(h[i - 1] - h[i])
  else:
    dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]),
                dp[i - 2] + abs(h[i - 2] - h[i]))
print(dp[N - 1])

왜? 기본 값 세팅이 0으로 되어 있어서, 이동거리를 더할 경우 이보다 반드시 크게 되어, 비교가 무의미해짐.

코드 2. WA

N = int(input())  #4
h = list(map(int, input().split()))  #10 30 40 20
if N <= 1:
  print(0)
dp = [float('inf')] * N
for i in range(N):
  if i == 1:
    dp[i] = abs(h[i - 1] - h[i])
  else:
    dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]),
                dp[i - 2] + abs(h[i - 2] - h[i]))
print(dp[N - 1])

왜? dp 배열 맨 앞의 수를 0으로 세팅하는 것을 잊음. 이 위치는, 맨 처음 계단에 대한 최소비용으로, 애초에 추가적 노력 없이 이 자리에서 시작했기 때문에 0이어야 함.

코드 3. WA

N = int(input())  #4
h = list(map(int, input().split()))  #10 30 40 20
if N <= 1:
  print(0)
dp = [float('inf')] * N
dp[0] = 0
for i in range(N):
  if i == 1:
    dp[i] = abs(h[i - 1] - h[i])
  else:
    dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]),
                dp[i - 2] + abs(h[i - 2] - h[i]))
print(dp[N - 1])

왜? for문에서 0번째 자리는 다시 계산해선 안됨. 왜냐면 그 전과 비교할 필요가 없기 때문.

코드 4. AC

N = int(input())  #4
h = list(map(int, input().split()))  #10 30 40 20
if N <= 1:
  print(0)
dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
  if i == 1:
    dp[i] = abs(h[i - 1] - h[i])
  else:
    dp[i] = min(dp[i], dp[i - 1] + abs(h[i - 1] - h[i]),
                dp[i - 2] + abs(h[i - 2] - h[i]))
print(dp[N - 1])

for를 1부터 시작하게 바로잡고, 내 원래 자리에 있던 dp 값과도 비교하는 부분을 넣음. 그러나 이건 꼭 필요가 없다.

코드 5. AC

N = int(input())  #4
h = list(map(int, input().split()))  #10 30 40 20
if N <= 1:
  print(0)
dp = [float('inf')] * N
dp[0] = 0
for i in range(1, N):
  if i == 1:
    dp[i] = abs(h[i - 1] - h[i])
  else:
    dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]),
                dp[i - 2] + abs(h[i - 2] - h[i]))
print(dp[N - 1])

위에서 dp에 불필요한 비교 부분을 지움. 왜냐면 bottom-up은 DAG랑 같기 때문이다. 아래에서부터 차례로 채우기 때문에, 그 순서에 따른다면 늘 가장 최신의 값을 참조하여 뒤로 보내게 된다. 따라서 자기 자신의 값과 비교할 필요는 없다. 반면, 트리가 아니라 일반적으로 cycle이 있는 그래프의 경우에는 자기 자신의 값과 비교해 주는 로직이 필요하다. 그것을 MST에서 Relaxation 이라고 부른다.

코드 6. AC 2

# Source: https://usaco.guide/gold/intro-dp?lang=py,   error corrected

N = int(input())
# height is 1-indexed so it can match up with dp
height = [0] + [int(s) for s in input().split()]
assert N == len(height) - 1

"""
dp[N] is the minimum cost to get to the Nth stone
(we initially set all values to INF)
"""
dp = [float("inf") for _ in range(N + 1)]
# dp[1] = 0 is our base case since we're already at the first stone
dp[1] = 0

for i in range(1, N + 1):
    if i + 1 <= N:
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(height[i] - height[i + 1]))
    if i + 2 <= N:
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(height[i] - height[i + 2]))

print(dp[N])

이건 지금 나의 위치가 과거의 두 종류 계단으로부터 왔다는 가정이 아니라, 현재부터 앞으로 두 가지를 보낸다는 가정에서 작성된 코드다. 해당 목적지에 원래 있는 값과 내가 지금 위치로부터 갔을때 비용의 합과 비교하고 있다(Relax). 왜냐하면, 내가 지금 출발지에서 1칸 위, 혹은 2칸 위라는 목적지로 걸음을 보낸 다음에나 그 전에도, 다른 출발지에서 그 두 목적지로 얼마든지 걸음을 보냈을 수 있기 때문이다. 반면 코드 5 까지에서는, 내가 밟고 서있는 곳에 도달하기 위한 모든 경로를 논리적으로 따져보니 단 두 경로(1칸 전, 혹은 2칸 전에서 온) 만 고려하면 되기 때문이다.

처음에는 top-down의 재귀가 편했지만, 지금은 메모이제이션을 위한 캐시 설정을 고민하지 않아도 그저 표를 차례로 채우면 되는 bottom-up이 더 편하다고 느껴진다. 생각이 또 바뀌려나.