코딩테스트에서는 각 문제 당 메모리와 시간이 제한되어 있다. 비교적 적은 입력이나 짧은 알고리즘에서는 이러한 제한이 큰 장애가 되지는 않는다. 그러나 입력이 많은 문제 (예를 들어 10억개의 입력 등) 거나 재귀적인 알고리즘에서는 메모리 혹은 시간 제한에 걸리게 된다. 따라서 우리는 최대한 연산 속도와 메모리 공간을 효율적으로 활용하는 알고리즘을 구현해야 한다.
몇몇 문제에서는 메모리 공간을 조금 더 사용할 수록 비약적으로 연산속도를 줄일 수 있는 경우가 존재한다. 이는 뒤에서 설명할 다이나믹 프로그래밍 기법을 사용하는 경우이다. 다이나믹 프로그래밍이란 동적 계획법이라고도 표현하며 2가지 방식이 존재한다. 이는 아래와 같다.
- 탑다운 방식
- 바텀업 방식
먼저 다이나믹 프로그래밍의 기본적인 아이디어는 다음과 같다. 예를 들어 피보나치 수열의 문제를 생각해보자. 피보나치 수열이란 이전 두 항의 합을 현재의 항으로 설정하는 수열이다. 피보나치 수열을 조금 나열해보자.
1 1 2 3 5 8 13 21 34 55 89 ...
이를 수학적 점화식으로 나타내면 다음과 같을 것이다.
파이썬에서 수열은 리스트로 처리할 수 있다. 첫 번째 항을 리스트의 첫 번째 인덱스에 저장, 두 번째 항을 리스트의 두 번째 인덱스에 저장하는 식으로 수열을 처리할 수 있을 것이다. 리스트를 통해서 '연속된 많은 데이터'를 처리할 수 있을 것이다.
위의 수학적 점화식을 파이썬으로 표현하려면 재귀 함수를 이용하면 간단하다.
fibo라는 함수를 만들어서 매개변수인 n이 1 이거나 2 인 경우에 1을 리턴한다. 그렇지 않은 경우에는 fibo(n-1) + fibo(n-2) 를 리턴함으로써 이전 두 항을 더한 값을 리턴하게끔 재귀 함수를 구현하였다.
여기서 fibo 함수에 같이 호출되는 매개변수인 n이 작은 경우에는 정상적으로 작동한다. 그러나 n이 커질수록 문제점이 발생하게 된다. 바로 최대로 호출할 수 있는 재귀 함수의 범위를 넘어가게 되는 것이다. 그로 인해서 오류가 출력되는 것을 알 수 있다. 또한 오류가 발생하지 않는다고 해도 재귀 함수로 구현한 피보나치 수열 알고리즘은 시간 복잡도가 O(2^N) 이기 때문에 n=30 인 경우에는 약 10억 번 가량의 연산을 수행해야 함을 알 수 있다. 즉 연산 속도 측면에서 매우 치명적인 결함이 있는 것이다.
이러한 문제를 해결할 수 있는 방법이 바로 '다이나믹 프로그래밍' 인 것이다. 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어서 문제를 효율적으로 해결하는 알고리즘 기법이다. 비슷한 예로 분할 정복 (Divide and Conquer) 기법도 존재하는데 이 기법 또한 큰 문제를 작게 나눈 다는 점에서 공통적이다. 하지만 둘의 차이점은 다이나믹 프로그래밍에서는 앞선 문제들이 다른 문제들과 서로 영향을 끼친다는 점이다.
다이나믹 프로그래밍을 사용하기 위해서는 다음의 조건을 모두 만족하는 경우여야만 한다.
다이나믹 프로그래밍 사용 조건
1. 큰 문제를 작은 문제로 나눌 수 있는 경우
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일한 경우
위의 조건을 만족하는 경우에 다이나믹 프로그래밍 방법을 사용할 수 있는데 여기에는 두 개의 방식이 존재한다.
- 탑다운 (Top-Down)
- 바텀업 (Bottom-Up)
탑다운 방식이란 큰 문제를 작은 문제로 쪼개서 문제를 해결하는 방식이다. 이 방식에 국한되어 있는 기법 중 한 가지가 바로 메모이제이션(Memoization) 기법인데 이는 한 번 연산한 결과를 메모리 공간에 저장해두고 같은 식을 다시 호출하면 메모리 결과를 그대로 가져오는 기법을 의미한다. (메모이제이션은 값을 저장하는 방법이므로 캐싱 (Caching) 이라고도 한다.)
위의 피보나치 수열 문제를 탑다운 (메모이제이션 기법)을 사용해서 구현한 소스코드는 아래와 같다.
앞선 소스코드와의 차이점은 바로 한 번 계산한 결과를 새로운 리스트에 저장한다는 점이다. 소스코드를 살펴보면 d 라는 리스트를 먼저 0으로 초기화 해둔다. fibo라는 함수를 호출하게 되면 d 리스트에 값이 저장되어 있는지 확인하고 저장되어 있으면 저장된 결과를 그대로 사용한다. 이로써 연산 횟수를 현격히 줄일 수 있는 것이다. 만약 연산을 수행한 적이 없다면 다시 함수를 재귀 호출하여 연산하는 방식으로 원하는 수열의 항을 구하게 된다.
탑다운 방식으로 알고리즘을 구현하더라도 재귀 함수를 호출하는 최대 횟수를 초과하는 경우가 생길 수도 있다. 즉, 오버헤드가 발생할 수 있다는 것이다. 이러한 방식은 단순히 반복문을 이용하여 다이나믹 프로그래밍을 구현하는 방법으로 해결할 수 있는데 이 방법이 더 효율적일 수 있다. 이러한 방식을 바텀업 (Bottom-Up) 방식이라고 한다. 바텀업 방식에서는 반복문을 통해서 작은 문제부터 차근차근 원하는 답을 도출한다.
바텀업 방식으로 피보나치 수열을 구현하면 더욱 간단하게 구현할 수 있다.
소스코드를 살펴보면 함수를 생성할 필요없이 단순히 반복문 하나로 마무리 하는 것을 알 수 있다. 리스트에 값을 초기화하고 반복문 내에서 앞의 두 항을 단순하게 더해서 원하는 항을 구하는 것이다.
위의 코드에서 리스트 d 에 연산 결과를 저장해서 원하는 결과를 얻는 것을 알 수 있다. 바텀업 방식에서는 이렇듯 결과를 저장하는 리스트가 필요한데 이 리스트를 'DP 테이블' 이라고 부른다.
피보나치 수열 (재귀함수)
피보나치 수열 (메모이제이션)
메모이제이션 시 호출 함수 확인
피보나치 수열 (바텀업)
'Algorithm' 카테고리의 다른 글
| 다이나믹 프로그래밍 (Dynamic Programming) (3) - 실전문제 8.3) 개미 전사 (0) | 2023.08.22 |
|---|---|
| 다이나믹 프로그래밍 (Dynamic Programming) (2) - 실전문제 8.2) 1로 만들기 (0) | 2023.08.22 |
| 이진 탐색 (Binary Search) (3) - 실전문제 7.3) 떡볶이 떡 만들기 (2) | 2023.08.05 |
| 이진 탐색 (Binary Search) (2) - 실전문제 7.2) 부품 찾기 (0) | 2023.08.05 |
| 이진 탐색 (Binary Search) (1) - 이진 탐색이란? (0) | 2023.08.05 |
