230310 TIL - DP 구현

---

Dynamic Programming (DP) 사용 예

작은 문제와 큰 문제간 관계 이용, 이전의 해 재활용

• Dijkstra 알고리즘 (single source to multiple destinations 최단 경로)
  • DP인 이유 : 찾아온 길을 기억하면서 출발점s로부터 항상 바깥쪽으로 뻗어 가는 방향으로 탐색하여 절대로 다시 출발점 s쪽으로 돌아오지 않음
  • 이전에 찾은 해에서 하나의 링크를 더하면서 다음 목적지로의 최단 경로를 찾음
• 각 원이 다른 모든 원과 겹치도록 N개의 원을 그렸을 때 교점의 개수 구하기
  • P(N) = P(N-1) + 2(N-1)
  • 이전의 해(원래 있던 교점) + 새로운 원은 기존에 있던 원들과 항상 2개의 새 교차점이 생김
• 2N 명의 사람들이 둥근 탁자에서 팔이 교차되지 않게 짝을 지어 악수를 하는 서로 다른 경우의 수 (카탈란 수)
• knapsack(배낭) 문제 : 총 가치의 합이 최대가 되는 짐의 조합 구하기

---

DP 구현 방법 2가지

1. 함수의 재귀호출 사용
2. 반복문을 사용해 작은 문제부터 차례로 모두 풀기

한 번 계산한 값을 저장해 두었다가 재사용하기 위해 memoization 필요

---

구현 중 생긴 문제와 수정

1. 시간 초과
   2N 명의 사람들이 둥근 탁자에서 팔이 교차되지 않게 짝을 지어 악수를 하는 서로 다른 경우의 수 (카탈란 수)
   반복문을 사용해 작은 문제부터 차례로 모두 풀기 사용

def handshake(n):
    '''
    Return the number of ways to pair 2n vertices around a circle, such that the lines connecting pairs do not cross one another
    Input:
        n -- number of vertices
    '''
    assert type(n) == int, "n = {n} must be an integer" # 입력이 올바른지 확인하는 부분
    assert n>=0 and n<=100, f"n={n} must be >=0 and <=100"

    '''
    Write your codes below
    '''
    memo = [1]

    if (len(memo) > n):
        return memo[n]
    
    
    for i in range(len(memo), n+1):
        sum = 0
        for j in range(i):
            # sum += handshake(n - 1 - j) * handshake(j)
            sum += memo[i - 1 - j] * memo[j]
        memo.append(sum)

    return memo[n]

memoization 안 해서 생긴 문제
-> memo 하는 것으로 해결

2. UnboundLocalError: cannot access local variable 'knapsack_memo' where it is not associated with a value

knapsack_memo = {'loads': [], 0: 0}
def knapsack(n, loads):
    # n: 배낭 크기, loads: item 목록 (3-tuple : 짐 이름, 짐 하나 크기, 짐 하나 가치)

    global knapsack_memo  # 해결
    
    if (knapsack_memo['loads'] == loads):
        pass
    else:
        knapsack_memo = {'loads': loads, 0: 0}

    if (n in knapsack_memo):   
        return knapsack_memo[n]

    values = []
    for i in range(len(loads)):
        if (n >= loads[i][1]):
            values.append(loads[i][2] + knapsack(n - loads[i][1], loads))
        
    # 배낭에 들어가는 짐의 최대 가치 합 반환
    if (len(values) == 0):
        knapsack_memo[n] = 0
        return 0
    knapsack_memo[n] = max(values)
    return max(values)

전역변수를 지역변수로 호출해서 발생
global 키워드 사용함으로써 해결