TIL(27) 21-10-25 : Brute Force, DP, Greedy

Facts

✅ 완전탐색 2문제

✅ DP 1문제

✅ Greedy 1문제

 

Findings

Fibonacci 공식을 Recursive와 Dynamic Programming으로 구현시 차이점

• Recursive

f(n) = f(n-1) + f(n-2)

f(1) = 1

f(2) = 1

def fibonacci(N):
	if N == 1 or N == 2:
		return 1

	return fibonacci(N-2) * fibonacci(N-1)

 

• Dynamic Programming

f(n) = f(n-1) + f(n-2)

f(1) = 1

f(2) = 1

계산이 중복되므로, 계산 값을 자료구조에 저장하여, 두번 이상 벌어지는 로직에 대해 그 값을 쓰게 한다.

def factorial(N):
    dp = [0 for i in range(N+1)]
    dp[1] = 1
    dp[2] = 1
    for i in range(3, N+1):
    	dp[i] = dp[i-1] + dp[i-2]
    
    return dp[N]

→ DP의 장점

• 피보나치 함수를 재귀를 통해 값을 구하면 O(2 ^ N)이라는 값이 나오지만,
• memorization 방법을 사용하면
  (= 계산 값을 자료구조에 저장하여, 두번 이상 벌어지는 로직에 그 값을 쓰게 하면),
  dp배열을 1번부터 N번까지 채우는  O(N)이라는 시간복잡도면 충분하다!
• 계산 값을 자료구조에 저장하여, 두번 이상 벌어지는 로직에 그 값을 쓰게 하여,
  시간복잡도를 줄일 수 있다.