DP 검색 결과
2 개의 검색 결과가 있습니다.
ProblemSolving

[BOJ] 1106_호텔

호텔 문제 링크: https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net i를 i개의 손님 유치 수라 하자. dp[i]는 손님 유치를 하는데 드는 최소비용이라고 정의할 수 있다. 현재 상태의 손님 유치의 수를 c라 하면, 다음의 단계에서 들었던 비용과 현재의 비용의 합이 c를 유치하는데 드는 비용이 된다. 그 중 가장 최소인 값이 dp[i]의 값이 될 것이다. Dynamic Programming의 방법 중 Top-Down 방식을 채택하여 다음과 같..

2021. 1. 28. 19:32
기타

Dynamic Programming

Dynamic Programming 동적계획법이란: 큰 문제를 작은 문제로 나누어 푸는 방법 언제 쓰는가? 부분 문제 반복 및 최적 부분 구조를 가지고 있는 알고리즘에 사용 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용 왜 쓰는가? 알고리즘을 일반적인 방법에 비해 더 적은 시간 내에 풀기 위함이다. 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토, 그 중 최적의 풀이법을 찾아냄에 있어 효율적 어떻게 쓰는가? 일반적으로 주어진 문제를 풀기 위해, 문제를 여러 하위 문제로 나누어 푼다. 여러 하위 문제를 푼 후, 그 해결책을 저장한다. 이 후 같은 하위 문제가 나왔을 경우 이전의 해결책으로 정리한다. 예를 들어 피보나치 수열을 보자. 일반적인 피보나치 수열의 알고리즘은 다음과 같다. funct..

2021. 1. 27. 20:08