파이썬 알고리즘 인터뷰 23장 다이나믹 프로그래밍(DP)

오늘 TIL 3줄 요약

• 최적 부분 구조 - 문제의 최적 해결방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제
• DP 알고리즘을 이용하면 최적 부분 구조를 갖고있는 문제를 풀이할 수 있다.
• 최적 부분 구조를 푸는 또 다른 알고리즘으로는 그리디 알고리즘이 있다. 그리디는 그 순간에 최적이라 생각하는 것을 선택하며 풀이
• DP는 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해 나간다.
• 중복되지 않은 문제들은 DP로 풀지 않고 병합정렬, 퀵 정렬 등을 이용해 분할정복으로 풀어나간다.
• 다익스트라 알고리즘은 최적 부분 구조, 중복된 하위 문제들, 탐욕 선택 속성을 모두 갖는 알고리즘이다.

TIL (Today I Learned) 날짜

• 2020 11. 12. FRI

오늘 읽은 범위

• 파이썬 알고리즘 인터뷰 - 23장 다이나믹 프로그래밍

책에서 기억하고 싶은 내용을 써보세요.

• DP의 방법론

  1. 메모이제이션, 하향식 접근 : 하위 문제에 대한 정답을 계산했는지 확인해가며 자연스럽게 재귀로 풀어나간다.

  2. 타뷸레이션, 상향식 접근 : 하위 문제부터 풀어나가며 큰 문제의 정답을 만든다.

  3. 두 방식을 피보나치 수열의 예제 코드로 비교하면 다음과 같다

     # 상향식
     def fib(n):
         dp[0] = 0
         dp[1] = 1
         for i in range(2, n+1):
             dp[i] = dp[i-1] + dp[i-2]
             return dp[n]
     # 하향식
     def fib(n):
         if n<=1:
             return n
         if dp[n]:
             return dp[n]
         dp[n] = fib(n-1) + fib(n-2)
         return dp[n]
     

• DP 대표문제 2) 배낭문제의 파이썬 풀이

• # pack 이라는 리스트 변수애 6 x 16 행렬 형태의 중간 결과 테이블이 생성된다.
  cargo = [
      # 가격, 무게
      (4, 12),
      (2, 1),
      (10, 4),
      (1, 1),
      (2, 2),
  ]
  
  

def zero_one_knapsack(cargo):
    # 배낭의 총 용량
    capacity = 15
    pack = []
    for i in range(len(cargo)+1):
        pack.append([])
    for c in range(capacity+1):
        if i == 0 or c == 0:
            pack[i].append(0)
        elif cargo[i-1][1] <= c:
            pack[i].append(
                max(
                    cargo[i-1][0] + pack[i-1][c-cargo[i-1][1]],
                    pack[[i-1][c]]
                ))
        else:
            pack[i].append(pack[i-1][c])

        return pack[-1][-1]
```

<p></p>

• 원래 해시 테이블은 입력 순서가 유지되지 않는다. 파이썬 3.6 이하 버전에서는 딕셔너리 입력 순서가 유지되지 않는다. collections.OrderedDict 자료형을 이용해 이를 해결하자.

오늘 읽은 소감은? 떠오르는 생각을 가볍게 적어보세요

• DP는 유난히 문제를 못풀었을때의 허탈함이 큰 것 같다. 문제 해결의 실마리(점화식)의 중요성이 유독 크게 느껴진다.

• 그래도 PS 대회가 아니고서야 유형이 정해져있다는 사실이 위로가 된다.