나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리한다.
(내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저'임을 사전에 밝힙니다.)
'Ch04. 이진 탐색 알고리즘'에 이어, 다이나믹 프로그래밍에 대해 알아볼 것이다. 이진 탐색 알고리즘이 궁금하면 아래 링크를 참조하자.
https://jjuke-brain.tistory.com/73
Ch04. 이진 탐색 알고리즘 (feat. 이것이 취업을 위한 코딩테스트다)
나동빈님 유튜브의 '이것이 취업을 위한 코딩 테스트다'강의와 교재 내용을 공부하고, 그 내용을 정리한다. (내용의 출처는 모두 유튜브 동빈나, 그리고 책 '이것이 취업을 위한 코딩 테스트다 wi
jjuke-brain.tistory.com
강의 영상 링크는 다음과 같다.
https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6
목차
1. 다이나믹 프로그래밍 개요
1) 다이나믹 프로그래밍(Dynamic Programming)이란?
다이나믹 프로그래밍(=동적 계획법)은 메모리를 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
일반적으로, 프로그래밍 분야에서 '동적이다(Dynamic하다)'라는 말은 '프로그램이 실행되는 도중에'와 같은 의미를 갖는다.
- 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다.
- 하지만 알고리즘에서 다이나믹 프로그래밍에서의 다이나믹(Dynamic)은 별다른 의미 없이 사용된 단어이다.
이미 계산된 결과(sub problem, 작은 문제)를 별도의 메모리 영역에 저장해두었다가 해당 결과가 필요할 때 다시 계산하지 않고 그대로 사용한다.
완전 탐색을 이용할 경우(Brute Force) 매우 비효율적인 시간 복잡도를 가질 수 있는데, 다이나믹 프로그래밍을 이용하여 시간 복잡도를 획기적으로 줄일 수 있는 경우가 많다.
다이나믹 프로그래밍의 구현은 일반적으로 Top-down(하향식)과 Buttom-up(상향식) 두 가지 방식으로 구성된다.
2) 다이나믹 프로그래밍의 조건
다이나믹 프로그래밍은 문제가 두 가지 조건을 만족할 때 사용할 수 있다.
(1) 최적 부분 구조 (Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있어야 한다.
(2) 중복되는 부분 문제 (Overlapping Subproblem)
Overlap, 즉 부분 문제가 서로 중첩되어 여러 번 등장한다는 의미이다.
어떤 문제를 해결하기 위해 동일한 작은 문제를 반복적으로 해야할 때 사용한다.
2. 피보나치 수열
다이나믹 프로그래밍을 활용하여 해결할 수 있는 대표적인 문제는 피보나치 수열이다.
피보나치 수열이란, 다음과 같은 형태의 수열이다.
$$ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... $$
특정 index의 피보나치 수는 바로 앞에 있던 두 수를 더한 값으로 정해진다.
$$ 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, ... $$
이와 같이 각각의 항이 인접한 다른 항들 간의 관계식으로 표현된다.
인접한 항들 사이의 관계식을 점화식이라고 한다.
피보나치 수열을 점화식으로 표현하면 다음과 같이 표현할 수 있다.
$$ a_n = a_{n-1} + a_{n-2}, a_1 = 1, a_2 = 1 $$
이러한 점화식은 재귀 함수를 사용하여 코드로 표현할 수 있다.
실제 수열을 프로그램 상에서 표현하고자 할 때에는 배열(리스트)을 사용할 수 있다. 이는 수열이 선형적인 데이터를 표현하기 때문이다.
별도로 테이블과 같은 공간에 값을 기록한다고 하여, 수열을 표현한 배열이나 리스트를 테이블이라고 부르기도 한다.
피보나치 수열이 계산되는 과정으로 도식화하여 표현해보자.
4번째 피보나치 수를 구하기 위해서는 3번째 피보나치 수와 2번째 피보나치 수를 알고 있어야 한다.
또한 3번째 피보나치 수를 구하기 위해서는 1번째와 2번째 피보나치 수를 알아야 한다.
앞서 점화식을 재귀 함수로 표현할 수 있다고 하였는데, 위 그림으로 생각해보자.
f(4)를 호출하면 f(3)과 f(2)를 호출하여 각각의 결과 값을 더하는 과정을 포함한다.
또한 f(3)을 호출할 때에도 내부적으로 f(1), f(2)를 호출하여 결과 값을 더할 것이다.
1) 피보나치 수열: 단순 재귀 소스코드 (Python)
이를 간단히 파이썬 코드로 작성해보면 아래와 같다.
# 피보나치 함수 (Fibonacci Function)을 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2: # 재귀함수 종료 조건
return 1
return fibo(x-1) + fibo(x-2)
print(fibo(4))
실행 결과는 3을 나타낼 것이다.
하지면 이렇게 피보나치 수열을 재귀 함수를 사용하여 단순히 구현한다면, 지수 시간 복잡도를 가져 매우 비효율적이다.
피보나치 수열을 재귀 함수로 구현하였을 때에는 시간복잡도가 다음과 같다.
- 세타 표기법: \(\theta(1.618...^N)\) (황금비 값의 N제곱)
- 빅오 표기법: \(O(2^N)\)
빅오 표기법을 기준으로 f(30)을 계산하기 위해서는 10억 가량의 연산을 수행해야 한다.
위 그림에서와 같이, 고작 6번째 피보나치 수를 구할 때조차 2번째 피보나치 수가 5번이나 사용된다. 이를 부분 문제가 중복된다고 표현한다.
이렇게 이미 해결한 문제의 답을 알려줄 수 있도록 별도의 메모리 공간에 저장해두면 훨씬 효율적으로 계산할 수 있을 것이다.
2) 피보나치 수열의 효율적인 해법: 다이나믹 프로그래밍
그렇다면 다이나믹 프로그래밍을 적용하기 전에, 사용 조건을 만족하는지 살펴보자.
앞서 다이나믹 프로그래밍의 조건은 '최적 부분 구조(Optimal Substructure)', '중복되는 부분 문제(Overlapping Subproblem)'이라고 하였다.
- 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.
- 네 번째 피보나치 수를 구하고자 할 때(큰 문제), 3번째와 2번째 값(작은 문제의 결과값)을 더하여 구한다.
- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다.
- 네 번재 피보나치 수를 구할 때, 3번째 값을 구할 때와 4번재 값을 구할 때 2번째 값(작은 문제의 결과값)이 반복적으로 활용된다.
따라서 다이나믹 프로그래밍을 사용할 수 있다.
(1) 메모이제이션 (Memoization)
앞서 언급했듯, 다이나믹 프로그래밍은 Top-down, buttom-up 두 가지 방식을 사용할 수 있다.
이중 메모이제이션(Memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다.
이는 값을 기록한다는 점에서 캐싱(Caching)이라고도 하며, 같은 문제를 다시 호출하면 메모했던 결과를 가져오게 된다.
Top-down 방식에서 주로 사용된다.
엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해놓는 넓은 개념을 의미하며, 다이나믹 프로그래밍에 국한된 개념은 아니다. 즉, 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다.
(2) Top-down vs Buttom-up
앞서 언급했듯, 다이나믹 프로그래밍은 Top-down, buttom-up 두 가지 방식을 사용할 수 있다.
Top-down 방식은 하향식, Buttom-up 방식은 상향식이라고도 한다.
Top-down 구현 과정에서는 재귀 함수를 사용한다. 즉, 큰 문제를 해결하기 위해 작은 문제를 재귀적으로 호출하여 해결한다.
이 과정에서 한 번 계산된 결과값을 기록하기 위해 메모이제이션 기법을 사용하는 것이다.
Buttom-up은 아래쪽에서부터 작은 문제들을 하나씩 해결해 나가면서 먼저 계산했던 문제들의 값을 활용하여 다음 문제까지 차례대로 해결한다.
따라서 Buttom-up 방식을 구현할 때에는 반복문을 이용한다.
다이나믹 프로그래밍의 전형적인 형태는 Buttom-up 방식으로, 결과 저장용 리스트(배열)를 DP 테이블이라고 부른다.
(3) 피보나치 수열: Top-down 다이나믹 프로그래밍 소스코드 (Python)
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트
d = [0] * 100
# 피보나치 함수 (Fibonacci Function)를 재귀함수로 구현 - Top-down Dynamic Programming
def fibo(x):
# 종료 조건
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제는 그대로 반환
if d[x] != 0: # DP 테이블 확인
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))
실행 결과는 '218922995834555169026'이라는 매우 큰 값을 나타낸다.
Top-down 방식을 따르며 높은 index의 값을 구하기 위해 재귀적으로 낮은 index의 값을 찾아간다.
(4) 피보나치 수열: Buttom-up 다이나믹 프로그래밍 소스코드 (Python)
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현 - Buttom-up Dynamic Programming
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])
실행 결과는 Top-down 방식과 동일하고, 코드를 살펴보면 반복문을 돌면서 작은 수의 index부터 계산함을 알 수 있다.
(5) 피보나치 수열: Buttom-up 다이나믹 프로그래밍 소스코드 (C++)
#include <bits/stdc++.h>
using namespace std;
// 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
long long d[100];
int main(void) {
// 첫 번째 피보나치 수와 두 번재 피보나치 수는 1
d[1] = 1;
d[2] = 1;
int n = 50; // 50번째 피보나치 수를 계산
// 피보나치 함수(Fibonacci Function) 반복문으로 구현 - Buttom-up Dynamic Prgramming
for (int i = 3; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
cout << d[n] << endl;
return 0;
}
실행 결과는 '12586269025'와 같이 나온다.
특이하게 DP 테이블을 초기화할 때 'long long' 자료형을 사용하였는데, 이 자료형이 표현 가능한 범위가 제한적이므로 99번째 피보나치 수를 구하려 하면 범위를 벗어나 오버플로우가 발생한다.
3) 피보나치 수열: 메모이제이션 동작 분석
이미 계산된 결과를 메모리에 저장하면 다음과 같이 색칠된 노드만 처리한다.
재귀적으로 호출된다고 하더라도, 이미 계산된 결과를 메모리에서 꺼내오는 데에는 상수 시간이 사용되므로, 함수가 호출되는 시간이 확연히 줄어듦을 확인할 수 있다.
게다가 실제 호출 시에는 다음과 같이, 계산한 결과를 계속해서 저장하므로 실제 호출되는 함수의 개수는 훨씬 적어진다.
f(6)을 수행할 때 실제 호출되는 함수를 나타내보면 다음과 같다.
따라서 지수시간 만큼 걸리던 피보나치 수열 구현 코드를 시간 복잡도 \(O(N)\)으로 선형 시간까지 시간 복잡도를 줄일 수 있다.
즉, N의 값이 아무리 커져도 메모리 공간 또한 N 만큼 존재한다면 선형 시간 알고리즘으로 문제를 해결할 수 있다.
3. 다이나믹 프로그래밍 vs 분할 정복
앞서 '정렬'파트에서 공부했던 퀵 정렬 등과 같은 분할 정복 아이디어와 비교했을 때, 다이나믹 프로그래밍이 어떤 차이점을 갖는지 확인해보자.
다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조 (Optimal Substructure)를 가질 때 사용할 수 있다.
즉, 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황에 이용된다.
또한 다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복 (Overlapping Subproblems)에 있다.
다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다. (예 : 피보나치 수열 문제) 하지만 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지는 않는다.
분할 정복의 대표적인 예시인 퀵 정렬을 복기해보자.
위와 같이 첫 번째 원소인 '5'를 피봇으로 설정하여 분할을 진행했다고 가정하자.
분할이 완료되면 5는 중간에 들어가게 되는데, 이 위치는 더 이상 바뀌지 않는다.
실제로 퀵 정렬의 동작 원리를 확인해보면 분할이 이루어진 뒤에 왼쪽의 모든 원소와 오른쪽의 모든 원소에 대해 다시 한번 각각 재귀적으로 퀵 정렬을 수행하기는 한다. (최적 부분 구조는 해당됨)
하지만 한 번 피벗이 자리를 변경하여 정해지면 그 기준 원소의 위치는 바뀌지 않는다.
즉, 분할 이후에 해당 피벗을 다시 처리하는 부분 문제가 호출되지 않는 것이다. (부분 문제의 중복은 일어나지 않음)
이는 퀵 정렬 뿐만 아니라 분할 정복의 아이디어를 사용하는 병합 정렬 등의 알고리즘 또한 마찬가지이다.
4. 다이나믹 프로그래밍 문제 접근, 문제 풀이 팁
그렇다면, 다이나믹 프로그래밍 문제를 어떻게 쉽게 해결할 수 있을까?
가장 중요한 것은, 현재 주어진 문제가 다이나믹 프로그래밍 유형인지 파악해야 한다.
그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토하고, 이와 같은 알고리즘으로 해결할 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려할 수 있을 것이다. 물론 최적 부분 구조, 부분 문제의 중복 두 가지 조건은 만족해야 한다.
다이나믹 프로그래밍으로 해결 해야겠다고 결정한 뒤에는 일단 재귀 함수(Top-down)로 비효율적인 완전 탐색 프로그램을 작성한 뒤에 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선한다.
일반적인 코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다는 것을 명심하자.
특히 오프라인의 면접 과정 등에서 문제를 제시하는 경우, 더욱 쉬운 난이도로 잘 알려진 문제를 출제하는 경우가 많다.
왜냐하면 다이나믹 프로그래밍 문제를 해결할 때, 문제의 점화식을 떠올리는 과정에서 많은 시간이 소요될 수 있기 때문이다.
다시말해, 다이나믹 프로그래밍 문제는 처음 접했을 때 어렵다고 느낄 수 있으며, 헷갈릴 수 있는 여지가 많지만 반복적인 연습을 통해 많은 문제를 접하다 보면 이 유형에 익숙해질 수 있을 것이다.
최근댓글