다이나믹 프로그래밍이란 동적 계획법이라고 한다. 간단히 설명하자면 어떠한 문제를 한번에 해결하기 어렵기 때문에 작은 문제로 쪼개어 작은것 부터 하나씩 해결하여, 마지막에 문제를 해결하는 것이다.
솔직히 무슨 말인지 바로 와닿지 않는다.
그러나 원래 모를때는 일단 들으면서 알때까지 자료를 찾아보면 얼추 이해가 되기 마련이다.
다이나믹 프로그래밍에는 2가지가 존재한다.
1. Bottom-up : 작은 문제를 처음부터 풀어가는 방식이다. 주로 점화식을 세우고 for 구문으로 빠르게 해결해준다.(리스트나 배열에 직관적으로 구할 수 있는 값들이 넣어넣고 for 구문을 시작한다.)
2. Top-down : 재귀함수로 주로 구현하기 때문에 큰 문제를 풀기위해 작은 문제로 파고들어가서 작은 문제를 해결하면서 큰문제를 해결하는 방식이다. 주로 재귀함수를 돌릴때 메모이제이션 기법을 이용해서 재귀함수의 불필요한 연산을 제거한다.
(*메모이제이션 : f(n)의 결과를 리스트나 배열에 저장하여 필요할때 바로바로 꺼내 쓸수 있게 만드는 기법)
다이나믹 프로그래밍의 조건
1. 작은 문제가 반복되어야한다.
2. 반복되는 문제의 정답은 동일해야 한다.
=> 결국 이말이 점화식을 세울 수 있다는 소리같다.
일단은 여기까지 쓰고 다음에 더 깊이 알아봐야겠다.
'알고리즘' 카테고리의 다른 글
백준 10844 풀이 (쉬운 계단수, 다이나믹 프로그래밍) (0) | 2021.02.21 |
---|---|
백준 2579 풀이 (다이나믹 프로그래밍, bottom-up, 계단 오르기) (0) | 2021.02.19 |
백준 1932 풀이 (동적 계획법) (0) | 2021.02.19 |
백준 1149 풀이 (다이나믹 프로그래밍) (0) | 2021.02.19 |
백준 9461 풀이 (파도반 수열, 메모제이션, 다이나믹 프로그래밍) (0) | 2021.02.19 |