1. Dynamic Programming(동적 계획법)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법.
각 하위 문제의 결과를 저장해놓고 후에 같은 하위 문제가 나왔을 경우 활용함으로써 계산 횟수를 줄일 수 있다. 특히 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.
2 . DP의 활용 조건
1. 부분 반복 문제(Overlapping Subproblem)
기존 문제의 답을 그 문제의 부분들의 답을 사용하여 구할 수 있는 구조
2. 최적 부분 구조 (Optimal Substructure)
부분 문제들이 중복되어 계산되는 문제
3. Divide and conquer(분할 정복), Greedy Algorithm(탐욕 알고리즘)과 비교
분할 정복은 문제를 나눌 수 없을 때까지 분할해 재귀적으로 문제를 해결한 뒤 다시 합병하여 기존 문제를 해결하는 방식이다.
기존 문제를 작은 문제로 나누는 것은 공통점이지만 분할 정복의 부분 문제는 서로 중복되지 않고 메모이제이션 기법을 사용하지 않는다는 차이점이 있다.
탐욕 알고리즘은 최적해를 구하는데 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때 마다 그 순간에 최적이라고 생각되는 것을 선택해나가며 최종 해답에 도달하는 방식이다.
동적 계획법은 경우의 수를 모두 검토하기 위해 점화식을 통해 구성되는 반면, 탐욕 알고리즘은 순간순간의 최적의 선택을 선택한다는 차이점이 있다.
예를 들어, A라는 지점에서 B지점까지 가능한 빨리 이동하는 경로를 찾고 싶을 때를 생각해보자. 동적 계획법은 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안해 최적의 경로를 찾아낸다. 반면 탐욕 알고리즘은 전체적인 상황은 고려하지 않고 순간순간 교차로가 보일 때마다 가장 빠른 경로를 찾는다.
동적 계획법은 항상 최적의 해를 도출하지만 시간이 오래 걸리고, 탐욕 알고리즘은 최적의 해가 아닐 수 있지만 시간이 짧게 걸린다.
4. Memoization(메모이제이션)
기존 문제를 분할하면서 해결하는 하향식 방법(top-down).
메모이제이션은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 동적 계획법의 핵심기술이다.
가장 대표적인 예인 피보나치 수열에 메모이제이션을 적용해보자.
#메모이제이션을 위해 리스트 0으로 초기화
memo = [0] * 100
def fib(n):
if n == 1 or n == 2:
return 1
#이전에 계산한 결과가 없을 경우 계산
if memo[n] == 0:
memo[n] = fib(n-1) + fib(n-2)
#리스트에 저장된 값 반환
return memo[n]
5. Tabulation(타뷸레이션)
가장 작은 문제를 해결하고 최종적으로 기존 문제를 해결하는 상향식 방법(bottom-up).
메모이제이션이 결과가 필요해질 때 계산하는 방식이라면, 타뷸레이션은 필요하지 않은 값도 미리 계산해두는 방식이다.
마찬가지로 피보나치 수열에 타뷸레이션을 적용해보자.
def fib(n):
#초기값
tabel = [0] * (n+1)
tabel[1] = 1
tabel[2] = 1
#점화식으로 값을 채워나감
for i in range(3, n+1):
tabel[i] = tabel[i-1] + tabel[i-2]
#리스트에 저장된 값 반환
return tabel[n]참고
https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://velog.io/@alexjlee/TIL-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%99%EC%A0%81-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9-%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98-%ED%83%91
