동적계획법(DP)
- 모든 가능성을 고려해서 최적의 결과 도출
- 그리디에 비해서 시간은 걸리지만 결과적으로는 항상 최적의 해 도출
그리디 알고리즘(greedy)
- 현 상태에서 가장 최적의 경우 판단하여 결정
- 도출된 결과값이 항상 최적의 해라고 판단할 수 없음
동적 계획법(Dynamic programming, DP)
쉽게 말해 -> 기억하며 풀기, 답을 재활용하는 것
N번째 답을 구하기 위해 N-1이나 N-k번째의 값을 재활용하는 것.
예시) 피보나치 수열
1. 재귀함수를 사용하는 경우
def fibo(n):
if n <= 2:
return 1
else:
return fibo(n-1) + fibo(n-2)- 동적 계획법을 사용하는 경우
다이나믹 프로그래밍을 사용할 수 있는 조건
1. 최적 부분 구조(optimal substructure): 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음
2. 중복되는 부분 문제(Overlapping subproblem): 동일한 작은 문제를 반복적으로 해결함
메모이제이션(Memoization)
하향식(top-down)
:한 번 계산한 결과를 메모리에 저장해 두고 꺼내쓰면서 중복을 방지하는 기법
=> 결과가 필요해질 때 계산 lazy-evaluation
num = int(input())
dp = [0]*(num+1)
dp[1] =1
dp[2]= 1
def fibonacci(num):
if dp[num] == 0:
dp[num] = fibonacci(num-1) + fibonacci(num-2)
return dp[num]
print(fibonacci(num))타뷸레이션(Tabulation)
상향식(bottom-up)
: 값을 미리 계산 -> 필요하지 않은 값도 미리 계산 eager-evaluation
초기화에 오버헤드가 있지만 일단 값을 계산해두면 시간복잡도는 O(1)이 된다.
def fibonacci(num):
dp = [0] * (num+1)
dp[0] =0
dp[1] =1
for i in range(2, num+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp)
return dp[num]
print(fibonacci(num))분할정복(Divide and Conquer)
문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 합치며 문제의 답을 얻는 알고리즘
분할: 원래 문제를 분할하여 더 작은 하위 유형의 문제들로 나누기정복: 하위 문제를 각각 해결합치기: 하위 문제의 답을 합치기
분할 정복과 동적계획법 비교
공통점
: 문제를 부분 문제로 쪼개서 가장 작은 단위로 분할한다.
차이점
동적 계획법
: 부분 문제는 중복되어 상위 문제 해결 시 재활용
: Memoization
: 문제를 나누고 나누어진 문제들을 먼저 푼다.
: 그러나 이미 풀어서 답을 알고 있는 부분의 결과가 다시 필요한 경우에는 또 계산하는 대신 이미 계산된 결과를 그냥 재사용한다!
분할 정복
: 부분 문제는 서로 중복되지 않는다.
=> 나누어진 문제들이 서로 연관이 없는 경우
: Memoization 기법 사용 안함
그리디 (Greedy), 탐욕 알고리즘
지금 이 순간 가장 당장 최적인 값을 선택하여 답 도출하는 것 => 매 선택의 순간에서는 최적이지만 최종적으로 봤을 때 최적의 선택이라고는 보장할 수 없다.
그리디 조건)
-
최적 부분 구조(Optimal Substructure): 전체 문제의 해를 부분 문제로 구할 수 있다. -
탐욕적 선택 속성(Greedy Choice property): 각 단계에서 최선의 선택을 했을 때 전체 문제의 최적의 해를 구할 수 있다.
거스름돈 걸러주기
def solution(money):
answer = 0
change = [500, 100, 50, 10]
remain = money
for i in change:
answer += remain // i
remain = remain % i
return asnwer 하지만 거스름돈이 3원, 7원, 27원 이렇게 떨어지지 않는다면? Dp를 고려해야 할 수도 있다.
