| 작성자 | 이재영 |
| 일 시 | 2024. 10. 29 (화) 18:00 ~ 21:00 |
| 장 소 | 미래관 429호 자율주행스튜디오 |
| 참가자 명단 | 임혜진, 이재영, 성창민, 김명원, 장원준 |
| 사 진 |  |
목차
- DP란?
- DP의 특징
- DP 문제를 푸는 법
이번 주차에 파이썬을 사용한 알고리즘을 공부해보려고 한다. 알고리즘 때 DP를 공부하는데 뭐가 뭔지 감은 잡히는데 실제 문제에 적용시키는 것에 어려움을 많이 느꼈다. 그래서 이번 주차부터 파이썬을 사용한 알고리즘을 시작해보려고 한다.
1. DP란?
DP(Dynamic Programming)은 주어진 문제를 해결하기 위해 큰 문제를 여러 개의 작은 문제로 나누고, 각 작은 문제의 해답을 저장하여 중복 계산을 피하는 알고리즘 기법이다. 주로 최적의 해를 찾는 문제에 사용되며, 부분 문제 최적화와 중복 계산 방지라는 개념을 활용한다.
예를 하나들면 피보나치 수열이 있다. 피보나치 수란 연속된 두 수의 합이 다음의 수가 되는 수열을 말한다. (0, 1, 1, 2, 3, 5, ...) 여기서 n번째 피보나치 수를 구하기 위해서 보통 재귀함수를 많이 사용하는데 코드는 다음과 같다.
def fib(n):
if n <= 1: return n
return fibo(n-1) + fibo(n-2)
그러나 위에 코드는 매우 매우 비효율적이다. 그 이유는 다음 사진을 통해 설명하겠다.
위 사진을 보면 알다시피 fib 함수는 재귀함수를 통해 호출되는데 그 과정에서 중복되는 호출이 너무 많은 것을 볼 수 있다. 고작 5번째 피보나치 수열을 찾는데도 fib(2)가 3번, fib(1)은 5번이 호출되는 것을 볼 수 있다. 때문이 이것을 DP를 사용해서 코딩을 한다면 보다 더 효율적인 코드가 될 수 있다. 여기서도 2가지 정도의 방식이 있는데, 바로 재귀 호출을 통해 계산하고 이미 계산한 값을 메모리에 저장해 중복 계산을 피하는 방식은 메모이제이션과 작은 문제부터 계산해 나가면서 배열에 저장해 최종 결과를 얻는 방식인 타뷸레이션이다.
# 메모이제이션 코드
dp = [-1] * 1001
def fibo(n):
if dp[n] != -1: return dp[n]
if n <= 1: return n
dp[n] = fibo(n-1) + fibo(n-2)
return dp[n]위 코드처럼 메모이제이션은 추가적인 메모리를 사용해서 이미 계산한 값을 저장하는 식의 형태를 보여준다.
dp = [0, 1] + [-1] * 1001
n = 30
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]위 코드는 타뷸레이션 방식을 보여주는 코드로, 30번째 피보나치 수를 구하기 위해 작은 값부터 계산해 나가면서 결과를 얻는 형태를 보여준다.
위 결과값은 fibo(30)을 각각 재귀함수와 메모이제이션, 타뷸레이션 방식을 실행시켰을 때 실행 속도를 나타낸다. 확연히 빠른 것을 볼 수 있다.
2. DP의 특징
DP가 적용되기 위해서는 다음 두 가지 특징을 만족해야 한다.
1) Optimal Substructure (최적 부분 구조)
- 문제의 최적 해가 부분 문제의 최적 해로 구성될 수 있어야 한다. 즉, 큰 문제를 해결하는 데 필요한 작은 문제들도 최적의 해를 가져야 한다.
- 예를 들어, 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같이, F(n)을 구하기 위해 F(n-1)과 F(n-2)의 최적 해가 필요하다.
2) Overlapping Subproblems (중복되는 부분 문제)
- 동일한 부분 문제가 여러 번 반복되어 계산되는 경우가 있어야 한다. DP는 이러한 중복되는 문제를 한 번만 계산하고 저장하여 성능을 향상시킨다.
- 피보나치 수열에서 F(n) = F(n-1) + F(n-2)을 재귀적으로 계산할 경우, F(k) 값을 여러 번 중복해서 구하게 되지만, DP는 이를 방지한다.
3. DP 문제 푸는 법
DP 문제를 풀기 위해서는 우선, 지금 해결하려고 하는 이 문제가 과연 DP의 특징을 만족하는 가? 를 잘 파악하여야 한다. 이것이 제일 우선이다. 조건이 만족되었다면 기본적인 단계를 거쳐보자.
1) 문제 분석 및 부분 문제 정의
- 문제를 해결하기 위해 큰 문제를 어떻게 작은 문제로 나눌 수 있을지 생각한다. 주로 배열이나 함수로 현재 상태를 표현한다.
2) 점화식 도출
- 현재 상태를 이전 상태의 값들을 이용해 표현할 수 있도록 점화식을 도출한다. 점화식은 문제의 최적 부분 구조를 나타내는 핵심 요소이다.
- 예를 들어, 피보나치 수열에서 F(n) = F(n-1) + F(n-2)와 같은 식을 세우는 것을 말한다.
3) 메모이제이션 or 타뷸레이션
- 메모이제이션과 타뷸레이션 방식 중 어떠한 방식을 사용할지 생각한다. 메모이제이션은 가독성이 좋지만, 타뷸레이션은 속도가 보통 더 빠르다.
4) 초기 조건 설정
- DP 테이블의 시작점인 초기 값들을 설정한다. 문제마다 적절한 초기값 설정이 필요하며, 이는 재귀의 종료 조건이나 Bottom-Up 방식에서 첫 번째 값을 정의하는 것으로 시작한다.
- 피보나치 수열로 예시를 들자면 dp = [0, 1] * [-1] * 1001 과 같이 초기에 값들을 넣어놓는 것과 if dp[n] != -1: return dp[n] 과 같이 종료 조건을 설정하는 것을 말한다.
이번 모각코에서는 DP에 대해서 알아보았다. 다음 모각코 때는 DP를 이용해서 다양한 문제를 풀어볼 예정이다.