[자료구조와 알고리즘] Algorithm Advanced

동적 계획법 ( Dynamic Programming ) 이란?

- 문제의 일부분을 풀고 그 결과를 재활용하는 방법

- 하나의 문제를 중복되는 서브문제로 나누어 푸는 방법

- DP는 분할정복에 아래 개념이 추가됨

• 중복된 ( 반복되는 ) 서브문제 ( Overlapping Subproblems )
• 최적 부분 구조 ( Optimal Substructure )

- DP에 두 가지 방법론이 존재함

• 메모이제이션 ( 하향식 방법 ) : 메인무제를 분할하면서 해결을 하는 법

def memo_fib(input_value, save_memo):
    if input_value < 3:
        save_memo[input_value] = 1
    if input_value in save_memo:
        return save_memo[input_value]

    save_memo[input_value] = memo_fib(input_value - 1, save_memo) + memo_fib(input_value - 2, save_memo)

    return save_memo[input_value]

• 태뷸레이션 ( 상향식 방법 ) : 가장 작은 문제를 먼저 해결하고 최종적으로 메인문제를 해결하는 법

def tabul_fib(input_value):
    li = [i for i in range(input_value+1)]
    if input_value < 2:
        return input_value
    
    for i in range(2, input_value+1):
        li[i] = li[i-1] + li[i-2]

    return li[input_value]

탐욕 알고리즘 ( Greedy ) 란?

- 탐욕알고리즘은 발견법 ( Heuristic Method ) 의 방법 중 하나임

• 발견법 : 최선, 최적의 답을 찾기보다도 주어진 상황을 한단계씩 빠른 시간 내에 해결하기 위해 사용하는 방법론
  • Backtracking ( 역추적 ) 과 같이 알고리즘 수행시간이 많이 걸릴 때 사용하는 방법

- 탐욕법은 이전의 선택으로 돌아가는 역추적과는 반대개념으로, 다른 문제들과 독립적임

# 잔돈갯수 구하기

def changes(price):
    change = 1000 - price
    coin_list = [700, 400, 300, 100, 50, 10]
    
    change_count = {}

    while change != 0:
        for coin in coin_list:
            change_bool = 0
        
            change_bool = change_bool + (change // coin)
            if change_bool == 0:
                continue
            change_count[coin] = change_bool

            change = change - (change_bool * coin)

    return change_count