Dynamic Programming이란?
1. Dynamic Programming(동적 계획법) 이란?
큰 문제를 작은 문제로 나누어 푸는 문제
1.1 Divide&Conquer(분할정복) 과 다른 점은?
거의 비슷하지만 결정적 차이가 있다. 작은 문제가 중복이 일어나나는 아닌지
분할 정복
- 큰 문제를 해결하기 어려워 단순히 작은 문제로 나누어 푸는 방법
- 작은 문제에서 반복이 일어나는 부분이 없다
DP
- 작은 부분 문제들이 반복되는 것(답이 바뀌지 않는다.)을 이용해 풀어나는 것
1.2 Dynamic Programming 방법
모든 작은 문제들은 한 번만 풀어야함.
정답을 구한 작은 문제들을 어딘가에 메모해놓고
다시 그보다 큰 문제 풀어나갈 때 똑같은 작은 문제가 나타나면
앞에서 메모한 작은 문제의 결과값 이용
1.3 Dynamic Programming의 조건
- 작은 문제가 반복이 일어나는 경우
- 같은 문제는 구할 때마다 정답이 같은 경우
이 조건 만족할 때만 DP 사용할 수 있다.
1.4 Memoization?
Memoization : 작은 문제들이 반복되고 이 작은 문제들의 결괏값이 항상 같으니 한번 계산한 작은 문제를 저장해 놓고 다시 사용하는 것
피보나치를 예로 들 수 있다.
재귀함수(Recursive)로 푼다면?
훨씬 간단하지만 n이 증가함에 따라 호출되는 함수의 수 기하급수적으로 증가해 일정 수 이상의 순열 구하기 어렵
def memoization_fibo(n):
memo[0] = 1
memo[1] = 1
if (n < 2)
return memo[n]
for i in range(2, n+1):
memo[i] = memo[i-2]+ memo[i-1]
return memo[n]
if __name__ == '__main__':
n = int(sys.stdin.readline())
memo = [0 for i in range(n+2)]
print(memoization_fibo(n))
1.5 장점 단점
DP는 모든 방법 일일이 검토해 최적의 해를 찾아내는 방식의 알고리즘으로 그리디 알고리즘과 대비된다.
그리디 알고리즘은 모든 해 구하지 않고 그 순간에서의 최적의 해 찾는 방식
닥치는 순간만을 고려해 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 순 없다.
DP는 모든 방법을 검토해 보고 결과적으로 효율적인 값 택
DP가 그리디 보다 시간이 오래 걸리지만 결과적으론 항상 최적의 해를 구할 수 있다는 장점있다.
2. Bottom-up 과 Top-down
2.1 구현 방법
1.Bottom-up
작은 문제부터 차근 차근 구해나가기
2. Top-down
재귀함수로 구현하는 경우가 대부분 top-down
큰 문제를 풀 때 작은 문제가 풀리지 않았다면 그때 작은 문제를 해결
둘 중 뭐가 좋을지는 정답 없음
bottom-up 풀기 쉽지만 가독성 저하
top-down은 소스 가독성 증가 but 작성 어렵
팁?
큰 문제가 있을 때 그것의 가장 작은 문제부터 생각해보자
작은 문제 해결해서 규칙 찾고 작은 문제들 답 가지고 점화식 도출해보자
참고 사이트
velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP