[Data Structure / Algorithms] DP(Dynamic Programming) (2) - Tabulation vs Memoization

주제: DP 계산 방식

---

Tabulation vs Memoization

Tabulation과 Memoization은 반복되는 비용이 큰 계산을 하는 함수의 실행을 최적화하기 위해 사용되는 동적 프로그래밍 기술이다. 이 두 기술은 비슷한 목표를 가지고 있지만 몇 가지 차이점이 있다.

Tabulation

• 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

• 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]
}

출처(참고문헌)

• https://www.geeksforgeeks.org/tabulation-vs-memoization/

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.