0과 1의 쉼터

[Code Tree] 최대 증가 부분 수열 [Python]

문제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..

[백준 23293] 아주 서바이벌 [Java]

문제23293번: 아주 서바이벌 23293번: 아주 서바이벌 boj.ma 풀이문제 요약게임 로그를 분석해서 주어진 부정행위 조건과, 차단 조건에 해당되는 유저 명단을 출력하면 된다.이동 : 이동의 경우 확인할 조건이 없다. 그냥 이동하자획득 : 현재 위치에 관계없이 일단 아이템을 얻을 수 있다. 만약 위치가 다르다면 부정행위를 기록하자조합 : 가지고 있는 아이템의 수에 관계없이 일단 아이템을 조합할 수 있다. 만약 재료가 없는 경우 부정행위를 기록하자. 이때, 아이템의 수는 0보다 작아질 수 없음에 유의하자.공격 : 다른 지역 플레이어를 공격할 경우 부정 행위/차단 조건에 둘 다 해당된다. 하지만 차단된다 해서 이후 로그를 처리하지 않는 것은 아니다.부정 행위의 로그와, 차단 유저의 번호를 중복없이 오름..

문제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)보다..

문제http://boj.ma/15886 15886번: 내 선물을 받아줘 2 boj.ma 풀이문제 요약1 * N칸에 놓인 선물을 ‘구사과’가 가져갈 때, ‘구사과’를 어디에 놓든 항상 선물을 가져가도록 하기 위한 최소 선물 개수를 구하자.아이디어‘구사과’는 어디에 놓이든 지도를 벗어나는 경우가 없으며, ‘EW’인 지역에 위치하거나 이동하게 되면 고립된다. 따라서 1 * N 칸 중 ‘EW’인 칸의 수 만큼 선물을 놓아야 한다. int cnt = 0; for (int i = 1; i 풀이 시간5분소스코드https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/15886.java problem-so..

문제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 한개를 붙이는..