dvpzeekke

문제 링크입니다. https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이방법 다이나믹 프로그래밍 기법을 사용해 문제를 해결합니다. DP 문제를 풀 때에는 점화식을 세우는 게 중요합니다. 이 문제의 점화식은 solve 함수의 for loop에 해당합니다. 수익이 상담이 마쳐진 다음날 들어온다고 가정했을 때, dp[i]은 i번째 날에 가질 수 있는 최대 금액입니다. 각 loop은 먼저 i번째 날에 일을 했을 경우를 계산합니다. i번째 날에 일을 했을 경우엔 i + t[i] 날에 수익이 들어옵니다. 따라서 dp[i + t[i]]을 새롭게 계산해줍니다. 그리고 다음 loop으로 넘어가기 전..

문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 1..

문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 입출력 예 n result 4 5 ..

다이나믹 프로그래밍과 메모이제이션 알고리즘을 비교해보겠습니다. 다이나믹 프로그래밍은 모든 subproblem들을 전부 구해야하는 문제에 적용하면 좋습니다. 메모이제이션은 모든 subproblem들을 전부 구해야하는 경우, stack에서 왔다갔다하는 overhead가 있기 때문입니다. 반면, 메모이제이션은 subproblem을 전부 다 계산하지 않아도 되는 문제에 적용하면 좋습니다. 이전에 계산한 결과를 다시 계산할 필요가 없기 때문입니다. 코드를 통해 비교 및 이해를 해보도록 하겠습니다. 피보나치 수열을 다이나믹 프로그래밍과 메모이제이션으로 각각 구현해보겠습니다. 먼저 다이나믹 프로그래밍 기법을 이용한 피보나치 수열 구현 방법입니다. int fibonacci(int n) { if (n < 2) { ret..