탑 다운 방식은 재귀적인 방법으로 문제를 해결하는 방식입니다. 큰 문제를 작은 문제로 나누어 해결하며, 작은 문제의 해결 결과를 저장해두고 재사용하는 방식입니다. 이 방법은 일반적으로 메모이제이션(memoization) 이라고 불리는 기법을 통해 중복 계산을 피합니다.
탑 다운 방식에서는 큰 문제를 해결하기 위해 작은 문제로 쪼개고, 작은 문제의 해결 결과를 저장해 두는 것이 핵심입니다. 이를 통해 중복 계산을 피하며 효율적인 문제 해결이 가능합니다.
예를 들어, 피보나치 수열을 구하는 문제를 탑 다운 방식으로 해결해보겠습니다.
def fibonacci(n, dp):
# 이미 계산된 결과가 있다면 그 값을 반환
if dp[n] != None:
return dp[n]
# 기저 조건
if n == 0 or n == 1:
dp[n] = n
return n
# 작은 문제로 나누어 해결하고 결과 저장
dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp)
return dp[n]
n = 10
dp = [None] * (n + 1)
result = fibonacci(n, dp)
print(result)
이 코드에서는 dp라는 리스트를 생성해 문제의 결과를 저장합니다. 이미 계산된 값이 있는지 확인한 후에는 그 값을 반환하고, 계산된 값이 없다면 작은 문제로 나누어 해결하고 그 결과를 저장합니다. 이렇게 하면 중복 계산을 피할 수 있으며, 피보나치 수열을 효율적으로 구할 수 있습니다.
보텀 업 방식(Bottom-up approach)
보텀 업 방식은 작은 문제부터 시작하여 큰 문제를 해결하는 방식입니다. 작은 문제들을 순차적으로 해결하며, 그 결과를 저장하여 나중에 큰 문제를 해결할 때 재사용합니다. 이를 통해 중복 계산을 피하면서 효율적으로 문제를 해결할 수 있습니다.
보텀 업 방식은 일반적으로 반복문을 사용하며, 큰 문제를 작은 문제로 쪼개어 순차적으로 해결합니다.
예를 들어, 피보나치 수열을 구하는 문제를 보텀 업 방식으로 해결해보겠습니다.
def fibonacci(n):
# 결과를 저장할 리스트 초기화
dp = [0] * (n + 1)
# 기저 조건
dp[0] = 0
dp[1] = 1
# 작은 문제부터 순차적으로 해결
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
n = 10
result = fibonacci(n)
print(result)
이 코드에서는 dp라는 리스트를 생성하여 결과를 저장합니다. 초기 값으로 피보나치 수열의 첫 번째와 두 번째 항을 저장한 후에는, 작은 문제부터 순차적으로 해결하여 결과를 저장합니다. 이렇게 하면 중복 계산을 피하면서, 피보나치 수열을 보텀 업 방식으로 효율적으로 구할 수 있습니다.