Dynamic Programming, Greedy Algorithm

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 방법이다. 각 하위 문제는 한 번만 계산되며, 그 결과는 테이블에 저장되어 필요할 때마다 재사용된다. 이 접근법은 중복 계산을 피하고, 효율성을 크게 향상시킨다.

 

DP 추천 알고리즘 : https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

DP는 큰 문제를 해결할 수 있는 작은 문제로 나누고, 각 하위 문제를 해결하고, 결과를 저장한 뒤, 저장된 하위 문제의 해결책을 조합하여 원래 문제의 해결책을 구하는 방식이다.

 

Top-Down(Memoization)방식은 큰 문제를 작은 문제로 나누어 재귀적으로 해결한다. 이미 계산된 결과는 저장(메모)하여 중복 계산을 방지한다.

 

Bottom-Up(Tabulation)방식은 가장 작은 하위 문제부터 시작하여 순차적으로 큰 문제를 해결해 나가는 방식이다. 각 단계의 결과를 테이블에 저장하며, 최종적으로 원하는 문제의 해를 얻을 수 있다.

 

피보나치 수열에서 F(n) = F(n-1) + F(n-2)라는 관계가 있다. 이를 동적 계획법으로 해결할 수 있다.

# Top-Down
def fib_memo(n, memo):
    if n <= 1:
        return n
    if memo[n] == 0:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

n = 10
memo = [0]*(n+1)
print(fib_memo(n, memo))

#Bottom-Up
def fib_tab(n):
    if n <= 1:
        return n
    fib_table = [0]*(n+1)
    fib_table[1] = 1
    for i in range(2, n+1):
        fib_table[i] = fib_table[i-1] + fib_table[i-2]
    return fib_table[n]

n = 10
print(fib_tab(n))

 

탐욕 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 선택을 하여 최종적인 해답에 도달하는 방법이다. 이 알고리즘은 전체를 고려하는 것이 아니라, 각 단계에서 최선의 결정을 내려서 전역 최적화(global optimum)를 추구한다. 탐욕 알고리즘은 구현이 간단하고, 계산 효율이 높다는 장점이 있지만, 모든 문제에 대해 항상 최적의 해를 보장하지는 않는다.

 

107을 얻을 수 있지만 눈 앞의 이익을 따라 결국에는 24를 얻은 모습

 

그리디 알고리즘은 각 단계에서 지역적으로 최적이라고 판단되는 선택을 함으로써 전체 문제의 최적해를 찾아가고, 한 번 선택된 결정은 취소할 수 없다. 최적의 선택을 통해 탐색 공간을 신속하게 축소한다.

 

그리디 알고리즘을 적용하기 위해서는 두 가지 규칙이 있는데 첫 번째는 앞의 선택이 이후의 선택에 영향을 주지 않으며, 부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있는 것이고, 두 번째 규칙은 문제의 최적 해결책이 그 부분 문제의 최적 해결책으로부터 구성될 수 있다는 것이다.

#동전의 종류가 500원, 100원, 50원, 10원이 있을 때, 
#거스름돈을 가장 적은 수의 동전으로 나누어 주는 방법을 찾는 것이 목표

def min_coins(change, coins):
    count = 0
    for coin in sorted(coins, reverse=True):
        count += change // coin
        change %= coin
    return count

coins = [500, 100, 50, 10]
change = 1260
print(min_coins(change, coins))

 

각 단계에서 가장 큰 동전부터 최대한 많이 사용하는 탐욕적 선택을 한다. 이러한 선택이 전체 문제에 대한 최적의 해답(최적 해)을 제공한다.