0과 1의 쉼터

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-knapsack/description 배낭 채우기 설명 | 코드트리배낭 채우기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약N개의 보석 중 무게가 M이 넘지 않도록 적절히 골라 최대 값어치를 만드는 냅색 문제다.아이디어대표적인 냅색 문제다. N개의 보석에 대해 최대 무게 M ~ 현재 보석의 무게 W[i]에 대한 최댓값을 구해주자.for i in range(N): for m in range(M, w[i] - 1, -1): dp[m] = max(dp[m], dp[m - ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-max-coin-change/description 최대 동전 거슬러주기 설명 | 코드트리최대 동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약종류 N개의 동전을 최대한 많이 사용해서 M을 만들자.아이디어금액 M에서 coin[j]을 뺀 금액을 만들 수 없는 경우가 존재한다. 이를 유의하며 coin[j - 1]를 만드는 수를 이용해 coin[j]를 만드는 수를 구하자.점화식은 다음과 같다.dp[i] : i를 만들기 위해 사용된 동전의 최대 갯수dp[i] = max(dp[i],..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-1-2-5-plus/description 1, 2, 5 더하기 설명 | 코드트리1, 2, 5 더하기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약정수 N을 1, 2, 5로 나타내는 방법의 수를 1e4 + 7로 나눈 나머지를 구하자.아이디어정수 i는 i에서 1, 2, 5를 뺀 수를 나타내는 방법의 수를 전부 더한 것과 같다.i - k(k=1,2,5)이 0 이상인 k들에 대해 점화식은 다음과 같다.dp[i] += dp[i - k]nums = [1, 2, 5]dp[0] = 1for i in..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-the-sum-of-the-subsequences-is-m/description 부분 수열의 합이 M 설명 | 코드트리부분 수열의 합이 M를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약수열 A의 부분 수열 중 합이 M이 되는 경우 중 가장 짧은 길이를 구하자.아이디어0-1 냅색 문제이다. 점화식은 다음과 같다.dp[i] : 합이 i가 되는 부분 수열의 최소 길이동일한 원소를 여러 번 사용하는 것을 방지하기 위해 각 원소에 대해 역순으로 탐색하자.n, m = map(int, input().sp..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-coin-change/description 동전 거슬러주기 설명 | 코드트리동전 거슬러주기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약종류 N개의 동전을 최소로 사용해 M원을 만들자아이디어N, M = map(int, input().split())coin = list(map(int, input().split()))# Please write your code here.INF = int(1e10)dp = [INF] * (M + 1)dp[0] = 0for i in range(1, M + 1): ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/test-being-rich-by-working-part-time/description 알바로 부자 되기 설명 | 코드트리알바로 부자 되기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약여러개의 알바 시작/종료 시간과 임금이 주어졌을 때, 최대한 많은 돈을 벌어보자.아이디어다른 알바가 끝나야. 새로운 알바를 할 수 있다. 입력받은 알바 정보에 대해 종료시간을 기준으로 정렬해주자.점화식은 다음과 같다.dp[i] : i번째 알바를 마지막으로 선택했을 때의 최대 이익n = int(input())jobs = [..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-increasing-and-descreasing-subsequence/description 증가했다가 감소하는 부분 수열 설명 | 코드트리증가했다가 감소하는 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약가장 긴 LIS + LDS를 구하자.아이디어LIS와 LDS를 동시에 구해주자.점화식은 다음과 같다.dp[state][i] : i번째 요소로 끝나는 LIS 또는 LDS의 최대 길이LIS, LDS를 비교하며 최댓값을 LDS에 기록해 하나의 부분 수열에 대한 최대 길이로 계산하자...

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-select-segments-without-overlap-2/description 겹치지 않게 선분 고르기 2 설명 | 코드트리겹치지 않게 선분 고르기 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약수직선 상의 N개의 선분을 겹치지 않도록 최대한 많은 선분을 선택하자.아이디어우선 주어진 선분이 정렬되어있다는 보장이 없다.정렬을 한 후 임의의 선분에 대해 이전 선분을 선택했을 때보다 더 많은 선분을 선택할 수 있는지 확인해야 한다.점화식은 다음과 같다.dp[i] : i번째 선분의 끝 ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-increasing-sequence-2d/description 2차원 최대 증가 수열 설명 | 코드트리2차원 최대 증가 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N * N 행렬에서 (1, 1)에서 오른쪽 아래 어느 범위로든 현재 칸보다 더 큰 숫자로 최대한 많이 점프하자.아이디어N, M이 50으로 작아 모든 현재 위치에 대해 모든 이전 위치로부터 최대 점프 횟수를 구할 수 있다.점화식은 다음과 같다.dp[i][j] : (i, j)에 도착했을 때 지금까지 ..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximum-number-of-jumps/description 풀이문제 요약각 요소의 수 arr[i]에 대해 1 ~ arr[i] 만큼 앞으로 건너뛸 수 있을 때 최대한 많이 점프하는 횟수를 구하자.아이디어점화식은 다음과 같다.dp[i] : i번째 요소에서 1 ~ arr[i] 만큼 점프해서 갈 수 있는 최대 점프 횟수주어진 배열의 반대부터 계산하면 쉽게 해결할 수 있다.만약 arr[i]이 0보다 크면 1칸 이상 점프가 가능하다.i + 1 부터 min(i + arr[i] + 1, n - 1)까지 점프 할 수 있으므로 이 중 최댓값을 찾아서 점프해주며 dp[0]까지 진행하자.n = i..