🖥 dev-ruby

문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 풀이 function solve() { const aDp = [1, 0]; const bDp = [0, 1]; for (let i = 2; i < d; i++) { aDp[i] = aDp[i - 1] + aDp[i - 2]; bDp[i] = bDp[i - 1] + bDp[i - 2]; } const aCoef = aDp[d - 1]; const bCoef = bDp[d - 1]; f..

문제 (https://www.acmicpc.net/problem/14501) 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다..

문제 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) 그런..