[MIT] 파이썬을 이용한 알고리즘 : 동적 프로그래밍 4

 

 

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다.

 

 

✔ 복습

⁉️ 동적 프로그래밍의 5단계

1. 하위 문제 정의하기 ⇒ 하위 문제의 개수 세기
2. (해법의 일부분을) 추측하기 ⇒ 선택지의 개수 세기
3. 하위 문제의 풀이 연관짓기 ⇒ 하위 문제당 시간 계산
4. 재귀+기억 또는 DP 테이블을 상향식으로 만들기 ⇒ 시간 = 하위 문제당 시간·하위 문제의 개수
   하위 문제가 비순환적인지/위상학적 순서인지 확인하기
5. 원래 문제 풀이 ⇒ 추가 시간 필요
   : 하위 문제의 풀이 또는 하위 문제들로 조합하여 풀기

 

 

 

✔ 2종류의 추측

• 2&3단계에서 어떤 하위 문제를 사용할지 추측
  (피보나치를 제외하고 모든 동적 프로그래밍에서 사용)
• 1단계에서 정답 구조에 대해 더 많은걸 기억하거나 추측하기 위해 하위 문제를 추가
  (가방 싸기 동적 프로그래밍에서 사용)
  • 하위 문제에게 해법을 효율적으로 알려줌
  • 부모 하위 문제가 해법의 특징을 알 수 있게 함

 

 

 

✔ 피아노/기타 핑거링

⁉️ 피아노

• n개의 음이 주어져서 그걸 연주할 때 각 음에 어떤 손가락을 사용할지 찾는 것
• 손가락 : 1, 2, ..., F = 5
• d(f, p, g, q) : 음 p를 손가락 f로 연주한 다음 음 q를 손가락 g로 연주할 때의 난이도
  d : 난이도
• 예)
  1 < f < g & p > q ⇒ 불편함
  잡아당기는 규칙: p ≪ q ⇒ 불편함
  레가토(부드럽게) ⇒ ∞ (f = g일 때)
  약한 손가락 규칙: g ∈ {4,5}는 가급적 사용하지 않음
  3 → 4 & 4 → 3 귀찮음 ∼ 기타 등등.

 

⁉️ 올바른 동적 프로그래밍

1. 하위 문제 = i번째 음을 손가락 f로 연주할 때 suffix notes[i:]의 난이도 최솟값
   ⇒ n·F subproblems
2. 추측 = 다음 i+1번째 음을 손가락 g로 연주함
   ⇒ F 개의 선택지
3. 반복: DP[i, f] = min(DP[i + 1, g] + d(note[i], f, note[i + 1], g) for g in range(F))
   DP[n, f] = 0
   ⇒ 하위 문제당 시간Θ(F)
4. 위상학적 순서:
   for i in reversed(range(n)):
       for f in 1, 2, ..., F:
   ⇒ 총 시간 O(nF^2)
5. 원래 문제 = min(DP[0, f] for f in 1,...,F)
   (가장 첫 번째 손가락을 추측)

 

⁉️ 기타

 같은 음을 연주하는 최대 S개의 방법!(S는 줄의 개수)

"손가락"의 재정의 = 음을 연주하는 손가락 + 음을 연주하는 줄 ⇒ F → F ·S

 

일반화 : 한 번에 여러 개의 음(화음)

• 입력: notes[i] = 최대 F개의 음들의 리스트
  (한 손가락으로 여러 음을 연주할 수 없음)
• 상태: 과거에 대해 알아야 함. F개의 손가락에서 F +1 (음 또는 아무것도 안 하는 상태)
  ⇒ (F + 1) F 개의 대응

(1) n·(F + 1)^F개의 하위 문제, (F + 1)^F는 i번째 음을 연주하는 방법의 수

(2) (F + 1)^F개의 선택 (i+1번째 음을 연주하는 방법)

(3) Θ(n·(F + 1)^(2F))의 총 시간

• 양손으로 칠 때도 적용, F = 10
• 적절한 d를 정의할 필요가 있음 

 

 

 

✔ 테트리스

 일반적인 테트리스의 룰에서 아래의 룰을 추가해서 n개의 테트리스 블럭이 주어졌을 때 살아있을 수 있는가? 또는 높이를 h내에서 유지할 수 있는가?입니다.

• n개의 테트리스 조각과 작은 폭 w의 빈 보드가 주어짐
• 무조건 위에서 떨어짐
• 꽉 찬 행은 지우지 않음

 

👀 강의 자료와 강의 내용이 서로 다른 부분이 존재하지만 강의 내용을 토대로 수정하였습니다.

⁉️ 정답

• 하위 문제 = suffix pieces[i:]에서 생존
  보드의 스타이라인(블럭이 쌓여 있는 높이)이 주어져야 함 → 초기의 열이 채워진 정보인 h0, h1, ..., hw-1가 주어진 경우 h라 명명
  ⇒ 하위 문제 = (n· (h+1)^w) 개
• 추측 : i 번째 블럭을 어떻게 플레이할 것인가?
  ⇒ 4w(4개의 회전과 w개의 x좌표)의 선택지 존재
• 반복 : DP[i, h] = max(h의 조각 i의 유효한 이동 m에 대한 DP[i, m])
  ⇒ 하위 문제의 시간 = O(w)
• 위상학적 순서 : for i in reversed(range(n)): for h ...
  ⇒ 총 시간 = Θ(nw(h+1)^w)
• 해답 = DP[0, 0]

 

 

 

✔ 슈퍼 마리오 브라더스

 - 주어진 레벨 : n

 - w×h의 크기를 가지는 화면

 - 게임 상태 : Θ(wc^(wh)ST)

• 화면에 대한 모든 것 : c^(wh)
• 마리오의 속도 : c
• 점수 : S
• 시간 : T
• 화면 vs 레벨 : w

👀 강의에는 없는 자료 내용

- 전환 함수 δ: (게임 상태, 행동) → 게임 상태

  → 아무것도 하지 않거나, ↑,↓,←,→, B, A 버튼을 누르고/떼는 행위

 

⁉️ 풀이

1. 하위 문제: 게임 상태 C로부터의 최고의 점수 (또는 시간)

    ⇒ n·c^(w·h)·S·T개의 하위 문제

2. 추측 : C에서 할 다음 행동

    ⇒ O(1) 선택지

3. 반복

    ⇒ O(1) 하위 문제당 시간

4. 위상학적 순서 : 시간 오름차순

5. 원래 문제 : DP(초기의 게임 상태)

• S와 T의 유사 다항 시간
• n에 대해 다항 시간
• w와 h에 대해 지수적 시간