[알고리즘] 동적계획법과 분할정복

동적계획법(Dynamic programming, DP)

• 입력 크기가 작은 부분 문제들을 해결 후, 그 문제들의 해를 통해 큰 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
• 상향식 접근법으로, 가장 최하위 해답을 구한 후 저장, 이 해답들을 이용해 상위 문제를 해결한다 (Memoization)
• Memoization: 프로그램 실행 시 이전에 계산한 값을 저장하고 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
• 문제를 쪼갤 때 부분 문제는 중복되어 재활용됨
• ex) 피보나치수열 등

분할정복(Divide and Conquer)

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 하양식 접근법으로, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
  • 일반적으로 재귀함수로 구현
• 문제를 쪼갤 때 부분 문제는 서로 중복되지 않음
• ex) 병합정렬, 퀵정렬 등

동적계획법 VS 분할정복

• 공통점
  • 문제를 쪼개어 가장 작은 단위로 분할한다
• 차이점
  • 동적계획법
    • 부분 문제는 중복되어 상위 문제 해결 시 재활용됨
    • Memoization 기법 사용
  • 분할정복
    • 부분 문제는 서로 중복되지 않음
    • Memoization 기법 사용하지 않음

---

• Memoization
  

• 분할정복
  

---

예시(피보나치 수열) 구현

• 재귀를 이용한 방법

# Python
def fibonacci(num):
    if num <= 1:
        return num
    return fibo(num - 1) + fibo(num - 2)

// Swift
func fibonacci(_ n: Int) -> Int {
	if n <= 1 {
    	return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

• 동적계획법을 이용한 방법

# Python
def fibonacci_dp(num):
    cache = [0 for _ in range(num+1)] # 하위값들을 저장할 list
    cache[0] = 0 # 피보나치수열 초기값 저장
    cache[1] = 1 # 피보나치수열 초기값 저장
    
    for i in range(2, num+1):
        cache[i] = cache[i-1]+cache[i-2] # 반복해서 저장
    return cache[num]

// Swift
func fibonacciDp(_ n: Int) -> Int {
    var cache = (0...n).map { $0 * 0 }
    cache[0] = 0
    cache[1] = 1
    
    for i in 2...n {
        cache[i] = cache[i-1] + cache[i-2]
    }
    return cache[n]
}

참고

• 피보나치 수열은 일반항이 존재한다
  • $F_n = {\frac{1}{\sqrt{5}}}\left(\left( \frac{1+\sqrt{5}}{2} \right)^n-\left( \frac{1-\sqrt{5}}{2} \right)^n\right)$