병아리 개발자의 실력 양성기

서로 다른 동전으로 목표합을 구하는 방법의 수를 구하는 문제이다. 다만, 하나는 같은 동전 조합이면 순서가 달라고 1가지로 치고(조합), 나머지는 순열을 구하는 문제이다. 조합문제 https://leetcode.com/problems/coin-change-2/ Coin Change 2 - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 순열문제 https://leetcode.com/problems/combination-sum-iv/ Combination Sum I..

많은 변형을 양산하는 구조이다. 컨셉을 제대로 이해할 필요가 있다. 결론적으로, DP 이지만 더 발전된 형태로 풀도록 하는 것이 요즘의 경향인 것 같다. 아래 array에서 가장 긴 subsequence (연속될 필요는 없는 배열 원소들의 부분 수열) 의 길이를 찾는 문제가 있다고 하자. nums = [5, 6, 7, 8, 1, 2, 3] https://leetcode.com/problems/longest-increasing-subsequence/ Longest Increasing Subsequence - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and..

아내에게 한도가 무한대인 카드와, 정해진 무게를 넘어서 담으면 찢어져 버리는 가방을 하나 주었다. 아내는 물건이 종류당 1개씩 있는 가게에 가방을 들고 가서 값어치 있는 물건들을 최대한 많이 가방에 담아서 나오려고 한다. 물건은 당연히 쪼갤 수도 없고, 정해진 용량을 넘을 수 없다. 이것이 바로 0/1 냅색 문제이다. 첫번째 해: top down DP stack overflow 때문에 일부러 @lru_cache는 쓰지 않고 table을 만들었다. Item = collections.namedtuple('Item', ('weight', 'value')) def optimum_subject_to_capacity(items: List[Item], capacity: int) -> int: # i: 1:i th i..

https://cses.fi/problemset/result/3889109/ https://cses.fi/problemset/result/3889109/ cses.fi 이 문제는 주어진 숫자 n이 가진 각 자리의 수 중에서 하나씩 빼어서 0이 되는 최소의 연산 수를 구하는 것이다. 즉, 최적해는 27→20→18→10→9→0.으로 총 5번의 연산이 최소한 필요하다. 여기서 dp[x]를 x라는 수를 0으로 만들기 위한 최소의 연산 수라고 정의하자. 우선, 27의 자리의 수는 2, 7이다. 그러므로 dp[27]을 구하려면, dp[25], dp[20] 으로 가는 2가지 경우가 있다. 그리디로 풀자면 dp[20]으로 무조건 가면 되지만, dp로 풀자면 두 경우를 모두 계산해서 비교해봐야 한다. 단, 주의할 것은,..

https://cses.fi/problemset/task/1636/ CSES - Coin Combinations II cses.fi 이 문제는 목표값을 만들기 위해 필요한 동전의 순열이 아닌 조합의 개수를 구하는 문제이다. 예를 들면, Input: 3 9 2 3 5 Output: 3 이렇게 되어야 한다. 이 문제의 아이디어는, 목표값을 향해 1씩 숫자를 증가하면서, 모든 가능한 동전의 경우를 차례로 따져보는 것이다. 예를 들어, 위 문제를 풀기 위해서는 다음의 dp 표를 채운 뒤, dp[3][9] 값을 읽으면 된다. i\j 0 1 2 3 4 5 6 7 8 9 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 2 1 0 1 1 1 1 2 1 2 2 3 1 0 1 1 1 2 2 ..

https://cses.fi/problemset/task/1635 CSES - Coin Combinations I cses.fi 오늘 문제는 동전 액면 집합이 주어질 때 목적한 금액(x)을 만들기 위한 동전 순열의 가지수(dp(x)라 부르자)를 구하는 것이다. 문제에선 조합이라고 했지만 같은 동전 조합의 순서가 다른 경우를 따로 센다. 발상만 정하면 쉽다. 만일 동전 액면 집합 coins = {2,3,5} 에 대해 11을 만들려고 하면, 2, 3, 5를 맨 나중 고른 경우가 모두 상이한 조합이 될 것이며, 이를 제외한 목표값에 대한 부분문제로 recurse 할 수 있다. 그러면 dp(11)은, dp(11) = dp(11-2) + dp(11-3) + dp(11-5) 가 된다. 이를 코드로 짜면 # Coin..

먼저 AtCoder의 문제를 보자. 가장 기본적인 피보나치 계열 문제다. A - Frog 1 (atcoder.jp) A - Frog 1 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 첫 계단부터 마지막 계단까지(높이는 단조증가하지 않음) 1칸 혹은 2칸씩 걸을 수 있을때 최소의 이동거리(변위)의 합은? 여기서 이동거리는 이동하는 계단 사이의 높이의 차(절대값)을 말한다. bottom-up 방식을 택했다. 코드 1. 맨 앞의 N은 계단의 갯수를, h는 계단의 높이들을 저장한 배열이다. 오답(WA). N = int(inpu..

코인 문제 경우 1. 정해진 금액을 가장 적은 수의 코인(동전)으로 구성하는 문제를 풀 때(단 각 동전 액면은 무한히 사용 가능), 1, 2, 5, 10, 20, 50, 100, 200 cents 로 되어 있는 유로화 코인이나 1, 5, 10, 50, 100, 500으로 된 원화 동전은 가장 큰 액면부터 차례로 채우면 최적해를 구할 수 있다. 두 경우 모두 뒤의 액면 중에는 이전 액면의 배수가 존재하므로 어느 액면이나 그 전단계의 동전을 통해 구할 수 있고, 이런 경우는 가장 큰 코인부터 답에 포함하게 된다면, 더 적은 액면으로 구성한 뒤 더 큰 액면으로 바꾼 결과와 다름이 없어 최적해가 되는 것이다. 예를 들어 1520원을 구성하고 싶으면 500 * 3 + 10 * 2 이렇게 5개 동전이 최적해이다. ..

DP의 핵심요소는 메모이제이션(캐싱)이라고 할 수 있다. 이미 계산한 결과를 저장하는 재귀라고도 할 수 있다. 기억 공간을 반복될 계산결과의 저장에 할당함으로써 귀중한 연산시간을 절약하는 것이다. DP를 이용해 해결할 수 있는 대표적이며 가장 간단한 예로 피보나치 수열이 있다. 어떻게 이 문제가 재귀, top-down DP, bottom-up DP, 그리고 그 기억공간을 추가로 절감하는 방식으로 수행되는지를 살펴본다. 재귀 피보나치 수열은 수학적으로 다음 점화식(recurrence relation)으로 정의된다. $$ f_n = f_{n-1} + f_{n-2} $$ $$ f_0 = 0; \ f_1 = 1 $$ n번째 수를 구하기 위해서는 n-1번째, n-2번째 수를 알아야 하고, 그들을 알기 위해서는 다..