Min IT's Devlog

풀이 일자: 23.02.20 난이도: [Gold V] 분류: [DP, 0-1 Knapsack] 문제 내용 => 일반적인 Knapsack Problem 문제이다. 문제 해결 흐름 1. 무게당 가치를 각각 계산해서 Greedy하게 처리할 수 있지 않을까? → 만약 해당 문제가 fractional knapsack이었다면 가능하지만 0-1 Knapsack 즉, 물건을 쪼갤 수 없는 상태이기 때문에 Greedy알고리즘으로 처리할 수 없다. 주어진 예제를 보면 바로 확인이 가능한데. MaxWeight = 7이고 (6,13), (4,8), (3,6), (5,12)의 (weight, value)쌍이 존재한다면.. 각 무게당 value 계산시 13/6 = 2.1 8/4 = 2 6/3 = 2 12/5 = 2.4 으로 Gr..

풀이 일자: 23.02.17 난이도: [골드 V] 분류: [Math, DP] 문제 내용 문제 해결 흐름 1. 이것도 대표적인 DP문제 중 하나로 DP문제에서 가장 중요한 것은 점화식을 찾는 게 중요하다. → 한번 N과 K를 차례대로 조정해보면서 직접 경우의 수를 구해보자. K=2 N=3인 경우 0~3사이에 2개의 수를 가지고 3을 만들 수 있는 경우의 수는 0+3 / 1+2 / 2+1 / 0+3으로 경우의 수가 4이다. 이런식으로 계속 채워나가다보면 어떤 패턴을 발견해나갈 수 있는데 바로 현재 위치의 위쪽과 왼쪽의 수를 합하면 해당 경우의 수가 된다는 것을 확인할 수 있게 된다. 이를 코드로 옮겨본다면, N, K = map(int, input().split()); dp = [[1 for i in rang..

풀이 일자: 23.02.16 난이도: [Silver 3] 분류: [DP] 문제 내용 문제 해결 흐름 1. 대표적인 DP문제로 점화식을 뽑아내는 것이 가장 중요하다. → 해당 문제에서 가장 중요한 제약 조건은 시작점을 계단으로 치지 않고 세 계단 연속으로 밟을 수 없다는 것이었다. → 3번째 계단까지는 시작점을 계단으로 계산하지 않는다는 점에서 따로 계산했고 그 이후부터는 점화식을 사용했다. dp[i-2] => 2칸으로 현재 위치로 올라왔을 때 값 dp[i-3] + stair[i-1] => 1칸으로 현재 위치로 올라왔을 때 값 ex. 왜 dp[i-1]로 안했는지에 대한 의문이 든다면? 만약 dp[i-1]이라고 하자.. dp[i-1]은 현재 위치보다 1보다 낮은 계단에 도착했을 때의 최대값이다. 그런데 dp..