동적 계획법(DP)
1. 정의
- 특정 범위까지의 값을 구하기 위해서 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘
- 이미 과거에 구한 값을 활용하여 불필요한 계산을 하지 않는다.
2. DP 언제 쓸까?
1. 최적의 정답을 찾을 때 : (~가능한) 최대값 또는 최소값.
2. 정답의 수를 세야 할 때 : 문제를 해결할 수 있는 경우의 수를 세고 싶을 때.
3. 방법론
- 탑다운(top-down) : 메모이제이션을 사용한 재귀 호출 방식.
- 바텀업(bottom-up) : 반복문(for문)을 사용, 일반적으로 점화식을 한 눈에 나타내기에 가독성이 좋다.
이건 한번 검색해서 보시면, 느낌이 오실겁니다!
https://blog.naver.com/kks227/220777103650
동적 계획법(Dynamic Programming) (수정: 2019-02-07)
안녕하세요. 오늘 소개해 드릴 것은 바로 그 유명한 다이나믹 프로그래밍(Dynamic Programming)입니다. ...
blog.naver.com
4. 대표 유형
1. 최적의 정답 : 최대 or 최소 구하기
11047번: 동전 0
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
www.acmicpc.net
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
12865번: 평범한 배낭
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)
www.acmicpc.net
2. 경우의 수
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
2293번: 동전 1
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [BOJ/백준] 7453번 - 합이 0인 네 정수 (0) | 2023.02.04 |
|---|---|
| [BOJ/백준] 14502번 - 연구소 C++ 문제 풀이(시간 초과 포함) (0) | 2021.10.03 |
| 다익스트라 알고리즘(Dijkstra's Algorithm) (0) | 2021.09.12 |
| [BOJ/백준] 10451번 - 순열 사이클 (0) | 2021.08.23 |
| [BOJ/백준] 11053번 - 섬의 개수 (0) | 2021.08.23 |
