🖥 dev-ruby

문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 function solution(N, price){ let dp = [0, ...price]; for(let i = 2; i +el); console.log(solution(N, price)) 처음에 일일이 N개를 뽑을 수 있는 조합의 경우 수를 다 구했는데, 아무리봐도 좀 더 쉽게 풀 수 있을 것 같았다. 위 코드는 각 i마다 i개씩 뽑을 수 있는 경우의 수 별로 최댓값을 계속 업데이트 해주..

동적계획법(Dynamic Programming)은 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. dp의 핵심은 "메모이제이션" 기법인, 이미 계산된 결과를 별도의 메모리에 저장하여 필요한 경우 다시 계산하지 않고 사용하는 방식이다. 작은 문제들이 계속 반복되고, 그 작은 문제의 결괏값은 항상 같을 때 DP 알고리즘 적용할 수 있다. 가장 대표적인 예로 피보나치 수열을 들 수 있다. 피보나치 수열 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ... 피보나치 수열을 구할 때는 재귀를 쓴다. 다음과 같이 이전 결과와 전전 결과의 합으로 계속 구해나가는 방식이다. return f(n) = f(n-1) + f(n-2) 그런..