4Legs_Archives

문제 링크 : www.acmicpc.net/problem/1289 1289번: 트리의 가중치 첫째 줄에 트리의 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N-1개의 줄에 대해 각 줄에는 세 개의 정수 A, B, W(1 ≤ A, B ≤ N, 0 ≤ W ≤ 1,000)가 입력되는데 이는 A점과 B점이 연결되어 있고 이 www.acmicpc.net 문제 유형 Tree DP, Math 어떤 한 서브트리에서 나올 수 있는 모든 경로를 구해 보자. 우선 root를 경유하지 않는 경로, 즉 root노드가 경로의 한쪽 끝인 경우이다. 이는 일반적인 재귀를 통해 모두 구할 수 있다. 문제는 root를 경유하는 경로이다. 이를 구하기 위해서는 root로부터 이어진 각 자식들의 서브트리 가중치를 서로 ..

문제 링크 : programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 문제 유형 Tree DP, Greedy 2021 카카오 블라인드 코딩 테스트의 7번 문제이다. 문제의 '팀장'이 곧 서브트리의 root 노드임을 캐치했다면, 이 문제가 각 서브트리에서 최소 하나의 노드를 선택한 경우의 최소 가중치를 묻는 문제임을 알 수 있다. 단, 이 서브트리는 root와 그 자식 노드로만 이루어져 있다. 백준 2213 트리의 독립집합..

문제 링크 : www.acmicpc.net/problem/1006 1006번: 습격자 초라기 하나의 특수 소대로 인접한 두 영역을 커버할 수 있는 배치는 (2,10), (9,16), (4,5), (7,8), (13,14) 이다. 그리고 나머지 6개 구역은 각각 하나의 특수 소대로 커버할 수 있다. 그러므로 최소 11개 특수 소 www.acmicpc.net 굉장히 난해하고 어려운 문제다. 그나마 쉽게 접근하기 위해 원형으로 제시된 각 구역들을 선형으로 생각해보자. 그리고 다음과 같이 정의한다. - dp[k][2] : k열의 0행, 1행에 해당하는 구역 모두에 소대를 배치하지 않은 상태를 만드는 데 필요한 최소 소대 수 - dp[k][0] : k열의 0행까지만 소대를 배치한 상태를 만드는 데 필요한 최소 소..

문제 링크 : www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 예제의 결과에서 알 수 있듯이, 서브트리의 부모 노드를 선택하지 않는다고 해서 반드시 자식 노드가 선택되는 것은 아니다. 이는 곧 그리디 알고리즘으로는 해결할 수 없다는 것을 의미한다. 따라서 Tree 구조에서의 DP 문제로 접근해 문제를 풀어보자. 어떤 한 서브트리에서, 문제를 두 가지 경우로 나눌 수 있다. ① 서브트리의 root 노드를 선택했을 경우 (코드의 ..

문제 링크 : www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 이전에 포스팅했던 BOJ 1176 섞기와 동일한 접근법을 가진다. 어떠한 수들로 순열을 만들었을 때, 그 수들의 순서와 관계없이 우리는 이어붙인 수의 나머지만 알 면 된다. X개의 수를 이어붙인 큰 수를 k로 나눈 나머지가 r이라면, 그 r에 새로운 수 하나를 붙인 다른 한 수에 대한 나머지가 곧 X + 1개의 수를 이어붙인 큰 수를 k로 나눈 나머지이기 때문이다. 즉 1, 3, 5번의 수를 (3, 1, 5)의 순서로 이어붙이거나 (5,..

최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는 서로 연속할 필요는 없다. 아래의 예시 수열을 보자. 위 수열에서 최장 증가 수열을 찾으면 아래와 같다. 그림에서 붉은 칸으로 칠해진 부분 수열 (1, 2, 3, 6, 7, 9) 는 전체 수열 중 오름차순으로 증가하는 가장 긴 부분수열이다. 이제 주어진 수열에서 LIS의 길이를 구하는 두 가지 방법을 알아보자. 다이나믹 프로그래밍을 이용한 방법 : O(N^2) 이러한 최장 증가 수열을 찾는 가장 단순한 방법은 완전 탐색일 것이다. 하지만 수열에 존재하는 수의 개수가 k개일 때,..

문제 링크 : www.acmicpc.net/problem/8984 8984번: 막대기 첫 줄에는 막대기의 개수와 수평선 사이의 간격을 나타내는 두 개의 정수 N과 L이 주어진다. 여기서 N은 1 이상 100,000 이하이고, L은 1 이상 1,000,000 이하이다. 그 다음 N 개의 줄에는 각 줄마다 막대 www.acmicpc.net 위쪽 수평선의 한 점과 아래쪽 수평선의 서로 다른 10개의 점을 잇는 막대기가 있는 상황을 가정해 보자. 이들 중 가장 긴 막대기를 선택한다고 해서, 가장 긴 지그재그가 나올지는 알 수 없다. 따라서 이 문제는 그리디 알고리즘이 아닌 다이나믹 프로그래밍으로 접근해야 한다. 어떤 한 막대에서 지그재그가 끝난 상황을 생각해 보자. 이 때, 맨 마지막 막대를 기준으로 지그재그는..

문제 링크 : www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 문제를 간단하게 생각해야 깔끔하게 점화식을 구할 수 있다. "dp[k] = k일째 되는 날의 짚신벌레 개체 수"로 두고 문제를 풀어보자. 우선, 예제인 a = 2인 상황에서 짚신벌레가 증식만 한다고 가정한다면 다음과 같다. 0일째 되는 날: (0) 1일째 되는 날: (1) 2일째 되는 날: (2, 0) 3일째 되는 날: (3, 1, 0) 4일 째 되는 날: (4, 2, 1, 0, 0) 5일 째 되는 날: (5, 3, 2, 1, 1..

문제 링크 : www.acmicpc.net/problem/1029 1029번: 그림 교환 첫째 줄에 예술가의 수 N이 주어진다. N은 2보다 크거나 같고, 15보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. i번째 줄의 j번째 수는 j번 예술가가 i번 예술가에 www.acmicpc.net 이 문제를 DP로 풀기 위해 필요한 정보는 다음과 같다. ① 현재까지 그림을 산 사람들에 대한 정보 (한번 그림을 산 사람은 다시 살 수 없으므로) ② 마지막으로 그림을 산 사람 (다음에 살 사람의 가격은 마지막으로 산 사람에 의해 정해진다.) ③ 마지막으로 팔았을 때 그림의 가격 (다음에 살 사람은 이 가격 이상으로 사야 하기 때문) 따라서, 이 3가지 정보를 담은 3차원 dp 배열을 ..

문제 링크 : www.acmicpc.net/problem/20120 20120번: 호반우와 리듬게임 호반우가 모든 노트를 처리하면 3×1 + 4×2 + (-7)×3 + 1×4 = -6 점을 얻을 수 있습니다. 3번 노트를 제외한 모든 노트를 처리하면 3×1 + 4×2 + 1×1 = 12 점을 얻을 수 있습니다. 3번 노트를 놓쳤기에 4번 노 www.acmicpc.net DP문제의 대표유형인 계단오르기 문제와 유사한 문제이다. 각 노트를 처리하는 것과 계단을 한 번 오르는 것을 동일하게 생각한다면 수월하게 문제를 해결할 수 있다. 단 점수를 계산하기 위해선 현재까지 몇 콤보로 현재 노트를 처리하는지에 대한 정보가 필요하므로, 이 풀이에서는 dp 배열을 2차원으로 두었다. k번 노트를 c 콤보에서 처리한 경..