1. 동적 계획법이란?
DP라고 불리는 동적 계획법은 코딩 테스트에 단골 문제 유형으로 나오고 있다.
코딩 테스트 문제를 풀다보면 아래와 같은 제한사항이 종종 나오곤 한다.
제한사항이 1초이고, 파이썬 기준(정확하지 않습니다) 1초에 2000만 = 20,000,000 번 연산이 가능한데, O(N^2) 으로 알고리즘을 짜게 되면 시간 초과가 발생합니다.
이런 경우 , 주어지는 숫자의 범위가 크고 경우의 수가 엄청난 값의 문제들을 대부분 DP를 이용해서 해결 하곤 합니다.
그렇다면 동적 계획법은 무엇일까?
동적 계획법(dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
2. 동적 계획법의 조건
동적 계획법을 적용하려면 위 정의에서 본 것 처럼 두 가지 속성을 만족 시켜야 하는데,
- 부분 반복 문제(Overlapping Subproblem)
- 이미 계산된 문제가 반복적으로 연산될 때 생기는 문제
- ex) 피보나치 수열
- 최적 부분 구조(Optimal Substructure)
- 최적 부분 구조란,
작은 부분 문제에서 구한 최적의 답으로 합쳐진큰 문제의 최적의 답을 구할 수 있어야 한다는 것이다.
- 최적 부분 구조란,
위 두 가지 속성을 만족 시켜야 한다.
3. 메모이제이션(Memoization)
위의 조건처럼 반복되는 연산 과정을 줄이기 위해서는 어떻게 해야 할까?
이를 해결하기 위해서 메모이제이션(Memoization) 이라는 동적 프로그래밍의 개념이 도입되게 되는데
메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
다시 말해 메모리에 계산한 값을 저장해 나감으로써
다음 반복 수행때는 연산 없이 저장된 값을 불러와 주는 방법이다.
일반적인 피보나치 수열의 재귀 함수를 메모이제이션을 적용하면 아래와 같다.
# 최대 범위 N보다 1 크게 사용하는 리스트 초기화
memo = [0] * 101
# 초기 조건 설정
memo[1] = 1
memo[2] = 1
def fib(n):
# 이미 계산된 값이면 바로 반환
if memo[n] != 0:
return memo[n]
# 아직 계산되지 않은 경우, 재귀적으로 계산
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
위 처럼 구하고자 하는 숫자의 크기 만큼 배열을 생성하고 계산한 값을 저장하
중복되던 연산 과정을 줄일 수 있게 된다.
4. 동적 계획법 접근 방법
동적 계획법으로 문제를 해결 할때는 크게 2가지 접근 방법을 들 수 있다.
Top-Down 방법과 Bottom-Up 방법이 있다.
4.1 Top-Down
- 말 그대로 위에서 아래로 접근하는 방법
- 탑다운 방식은 '하향식'이라고도 한다.
- 점화식을 이해하기 쉬운 장점이 있다.
위에 코드처럼 재귀 호출을 통해 피보나치 수 구하는 방식에 해당한다.
4.2 Bottom-Up
- 가장 작은 문제들부터 답을 구해가며 전체 문제의 답을 찾는 방식
- 바텀업 방식은 '상향식'이라고도 한다.
재귀 호출을 하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있는 장점이 있다.
위에 설명했던 피보나치 수열을 바텀업 방식으로 구현하면 아래와 같다.
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
dp = [0] * 100
dp[1] = 1
dp[2] = 1
n = 99
# 피보나치 수열 반복문으로 구현(Bottom-Up DP)
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n])블로그 참고
https://velog.io/@kimdukbae/%EB%8B%A4%EC%9D%B4%EB%82%98%EB%AF%B9-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D-Dynamic-Programming#%ED%83%91%EB%8B%A4%EC%9A%B4top-down-vs-%EB%B0%94%ED%85%80%EC%97%85bottom-up
https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming
