다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍이란 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 이는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있다.
1. 최적 부분 구조 (Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 한다.
다이나믹 프로그래밍에서는 메모이제이션(Memoization)이 사용된다. 이는 이미 계산한 결과를 배열에 저장하여 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기 위한 것이다.
다이나믹 프로그래밍을 이용하여 알고리즘 문제를 푸는 절차는 다음과 같다.
- 반복적인 시행을 통해 규칙성을 찾는다.
- 규칙성을 바탕으로 점화식을 만든다.
- 탑다운 방식 또는 바텀업 방식의 다이나믹 프로그래밍을 구현한다.
https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
https://www.acmicpc.net/problem/9084
9084번: 동전
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는
www.acmicpc.net
'SW사관학교 정글 > 정글 TIL' 카테고리의 다른 글
| [Pintos Project] User Programming - Argument Passing (1) | 2022.11.29 |
|---|---|
| [Pintos Project] Alarm Clock and Priority Scheduling (6) | 2022.11.17 |
| [WEEK 03] 백준 21606번 - 아침 산책 (Python) (0) | 2022.10.10 |
| [WEEK 03] 백준 5639번 - 이진 검색 트리 (Python) (0) | 2022.10.07 |
| [WEEK 03] 백준 5094번 - Moo 게임 (Python) (0) | 2022.10.06 |
