DP
(Dynamic Programming) ; 동적 계획법. 한 가지 문제에 대해서, 단 한번만 풀도록 만들어주는 알고리즘
조건
- 작은 문제에서 반복이 일어남
- 같은 문제는 항상 정답이 같음
예시 문제
https://www.acmicpc.net/problem/2133
2133번: 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
www.acmicpc.net
https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [알고리즘] 비트마스크 (0) | 2022.06.06 |
|---|---|
| [알고리즘] 다익스트라 (0) | 2022.06.06 |
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 해싱(자료구조 기말고사 공부 정리) (0) | 2022.05.30 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 그래프 (0) | 2022.05.22 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
DP
(Dynamic Programming) ; 동적 계획법. 한 가지 문제에 대해서, 단 한번만 풀도록 만들어주는 알고리즘
조건
- 작은 문제에서 반복이 일어남
- 같은 문제는 항상 정답이 같음
예시 문제
https://www.acmicpc.net/problem/2133
2133번: 타일 채우기
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
www.acmicpc.net
https://www.acmicpc.net/problem/11722
11722번: 가장 긴 감소하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}
www.acmicpc.net
'알고리즘' 카테고리의 다른 글
| [알고리즘] 비트마스크 (0) | 2022.06.06 |
|---|---|
| [알고리즘] 다익스트라 (0) | 2022.06.06 |
| [알고리즘] 선형 리스트(Stack, Queue, Deque) (0) | 2022.06.06 |
| [알고리즘] 해시 (0) | 2022.06.06 |
| [알고리즘] 해싱(자료구조 기말고사 공부 정리) (0) | 2022.05.30 |
| [알고리즘] 탐색 (0) | 2022.05.29 |
| [알고리즘] 그래프 (0) | 2022.05.22 |
| [알고리즘] 연결 리스트 (0) | 2022.05.21 |
