동적 계획법 테크닉

DP technique

• 최적화 문제 답 계산하기

  • 최적화 문제의 실제 답을 계산하는 데 쓰인다. 지금까지는 최적해의 수만을 계산했지 실제 최적해가 어떻게 이루어져 있는지는 직접 계산해야 한다.
    1. 재귀 호출의 각 단계에서 최적해를 만들었던 선택을 별도의 배열에 저장해둔다.
    2. 별도의 재귀 함수를 이용해 이 선택을 따라가며 각 선택지를 저장하거나 출력한다.

• k번째 답 계산하기
  1. 답들을 사전 순서대로 만들며 경우의 수를 세는 완전 탐색 알고리즘을 설계하고, 메모이제이션을 적용해 경우의 수를 세는 동적 계획법 알고리즘으로 바꾼다.
  2. 모든 답들을 사전순으로 생성하며 skip(k - 1)개를 건너뛰고 첫 번째 답을 반환하는 재귀 호출 함수를 구현한다. 재귀 함수는 각 조각들에 들어갈 수 있는 값을 하나씩 고려하면서 이 값을 선택했을 때 만들어지는 답의 수 M과 건너 뛰어야 할 답의 수 skip을 비교한다.

  • M <= skip: M개의 답은 모두 우리가 원하는 답보다 앞에 있으므로, 건너뛰고, skip을 M만큼 줄인다.
  • M > skip: M개의 답 중에 우리가 원한느 답이 있으므로, 이 값을 선택한다. M개의 답 중에 skip개를 건너뛴 것이 우리가 원하는 답이므로 이 값을 답에 추가하고 재귀 호출로 답의 나머지 부분을 만든다.

• 조합 게임 해결하기

  • 여러 조합 게임을 해결하는 데 쓰인다. 조합 게임이란, 체스나 바둑, 오목처럼 두 사람의 참가자가 하는 게임을 가리킨다. 이런 게임을 해결한다는 의미는 게임의 상태가 주어졌을 때 완벽한 수를 찾아내는 알고리즘을 짠다는 뜻이다.

• 반복적 동적 계획법

  • 반복적 동적 계획법도 동적 계획법 테크닉의 일종이다. 동적 계획법을 재귀 호출과 메모이제이션으로 구현하는 방법 외에도 반복문을 이용해서 동적 계획법을 구현할 수도 있다.

---

예제

• 조합 게임

틱택토 (문제 ID: TICTACTOE, 난이도: 하)

• 반복적 동적 계획법

삼각형 위의 최대 경로 (문제 ID: TRIANGLEPATH, 난이도: 하)

🖥️ 정답

python

• 틱택토

python

• 삼각형 위의 최대 경로

---

🤔 풀어보기 + 생각해보기

최적화 문제 답 구하기

여행 짐 싸기 (문제 ID: PACKING, 난이도: 중)

• 풀이

• 정답 코드

k번째 답 계산하기

모스 부호 사전 (문제 ID: MORSE, 난이도: 중)

• 풀이

• 정답 코드

---

마무리

• 최적해의 수를 구하고, 최적해를 실제로 계산하는데 동적계획법이 쓰인다. 동적 계획법 메모이제이션은 재귀 호출을 이용하는 동적 계획법과 반복문을 이용하는 동적 계획법(반복적 동적 계획법)이 있다.

• 많은 문제 풀이를 통해 경험을 쌓고 체화를 시키지 않는 이상, 문제에 바로 적용하기엔 쉽지 않은 것 같다.

---

✏️ HOMEWORK

숫자게임 (문제 ID: NUMERGAME, 난이도: 하) (선택)

• 풀이

• 정답 코드

회전초밥 (문제 ID: SUSHI, 난이도: 중)

• 풀이

  반복적 동적 계획법, 슬라이딩 윈도우 기법을 적용해서 최대한 시간복잡도를 줄여봤는데 시간초과가 났다. 예제 입력에 대한 출력은 똑바로 잘 되는데, 같은 로직으로 C++로 제출하면 통과가 될 것 같다. 정녕 파이썬의 한계인 것인가? 어떻게 하면 이 난관을 헤쳐 나갈 수 있을까...

• 코드

# SUSHI
# 계속 시간 초과남... python의 한계인건가?
def sushi():
    result = 0  # 선호도의 최대 합
    memoi[0] = 0
    # 모든 예산에 대해 선호도를 비교하고 가장 큰 선호도를 반환
    for budget in range(1, m+1):
        tmp = 0
        for dish in range(n):
            if budget >= price[dish]:
                tmp = tmp if tmp >= memoi[(budget - price[dish]) % 201] + prefer[dish] \
                    else memoi[(budget - price[dish]) % 201] + prefer[dish]
        memoi[budget % 201] = tmp     # 슬라이딩 윈도우
        result = result if result >= tmp else tmp
    return result

price = []
prefer = []
# 예산은 index, 선호도의 합은 값
# 스시 가격은 20,000 이하의 자연수이고, 항상 100 의 배수 -> 100으로 나눔
# 예산의 범위를 0 ~ 20000 제한 -> 0 ~ 200
memoi = [0 for _ in range(201)]

c = int(input())
for _ in range(c):
    n, m = map(int, input().split())
    m //= 100    # 예산을 100으로 나눔
    for _ in range(n):
        pi, pf = map(int, input().split())
        price.append(pi // 100) # 가격도 100으로 나눔
        prefer.append(pf)
    print(sushi())