Tabulation과 Memoization은 반복되는 비용이 큰 계산을 하는 함수의 실행을 최적화하기 위해 사용되는 동적 프로그래밍 기술이다. 이 두 기술은 비슷한 목표를 가지고 있지만 몇 가지 차이점이 있다.
- Tabulation은 하위 문제의 결과를 테이블에 저장하고 이러한 결과를 사용하여 전체 문제를 해결할 때까지 더 큰 하위 문제를 해결하는 Bottom-up 접근 방식이다.
- 이 방식은 문제를 하위 문제의 시퀀스로 정의할 수 있고 하위 문제가 중첩되지 않을 때 사용한다.
- 일반적으로 반복문을 사용하여 구현되며 큰 입력 집합을 가지는 문제에 적합하다.
- 하향식 접근 방식
- 하위 문제의 결과를 테이블에 저장함
- 반복적 구현
- 큰 입력 집합을 가지는 문제에 적합
- 하위 문제가 중첩되지 않는 경우 사용
// Tabulation를 활용한 fibonacci
func fibonacci(_ x: Int ) -> Int {
var dp = [Int](repeating: 0, count: x + 1)
if x == 0 {
return 0
} else if x == 1 {
return 1
}
dp[1] = 1
for i in 2...x {
dp[i] = dp[i - 1] + dp[i - 2]
}
return dp[x]
}- 처음부터 계산해서 올라감
- Memoization은 입력이 같으면 함수 호출의 결과를 캐싱하고 동일한 입력으로 함수가 다시 호출되면 캐싱된 결과를 반환하는 Top-down 방식이다.
- Caching) 오랜시간 걸리는 작업의 결과를 저장해서 시간과 비용을 필요로 회피하는 기법을 의미한다.
- 이 방식은 문제를 하위 문제로 나누고 그 하위 문제가 하위 문제들을 포함하고 있을 때 사용한다.
- Memoization은 대표적으로 재귀적으로 구현되며 상대적으로 작은 입력을 가지는 문제에 적합하다.
- 탑다운 접근 방식
- 함수 호출 결과를 캐싱함
- 재귀적 구현
- 상대적으로 작은 입력 집합을 가지는 문제에 적합
- 하위 문제가 중첩된 경우 사용됨
func fibonacci(_ x: Int) -> Int {
var cahce = [Int](repeating: 0, count: x + 1)
if x == 1 {
return 1
}
if x == 2 {
return 1
}
if cache[x] != 0 {
return cache[x]
}
cache[x] = fibonacci(x-1) + fibonacci(x-2)
return cache[x]
}- [[8. DP(Dynamic Programming)]]
- #Algorithm/Dynamic_Programming/Tabulation
- #Algorithm/Dynamic_Programming/Memoization
- #Algorithm/Math/Fibonacci