0과 1의 쉼터

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-longest-decreasing-subsequence/description 최대 감소 부분 수열 설명 | 코드트리최대 감소 부분 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 수열에서 가장 긴 감소하는 부분 수열의 길이를 구하자.아이디어점화식은 다음과 같다.dp[i] : i번째 요소로 끝나는 LDS의 최대 길이LIS의 응용문제다. 부등호만 바꾸면 된다.n = int(input())m = list(map(int, input().split()))# Please write yo..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-longest-increasing-subsequence/description풀이문제 요약주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 구하자.아이디어LIS를 구하는 가장 기본적인 문제다.점화식은 다음과 같다.dp[i] : i번째 요소로 끝나는 LIS의 최대 길이현재 위치 i에 대해 이전 위치 0 ~ i - 1 중 현재 위치의 값 m[i]]보다 작고, 지금까지 구한 LIS보다 dp[j] + 1이 더 긴 LIS가 된다면 다음이 성립한다.dp[i] = max(dp[i], dp[j] + 1)n = int(input())m = list(map(int, input().split()))# Ple..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/test-minimax-path-in-square/description 정수 사각형 최댓값의 최소 설명 | 코드트리정수 사각형 최댓값의 최소를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N * N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하는 경로 중 거쳐간 위치의 최대 비용이 최소가 되도록 하자.아이디어점화식은 다음과 같다.dp[i][j] = max(grid[i][j], min(dp[i - 1][j], dp[i][j - 1]))현재 위치 (i, j)보다 (i -..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimum-difference-on-the-integer-grid-2/description 정수 사각형 차이의 최소 2 설명 | 코드트리정수 사각형 차이의 최소 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N * N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하는 경로에 적혀있는 수의 최댓값과 최솟값의 차이를 가장 작게 만들자.아이디어경로의 최대/최소값을 모두 기록하며, 두 수의 차를 최소화 해야한다.점화식은 다음과 같다.dp[i][j][k..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-lis-on-the-integer-grid/description 정수 사각형 최장 증가 수열 설명 | 코드트리정수 사각형 최장 증가 수열를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약N * N 행렬의 임의의 위치에서 값이 커지도록 상하좌우로 이동할 때, 가능한 최대 이동 횟수를 구하자.아이디어임의의 시작점(i, j)에서 DFS를 통해 구한 최대 이동 횟수는, 다른 시작점에서의 탐색 과정에서도 재사용될 수 있다.즉 부분 경로의 결과가 전체 탐색에서 활용된다.점화식은 다음을 나타낸다.dp..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximin-path-in-square/description 정수 사각형 최솟값의 최대 설명 | 코드트리정수 사각형 최솟값의 최대를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N * N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하는 경로 중 거쳐간 위치의 최소 비용이 최대가 되도록 하자.아이디어점화식은 다음과 같다.dp[i][j] = min(grid[i][j], max(dp[i - 1][j], dp[i][j - 1]))현재 위치 (i, j)보다..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-minimum-sum-path-in-square/description 정수 사각형 최소 합 설명 | 코드트리정수 사각형 최소 합를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N*N 행렬에 대해 (1, N)에서 왼쪽/아래로만 이동하며 (N, 1)까지 도달하기 위한 최소 비용을 구하자.아이디어점화식은 다음과 같다.dp[i][j] : 현재 위치 (i, j)에 도달하기 위한 최소 비용주어진 행렬에서 (i - 1, j)와 (i, j + 1)의 비용 중 최소 비용을 골라 현재 위치 (i,..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/intro-maximum-sum-path-in-square/description 정수 사각형 최대 합 설명 | 코드트리정수 사각형 최대 합를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약주어진 N*N 행렬에 대해 (1, 1)에서 오른쪽/아래로만 이동하며 (N, N)까지 도달하기 위한 최대 비용을 구하자.아이디어점화식은 다음과 같다.dp[i][j] : 현재 위치 (i, j)에 도달하기 위한 최대 비용주어진 행렬에서 (i - 1, j)와 (i, j - 1)의 비용 중 최대 비용을 골라 현재 위치 (i, j)..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/test-rectangle-fill-2/description 사각형 채우기 2 설명 | 코드트리사각형 채우기 2를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약2 * N 크기의 사각형에 1 * 2, 2 * 1, 2 * 2 크기의 사각형으로 채우는 방법의 수를 구하자.아이디어점화식은 다음과 같다.dp[i] : 2 * i 크기 사각형을 채우는 방법의 수2 * N을 채우기 위해서는 dp[i - 1]에 2 * 1 사각형 한 개를 붙이는 경우,dp[i - 2]에 12 사각형 두 개를 붙이거나, 22 한개를 붙이는..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-number-of-unique-bst/description 서로 다른 BST 개수 세기 설명 | 코드트리서로 다른 BST 개수 세기를 풀며 문제 구성과 난이도를 파악해 적절한 알고리즘을 선정해보세요. 효율적인 코드 작성을 목표로 합니다.www.codetree.ai 풀이문제 요약1 ~ N으로 이루어진 서로 다른 BST의 개수를 구하자.아이디어서로 다른 BST는 루트 노드에 따라 좌우를 구성하는 서브트리가 달라진다.1 ~ N에 대해 root가 K이면, 왼쪽 서브트리는 1 ~ K - 1, 오른쪽 서브트리는 K + 1 ~ N 노드들을 가진다.점화식은 다음과 같다.dp[i] : 노드 i개로 ..