이것저것
[개념] 다이나믹 프로그래밍 (Dynamic Programming) 본문
다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍이라고 쓰면 좀 길어서 줄여서 DP라고도 많이 부른다. 이 글에서도 줄어서 그냥 DP라고 적겠다.
DP 문제를 여러 작은 문제(subproblem)들로 나누고 작은 문제의 계산결과를 이용하여 다음 작은 문제의 결과를 찾아가는 것을 반복하여 최종 정답을 찾아가는 알고리즘이다.
DP 문제를 푸는 과정은 다음과 같다.
- 문제의 해답을 찾기 위한 문제풀이과정을 생각한다.
- 문제풀이 과정 중 반복되는 연산은 결과값을 메모리에 저장하고 이를 다음 연산에 이용하도록 한다. (메모이제이션)
- 코드를 작성하고 해답을 찾는다.
아래글의 예시를 보면 DP가 어떤 알고리즘인지 어떻게 풀어야하는지 감을 잡기가 쉽다.
[백준] 2579번 - 계단 오르기
https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.ne..
hojun.xyz
※ Introduction to algorithms 3판을 참조하였다.
'스터디 > Algorithm' 카테고리의 다른 글
| [백준] 1208번 - 부분수열의 합 2 (0) | 2023.12.24 |
|---|---|
| [개념] DFS/BFS (0) | 2022.09.26 |
| [개념] 이분탐색 (Binary Search) (0) | 2022.09.25 |
| [백준] 2579번 - 계단 오르기 (0) | 2022.09.17 |
| [백준] 1114번 - 통나무 자르기 (0) | 2022.08.02 |
'스터디/Algorithm' Related Articles
more
