천천히 빛나는

1. 개미 전사 개미 전사를 위해 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하는 문제이다. N=4일 때 식량을 선택할 수 있는 경우의 수는 8가지이다. 최적의 해는 7번째(3+5=8)가 된다. a_i를 i번째 식량창고까지의 최적의 해라고 정의하도록 하겠다. i번째 식량창고에 대해서 털지 안 털지의 여부를 결정하기 위해서는 2가지 경우 중에서 더 많은 식량을 털 수 있는 경우를 선택하면 된다. int n; int food[101]; int dp[101]; int main() { cin >> n; for (int i = 1; i > food[i]; } dp[1] = food[1]; dp[2] = max(food[1], food[2]); for (int i ..

참고 영상: https://www.youtube.com/watch?v=5Lu34WIx2Us 다이나믹 프로그래밍 (Dynamic Programming, 동적 계획법) 메모리를 적절히 사용하여 수행 시간 효율성을 향상시키는 방법 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 나중에 해당 결과가 필요할 때 기록된 결과를 그대로 사용한다. 다이나믹 프로그래밍의 구현은 탑다운(하향식)과 보텀업(상향식) 방식으로 구성된다. 다이나믹 프로그래밍을 사용하는 조건은 다음과 같다. 1. 최적 부분 구조 (Optimal Substrcture) 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (Overlapping Subpr..