동적계획법 (2) 썸네일형 리스트형 [SW Expert Academy] 2115. 벌꿀 채취 C/C++ 풀이 이 문제에 꼬박 하루를 썼다면 당신 믿으시겠습니까? 애매하게 아는 것은 확실하게 아는 것보다 위험하다는 격언을 생각나게 해주는 문제였습니다... :) 문제는 모든 가능성을 이용하는 Brute Force인데, 상자 안의 최대 수익을 구하기 위해 DP(동적 계획법)의 테크닉이 필요하다. 동적 계획법은 예전에 포스팅 했으니 참고하세요. (여기로) 동적계획법(1) 동적계획법이란? 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 분할 정복의 알고리즘과 비슷하지만 동적계획법의 chavo-s-it-life.tistory.com M개의 영역 안에서 수익의 최댓값을 구하는 것은 반복적으로 사용되기 때문에 cache 배열에 저장해두면 연산을 빠르게.. 동적계획법(memoization) 동적계획법이란(Dynamic Programming)? 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내는 분할 정복의 알고리즘과 비슷하지만 동적계획법의 각 부분 문제들은 다른 답을 구하는 이용될 수 있기 때문에 계산결과를 재활용함으로써 속도의 향상을 꾀한다. 부분 문제들의 답을 재활용한다는 말이 무슨 말일까? 피보나치 수열 문제로 예를 들어보자! 동적계획법을 이용한 피보나치 수열의 풀이 https://www.acmicpc.net/problem/2748 피보나치 수열은 다들 아는 것처럼 Fn = Fn-1 + Fn-2 (n>=2)의 점화식을 가지고 전개되는 수열이다. 0 1 1 2 3 5 8 13 21 34 ..... n번째 피보나치 수.. 이전 1 다음
