01. 동적 계획법(Dynamic Programming)

동적 계획법이란?

가장 작은 부분의 해답을 구한 후 이를 저장하여, 저장한 값을 이용해 상위 문제를 풀어가는 방식

Dynamic Programming (동적 계획법) 조건

동적 계획법을 적용하기 위해서는 두 가지 속성을 만족시켜야 한다.

1. 부분 반복 문제 (Overlapping Subproblem)
2. 최적 부분 구조 (Optimal Substructure)
   

1. 부분 반복 문제 (Overlapping Subproblem)

• 동적계획법의 등장은 피보나치 수열이라고 한다. 피보나치 수열은 대표적인 재귀함수로, 아래와 같이 표현할 수 있다.

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

만약 fibo(7) 을 구하는 과정을 도식화 해보면, 아래 이진 트리와 같다.

이때 부분문제 (subproblem) 란 항상 새로운 부분 문제를 생성해내기 보다는 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가르킨다.

2. 최적 부분 구조 (Optimal Substructure)

• 최적 부분 구조란, 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.
• 그럼 중복되는 연산과정을 줄이기 위해서는 어떻게 해야할까? 이것은 바로 Memoization 개념에서 설명할 수 있다.

🤔 Memoization은 무엇일까?

동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장하여 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 함
하향식 접근 방법

코딩테스트에서의 DP

• 코딩테스트의 단골 문제로 출제되고 있기에 필수적으로 알아야하는 개념 중 하나이다.
• 간혹 제약사항에 주어지는 숫자의 범위가 크고, 경우의 수가 엄청 많은 문제들이 대부분 DP(동적계획법) 을 활용하여 풀어야 하는 문제이다.
  

시간복잡도

O(N)

한번의 반복문을 사용하기 때문에 시간복잡도는 O(N)이다. 또한 각 항의 값을 기억하고 있어야 하니까 O(N)의 메모리가 필요하기 때문에 공간복잡도 또한 O(N)이다.

코드

func fibo(_ n: Int) -> Int {
    var cache: [Int] = [0, 1]
    
    for num in 2...n {
        cache.append(cache[num - 1] + cache[num - 2])
    }
    
    return cache[n]
}

fibo(4)