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

위상정렬 (topological sorting)은 DAG에서 DFS 탐색 순서대로 노드의 값을 나열하는 것을 말한다. DFS는 어느 source 노드를 먼저 탐색할지를 임의로 정할 수 있기 때문에 다양한 위상정렬이 있을 수 있지만 '탐색 순서대로' 라는 규칙은 맞아야 한다. 일반적인 해법은 각 노드에 대해 탐색 상태를 저장하는 배열을 하나 만들고, DFS를 하면서, 배열에 다음과 같이 값을 기록한다. state 0 (white) : 노드가 아직 처리되지 않음 state 1 (light gray) : 노드가 처리되는 중임(visiting) state 2 (dark gray) : 노드가 처리 완료 됨(visited) 처리 완료라는 말은 모든 후속 노드가 처리가 되었다는 뜻이다. 그럼 모든 후속 노드가 처리되..

많은 변형을 양산하는 구조이다. 컨셉을 제대로 이해할 필요가 있다. 결론적으로, 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..

벽으로 둘러싸인 공간, 즉 방의 갯수를 구하는 Counting Rooms 라는 문제가 있다. https://cses.fi/problemset/task/1192/ CSES - Counting Rooms cses.fi 이는 DFS의 응용 형태로 푸는 것이다. DFS는 한 점에서 출발해 닿을 수 있는 미 방문점을 모두 방문하는 것이다. 방문할 때 마다 방문된 점을 표시하되 끝까지 방문이 되면 돌아온다. 이와 유사한 과정인 backtracking은 방문시마다 어떤 조건에 대해 확인하는 절차를 거쳐, 그 조건이 만족되지 않으면 방문을 종료하는 것이다. DFS에서 기본적으로 검증하는 조건은 바로 '방문여부'가 된다. 이미 방문된 것은 다시 방문하지 않는다. 이를 위해 방문된 노드에 대한 기호를 모아놓는 일을 set..

https://leetcode.com/problems/slowest-key/ Slowest Key - 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 이런 문제를 보자. 정렬시 두 조건을 차례로 비교하는 문제이다. max도 결국 비교하는 함수이므로 sort와 마찬가지로 key= 를 줄 수 있게 되어 있음을 안다면 쉽게 해결할 수 있다. class Solution: def slowestKey(self, releaseTimes: List[int], keysPresse..

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개 동전이 최적해이다. ..