[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

Dynamic Programming (동적 계획법)

동적계획법(다이나믹 프로그래밍) 이란, 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간을 내어 풀 때 사용한다. - Wikipedia

▷ 코딩테스트에서의 DP

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

 

Dynamic Programming (동적 계획법) 방법

모든 작은 문제들을 한 번만 풀어야 한다. 따라서 정답을 구한 작은 문제의 답은 어딘가에 메모해놓는다. 다시 그 보다 큰 문제를 풀어나갈 때, 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제에 대한 결과값을 이용하는 것이 DP 이다.

즉, 상향식 접근법으로, 가장 작은 부분의 해답을 구한 뒤 이를 저장하고, 저장한 값을 이용하여 상위 문제를 풀어가는 방식이라고 하면 되겠다. 이때 동적계획의 핵심은 Memoization(메모이제이션) 이라는 기법인데, 이에 대한 내용은 아래서 다뤄보자.

 

Dynamic Programming (동적 계획법) 조건

동적 계획법을 적용하기 위해서는 위 정의에서 본 것처럼, 두 가지 속성을 만족시켜야 한다.

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

 

▶ 부분 반복 문제 (Overlapping Subproblem)

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

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

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

7번째 값을 구하기 위해서는 총 25번의 함수가 호출된다는 것을 알 수 있다. 이 과정에서 fibo(5), fibo(4), fibo(3)들이 이미 진행했던 연산임에도 불구하고 재귀되며 반복적으로 연산하는 것을 볼 수 있다.

이러한 반복적인 연산을 부분 반복 문제 (Overlapping Subproblem) 이라고 한다. 이는 어떤 문제가 여러 개의 부분 문제로 쪼개질 수 있을 때 사용하는 용어이다.

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

▶ 최적 부분 구조 (Optimal Substructure)

최적 부분 구조란, 작은 부분 문제에서 구한 최적의 답으로 합쳐진 큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다. 

아래 피보나치 수열의 식을 보자.

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

큰 문제의 답인 fibo(n) 이 최적의 답이 되려면, 작은 부분의 문제인 fibo(n-1), fibo(n-2)이 최적의 답이어야만 한다. 작은 부분의 문제의 최적의 답으로 큰 문제의 최적의 답을 구한다는 뜻이다.

여기서, fibo(n-1)을 구하기 위해서는 다시 fibo(n-2) + fibo(n-3)이 되고, fibo(n-2)가 중복되게 된다. 그리고 최적 부분 구조를 만족한다면 문제의 크기에 상관없이 fibo(n-1)은 언제나 일정한 값을 가진다.

그럼 이 중복되는 연산과정을 줄이기 위해서는 어떻게 해야할까? 이것은 바로 Memoization 개념에서 설명할 수 있다.

 

Memoization (메모이제이션)

위의 중복되는 연산과정을 해결하기 위해서는 Memoization(메모이제이션)이라는 동적계획법의 개념이 도입되게 된다.

Memoization(메모이제이션)은 컴퓨터 프로그램이 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. - Wikipedia

즉, 메모리에 계산한 값을 저장해 나감으로써 반복 수행될 때 연산 없이 저장된 값을 사용한다는 개념이다.

이러한 메모이제이션 이라는 개념을, 스위프트 코드를 통해서 구현해보자. cache라는 배열을 이용해서 값을 저장해주었다.

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

배열을 생성하고, 계산한 값을 저장하고, 저장된 값일 경우 배열의 값을 리턴하는 형식으로 코드를 구현할 수 있다. 이렇게 하게 되면 연산의 중복을 막을 수 있다. 주로 저장을 해두는 메모리를 cache라고 부른다.

 

동적계획법의 2가지 접근 방법

동적계획법으로 문제를 해결하려고 할 때, 두 가지의 접근 방법이 존재한다.

• Bottom - up
• Top - down
  
  

▶ Bottom - up 방법

말그대로, 아래서 위로 접근하는 방법으로 부분 문제에서부터 문제를 해결하여 점차 큰 문제를 풀어가는 방식이다. for 문을 이용하는 방식이 이에 해당한다.

var cache = [Int](repeating: 0, count : 101)

cache[1] = 1
cache[2] = 1

func fibo(_ n: Int) -> Int {
	for i in 3...n {
    	cache[i] = cache[i-1] + cache[i-2]
    }
    
    return cache[n]
}

 

▶ Top - Down 방법

말그대로, 위에서 아래로 접근하는 방법으로, 큰 문제에서 부분 문제로 쪼개가면서 재귀 호출을 통해 문제를 푸는 방법이다.

//범위보다 1크게
// cache[0] 초기값 상태 0으로 모두 채워줌
var cache = [Int](repeating: 0, count: 101)

cache[1] = 1
cache[2] = 1

//피보나치 수열
func fibo(_ n: Int) -> Int {
	if cache[n] != 0 {
    	return cache[n]
    }
    
    cache[n] = fibo(n-1) + fibo(n-2)
    return cache[n]
}

 

 

👏🏻 참고한 자료, 감사합니다

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적 계획법(Dynamic Programming)

https://babbab2.tistory.com/100

Swift) 동적 계획법 (Dynamic Programming) 이해하기