동적 계획법 1 단계

단계	문제 번호	제목	정보	정답	제출	정답 비율
1	24416	알고리즘 수업 - 피보나치 수 1		19244	33461	58.387%
재귀 호출에 비해 동적 계획법이 얼마나 빠른지 확인해 봅시다.
2	9184	신나는 함수 실행	다국어	26997	59063	44.005%
재귀 호출만 생각하면 신이 난다! 아닌가요?
3	1904	01타일		43027	128733	32.362%
점화식의 값을 특정 상수로 나눈 나머지를 구하는 문제
4	9461	파도반 수열	다국어	61695	136305	43.928%
피보나치 수와 비슷한 규칙을 찾아 동적 계획법으로 푸는 문제
5	1912	연속합		69096	173558	38.631%
동적 계획법으로 합이 최대인 부분배열을 구하는 문제
6	1149	RGB거리		84833	144086	57.777%
i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의해봅시다.
7	1932	정수 삼각형	다국어	71297	118937	60.529%
각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제
8	2579	계단 오르기		90447	250794	35.271%
i번째 계단에 오를 때, 몇 개의 연속한 계단을 올랐는지를 고려하여 부분문제를 정의해봅시다.
9	1463	1로 만들기		137641	385260	34.167%
메모이제이션으로 N을 1로 바꾸기 위해 주어진 연산을 몇 번 사용하는지 계산하는 문제
10	10844	쉬운 계단 수		59169	178104	31.703%
동적 계획법을 이용해 계단 수를 구하는 문제
11	2156	포도주 시식		60716	173568	33.402%
규칙에 따라 포도주를 마실 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제
12	11053	가장 긴 증가하는 부분 수열		88463	213916	39.126%
LIS(Longest Increasing Subsequence)를 구하는 문제
13	11054	가장 긴 바이토닉 부분 수열		36349	69168	52.078%
LIS 응용 문제 1
14	2565	전깃줄		25245	50676	49.441%
LIS 응용 문제 2
15	9251	LCS		50302	115450	42.771%
LCS(Longest Common Subsequence)를 구하는 문제
16	12865	평범한 배낭		75107	188480	37.652%
대표적인 DP 문제 중 하나인 "냅색 문제"

문제

문제

출처

ICPC

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말