DP (2) Knapsack 응용

#DP #Knapsack #DynamicProgramming #개발자의도구들

​

​

• 사용된 언어: 코틀린, 혹은 파이썬
• 순서: 로직, 코드 구현, 코드 분석

DP를 꿰뚫어 보기

BOJ (1149, RGB 거리 57%)

문제 출처: https://www.acmicpc.net/problem/1149

​

• Knapsack 알고리즘은 빠른 시일내에 정리할 예정.
• 하지만, 이번 문제를 통해 깨달은게 너무 많음

​

​

DP는 매우 당혹스럽다. DP 풀이를 보면 아~ 그렇구나 하는데, 풀이에 해당하는 점화식을 어떻게 유도했는지 경이로울 지경이다. DP를 깊게 공부하다보면 문제를 보는 관점이 확장된다. DFS/BFS의 완전 탐색없이 관점을 바꿔 메모리로 깔끔하게 풀수 있는게 DP의 큰 매력이지 싶다.

​

​

이번 문제는 매우 유명한 문제다. 그래서 그런지 정답율이 높다. 유명한 만큼 풀이법이 고정되어 있다. 풀이법을 암기하는 것도 중요하지만, 엔지니어라면 왜 그런 풀이법이 만들어졌는가를 고민하는게 좀 더 중요하다.

🔍 탐구하기

해당 문제는 Coloring Problem으로 매우 잘 알려져있다. 나는 학교 알고리즘 시간에 해당 문제를 접했는데, 당시에는 back-tracking으로 설명해주셔서, DP 생각은 전혀 못했다.

원본 이미지 확인 필요: 이미지

https://www.researchgate.net/figure/An-example-of-graph-coloring-problem\_fig2\_325808704

​

문제를 보고 접근법을 조금만 고민해보면, 누구나 back-tracking이라는 것을 알 수 있다. 이를 간단하게 트리로 그리면 이렇게도 표현이 가능하다.

​

그래프를 절 보면 모든 문제는 큰 문제의 부분으로 나눌 수 있다는 것을 알 수 있다. 맨 위의 빨간 세모는 첫 번째가 Red인 경우, 왼편의 파랑 세모는 첫 번째가 Green인 경우이다. 전체 큰 문제는 각 부분 문제를 합한 결과가 될 것이다.

​

​

또한 각 노드에서의 최솟값은 이전 상태의 결과에서 업데이트가 되어야한다. A가 R인 경우 96이 최적이 된다. 이렇게 각 노드별로 최솟값을 모두 추적할 수 있도록 구성해주면 어떨까?

                                    🚀 바로 이 부분에서 DP의 hint를 얻을 수 있다.

🤔 트리를 가로로 생각하기 (원시 상태)

​

첫번째로 생각했던 것은 모든 상태의 수를 표로 펴서 정리하는 것이다. 표로 정리해서 각 상태를 위에서 받은 값으로 업데이트 하면 될 것 이다.

이 경우 n의 값에 따라 메모리가 지수적으로 증가하기 때문에 n 값이 1000까지인 이 경우에 문제를 풀 수 없다.

​

Knapsack에서 힌트 얻기

사실 이 문제를 풀기 바로전에 Knapsack 알고리즘을 공부하고 있었어서 해당 문제도 분명히 이와 비슷하다고 생각햇다. 하지만, 상태공간을 어떻게 정의해야할지 도저히 감이 안잡혔다.

​

그러다가 Knapsack과 LCS와 같이 이차원 표로 표현되는 DP는 A, AB, ABC ... 처럼 고려 갯수가 증가된다는 것을 이용하기로 하였다.

​

​

✍️ 첫번째로 정의하기

어떻게 정의해야할지 감이 잘 안잡힌 상태로 고민하다가, Knapsack에서 열에 해당하는 부분은 한계 조건을 나타낸다는 것을 착안하여 열을 한계조건 RGB로 잡았다.

​

이후 행은 A, AB, ABC 처럼 각 단계별로 경우를 늘려나가는 방향으로 잡았다. 하지만, Knapsack과 다르게 행에서 참고해야할 값이 이전 색깔과 동일해서는 안되기 때문에 idx를 추가로 기록하기로 하였다.

​

정리하자면 다음과 같다.

                                    dp[i][j] = A가 j인 상태일때 i까지의 최솟값.

나중에 설명하겠지만, 해당 정의는 틀렸다. 이유는 아래에 밝히도록 하겠다. 우선 해당 로직으로 작성된 코드를 보자.

                                    import sys

rgbs = []

N = int(sys.stdin.readline().rstrip())

for _ in range(N):
    rgb = list(map(int, sys.stdin.readline().rstrip().split(" ")))
    rgbs.append(rgb)

# dp
"""   j = A가 선택한 값 (0, 1, 2) = (R, G, B)
   i = A, AB, ABC ... N까지 각 단계별로 뒀을 때 최소 값

"""
dp = [[[0, 0] for j in range(3)] for i in range(N)]

for i, v in enumerate(rgbs[0]):
    dp[0][i][0] = v
    dp[0][i][1] = i

for i in range(1, N):
    b_row = dp[i - 1] # [[26, 0], [40, 1], [83, 2]]
    row = dp[i] # [[0, 0], [0, 0], [0, 0]]

    for j, pair in enumerate(row):
        selected = b_row[j][1] # 이전 선택 idx
        # pair = [0, 0]

        min_cost = 99999
        choice = -999
        for k in range(3):
            if k == selected: continue

            if rgbs[i][k] <= min_cost:
                min_cost = rgbs[i][k]
                choice = k

        pair[0] += b_row[j][0] + min_cost
        pair[1] += choice

print(min(dp[-1])[0])

✍️ 간략한 정리

                                    A, B, C = [[26,40,83], [49, 60, 57], [13, 89, 99]]

• 이 로직은 DP로의 접근의 첫발을 뗀 것이다. 하지만 치명적인 오류가 있다. 무엇인지 찾을 수 있겠는가?

​

해당 로직으로 테스트 케이스를 돌려보면 예제 입력 5를 제외하고 모두 통과한다. 하지만 예제 입력 5는 매우 엉뚱한 값이 나오는데 이유는 다음과 같다.

🤔 왜 오류가 발생하였는가?

다음 예시를 보자

                                    A: 26, 40, 83
B: 3, 2, 1
C: 6, 5, 1

위 알고리즘으로 돌렸을때 최솟값은 32이다. 하지만, 실제 최솟값은 26 + 2+ 1 로 29이다. 이와 같은 문제는 j를 A로 고정시켜서 발생하는 문제이다. AB행에서 26+1이 최소값이긴 하지만, 마지막열에서 1이 아닌 5가 선택될 수 밖에없어서 오류가 나는 것이다.

​

이 문제를 해결하기 위해서는 결국 각 행을 결정하는 i번째 요소가 선택가능한 모든 값을 가지고 있어야 한다.

​

• 복잡하게 생각하면 back-tracking을 써야하나 생각했을 것이다. 그렇다 back-tracking은 dp와 호환된다.

​

📌 정의 수정하기

출처: barking dog 블로그

DP는 정의하는 것이 전부이다. 정의만 잘해두면 문제해결이 알아서 된다. 근데 정의가 제일 어렵다...문제를 다음과 같이 정의하자.

                                    DP[i][j] = i번째까지 칠했을 경우, i가 j인 경우 (j = R, G, B)

처음에 세워둔 정의에는 j를 모두 A의 경우로 고정해서 틀렸다. 위 정의로 코드를 다시 작성하였다.

                                    import sys

rgbs = []

N = int(sys.stdin.readline().rstrip())

for _ in range(N):
    rgb = list(map(int, sys.stdin.readline().rstrip().split(" ")))
    rgbs.append(rgb)

# dp
"""   dp[i] = i번째 까지 선택했을때
      dp[i][0~2] = i 번째가 R, G, B

"""
dp = [[[0] for j in range(3)] for i in range(N)]
first = dp[0]
first[0], first[1], first[2] = rgbs[0][0], rgbs[0][1], rgbs[0][2]

for i in range(1, N):
    for j in range(3):
        min_value = 999999
        for k in range(3):
            if k == j: continue
            min_value = min(min_value, dp[i - 1][k])
        dp[i][j] = rgbs[i][j] + min_value

print(min(dp[-1]))

• 깔끔하게 정답이다.

​

처음 테이블을 다시 정리했다.

                                    A, B, C = [[26,40,83], [49, 60, 57], [13, 89, 99]]

• 이제 B의 선택지에 대한 모든 값을 저장하고 있다.

​

첫번째 예외 경우

                                    A: 26, 40, 83
B: 3, 2, 1
C: 6, 5, 1

• 제대로 구해진다.