[Algorithm/Swift] 동적 계획법(Dynamic Programming)

안녕하세요 제인입니다!

오늘은 알고리즘 개념 중 동적 계획법(Dynamic Programming)에 대해 정리해보려고 합니다.

동적 계획법이 무엇인지 정리해보고, 동적 계획법의 대표적인 예제인 <피보나치 수열> 문제를 통해 적용까지 해보도록 할게요!

동적 계획법(Dynamic Programming, DP)

다이나믹 프로그래밍(줄여서 DP)라고도 불리는 동적 계획법은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법입니다.

동적 계획법에서는 메모이제이션(Memoization) 기법이 핵심이라고 할 수 있는데요!

메모이제이션 기법이란, 한 번 구한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출해 저장한 결과를 그대로 가져오는 기법을 의미합니다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 합니다.

동적 계획법은 메모이제이션 기법을 활용해 동일한 계산을 반복해야할 때, 이전에 계산한 값을 메모리에 저장하여 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하기 때문에 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가시킬 수 있는 방법입니다.

동적 계획법으로 해결할 수 있는 대표적인 예제인 <피보나치 수열>을 통해서 더 자세히 이해해보도록 합시다!

피보나치 수열로 동적 계획법을 이해해보자

 

피보나치 수열이란, 어떤 수열의 항이 앞의 두 항의 합과 같은 수열을 말합니다.

피보나치 수열을 간단하게 활용한 문제인 프로그래머스의 피보나치 수 문제를 풀어보며 동적 계획법을 이해해보도록 할게요! 

프로그래머스

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 

예를들어 

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

입출력 예시 및 설명

n	return
3	2
5	5

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

문제풀이

1. 재귀함수를 이용한 구현

프로그래머스 Level2 난이도인 이 문제는 n번째 피보나치 수를 구하는데, 이 수를 1234567으로 나눈 나머지를 구하라는 조건만 추가된 문제인데요! 먼저, 재귀함수를 이용해 문제를 풀어본다면

 

func solution(_ n: Int) -> Int {
    if n <= 1 {
        return n
    } else {
        return (solution(n-1) + solution(n-2)) % 1234567
    }
}

 

위와 같이 간단하게 구현할 수 있습니다!

하지만.. 문제는..효율성 측면에서 좋지 못한 코드라는 점입니다!(시간초과가 와르르🥲)

 

이렇게 재귀함수를 이용해 구현하는 풀이가 왜 시간이 오래걸리는 풀이일까요??🤔

만약 4번째 피보나치 수를 1234567으로 나눈 나머지를 구하기 위해 solution(4)를 실행하면,

아래의 그림과 같은 형태로 함수가 호출되게 됩니다.

그림을 보면 동일한 함수가 반복적으로 호출되는 것을 확인할 수 있습니다. 이미 한 번 계산했지만, 계속 호출될 때 마다 동일한 값이 계산되게 되는 것입니다. 위의 그림에서 soultion(1)은 총 3번 호출되었습니다. solution(n)에서 n값이 커지면 커질수록 중복 호출되는 함수와 중복 횟수 또한 늘어나게 되는데, 이는 n값이 커짐에 따라 프로그램 실행 속도가 떨어진다는 것을 의미합니다.

2. 동적 계획법을 이용한 구현

피보나치 수열의 점화식을 위와 같이 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하기 때문에 문제를 효율적으로 해결할 수 없다는 것을 확인했습니다. 이러한 문제는 동적 계획법을 이용해 해결할 수 있습니다.

메모이제이션 기법을 활용해 이전에 계산한 값을 메모리에 저장해 반복 수행을 제거하는 방식으로 구현해봅시다!

 

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

 

위와 같이 구현할 수 있는데요, 코드를 보면 cache라는 Array 저장 공간을 활용해 (이전 두 수의 합 % 1234567)인 값을 저장해두고,

중복 계산 없이 n번째 피보나치 수를 1234567으로 나눈 나머지를 구하고 있습니다. (그냥 n번째 피보나치 수를 구하고 싶다면 for 루프에서 % 1234567 부분만 삭제해주면 되겠죠?)

 

만약 solution(4)를 실행한다면, (0, 1은 실행 시 초기값으로 cache에 저장되니) 2, 3번째 값까지를 먼저 구하여 저장하고, 이 값들이 모두 저장되어있는 메모리에서 필요한 값들을 가져와 cache[2] + cache[3] 연산을 통해 최종 값을 도출하게 됩니다. 앞에서 재귀함수로 구현한 것과 달리 함수의 중복 실행이 없기 때문에 실행 속도가 훨씬 빨라지게 됩니다. 

동적 계획법의 사용 조건

예제를 통해 재귀함수 풀이와 비교해보니 이제 동적 계획법이 어떤 알고리즘 기법인지 감이 오시죠??

하지만 모든 문제를 동적 계획법을 적용하여 해결할 수는 없습니다! 동적 계획법은 다음 두 가지 조건을 만족할 때 사용할 수 있습니다.

 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

동적 계획법의 두 가지 방식

위의 <피보나치 수> 문제에서 적용한 동적 계획법의 풀이 방법은 반복문을 이용해 작은 문제부터 답을 도출해 이를 메모리에 저장해두고 이를 이용해 큰 문제를 해결하는 방식이었습니다. 이렇게 반복문을 이용한 방식은 작은 문제부터 차근차근 답을 도출한다고 하여 보텀업(Bottom-Up) 방식이라고 말합니다.

 

동적 계획법에는 보텀업 방식과 더불어 탑다운(Top-Down) 방식도 존재합니다.

탑다운 방식은 재귀 함수를 이용하여 소스 코드를 작성하는 방식인데요, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운 방식이라고 말합니다.

위에서 재귀 함수를 이용한 방식의 중복 실행이라는 문제 때문에 동적 계획법을 사용해 효율성을 개선했는데 이게 무슨 소린가...하실 수 있을 것 같은데요! 탑다운 방식의 코드를 한 번 살펴봅시다!

 

var cache = Array(repeating: 0, count: 100001)

func solution(_ n: Int) -> Int {
    
    // 종료 조건(1 or 2일 때 1을 반환)
    if n == 1 || n == 2 {
        return 1
    }
    
    // 이미 계산한 적 있는 문제라면 그대로 반환
    if cache[n] != 0 {
        return cache[n]
    } else { // 아직 계산하지 않은 문제일 때 점화식에 따라 계산
        cache[n] = (solution(n-1) + solution(n-2)) % 1234567
    }
    
    return cache[n]
}

 

앞에서 본 재귀함수를 이용한 풀이와 다른 점은 제한 사항에 제시된 최댓값보다 1만큼 큰 크기의 cache라는 배열을 0으로 초기화해두고 계산한 값을 차례로 cache에다 저장해서 나중에 동일한 문제를 계산해야 할 때, 이미 저장한 값을 반환하여 함수의 중복 호출이 없도록 한다는 점입니다! (실제로 이 코드 또한 프로그래머스의 시간 제한에 걸리지 않고 통과됩니다)

 

이렇게 탑다운 방식까지 동적 계획법의 방식 두 가지 모두 살펴보았는데요, 동적 계획법의 전형적인 형태는 보텀업 방식입니다. 재귀함수를 이용해 구현할 경우 값이 너무 커서 함수 호출을 아주 많이 해야할 경우 스택 오버플로우가 발생할 수도 있고, 미리 cache 배열의 크기를 정해서 초기화해두어야 한다는 단점도 있기 때문에 가능하다면 보텀업 방식을 권장한다고 합니다!

 

동적 계획법은 사실 개념은 크게 어렵진 않지만 적용하기가 쉽지 않은 것 같습니다..(동적 계획법으로 풀 수 있겠구나를 깨닫고 점화식을 세우는 과정이 어려운 것 같아요..) 그렇기 때문에 만약 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래걸린다면 동적 계획법을 적용할 수 있는지 해결하고자 하는 부분 문제들의 중복 여부를 확인하는 방식으로 접근하는 것도 좋은 방법인 것 같습니다!

 

---

[참고 자료]

알고리즘과 자료 구조 - 다이나믹 프로그래밍 DP

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

<이것이 코딩 테스트다 with 파이썬>

이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고