0과 1의 쉼터

문제9335번: 소셜 광고 9335번: 소셜 광고 boj.ma 풀이문제 요약최소한의 사용자에게만 광고를 게시해, 전체 사용자들이 광고를 모두 볼 수 있도록 하자.아이디어N개의 줄에 걸쳐 i번째 사용자의 친구 d명의 번호가 주어진다.이중에서 최소한의 사용자를 선택해 전체 N명에게 광고를 게시해야 한다.사용자와 친구를 비트마스킹으로 표현하자. for (int i = 0; i 광고를 게시할 임의의 사용자(select)를 선택하고, 선택된 사용자의 친구들을 모두 합쳤을 때, N명 모두에게 광고를 게시할 수 있는지 확인하자.광고를 게시할 임의의 사용자가 최소가 되도록 결과를 갱신하면 된다. int res = N; for (int select = 1; se..

문제2615번: 오목 2615번: 오목 boj.ma 풀이문제 요약19 * 19 크기의 바둑판에 존재하는 오목의 가장 왼쪽 위 바둑알의 좌표와 색상을 출력하자.아이디어오목의 가장 왼쪽 위 바둑알의 좌표를 구해야 한다. 따라서, 좌상단부터 우하단으로 이동하며 현재 위치로부터 우상(↗), 우(→), 우하(↘), 하(↓) 방향으로 오목이 있는지 검사하면 된다. private static int whoWin(int x, int y) { final int start = board[x][y]; int[][] dirs = { {-1, 1}, // ↗ {0, 1}, // → {1, 1}, // ↘ ..

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

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

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