구름 개발일기장

https://www.acmicpc.net/problem/12912 🐢 설명 트리가 있을 때 하나의 간선만을 제거해서 새롭게 연결했을 때 다시 가질 수 있는 최대 지름을 구하면 되는 문제이다. 이때 새로만든 그래프는 트리로서 특성이 유지가 되어야 한다. 그럼 생각해보자. 트리에서 어떤 간선을 제거했다면 어떻게 될까? 바로 트리 두개가 생기게 된다. 그렇다면 문제는 단순해진다. N개의 노드로 이뤄진 트리에서 N-1개의 간선들에 대해서 x간선을 지우고, 트리 두개의 지름을 구한 후, 해당 간선의 길이를 더했을때가 해당 간선을 지웠을 때 최대로 가질 수 있는 지름이 된다. 어짜피 트리 + 트리 이므로 어느 노드에 연결할지는 중요하지 않고 간선을 지웠을 때 각 트리가 가지는 최대 지름만 잘 구해주면 된다. 문제..

https://www.acmicpc.net/problem/4256 🐢 설명 어떤 트리가 존재한다고 하였을 때, pre-order, in-order 순서로 방문한 결과를가지고 post-order 순서로 방문했을 때의 결과를 반환해야 하는 문제이다. 먼저 pre, in 결과를 가지고 트리를 만들고, post 방식으로 방문한 결과를 반환하도록 하면 되겠다. 그럼 pre와 in의 조회 방식 차이를 봐보자. pre-order 현재 방문한 노드의 값을 출력 -> left를 체크, 존재하면 left 방문 -> right를 체크, 존재하면 right 방문 하는 방식으로 이뤄진다. 즉, 처음에 방문하는 노드가 루트임이 보장된다. in-order 현재 방문한 노드 left 체크, 존재하면 방문 -> left 방문 후 현재..

https://www.acmicpc.net/problem/12978 🐢 설명 전형적인 트리 DP 문제이다. 먼저 N개의 정점이 있는데 간선이 N-1개라는 말이 있다면 트리를 의미하는건지 의심하면 되는데, 문제에서 보면 N - 1 개의 도로를 이용해 모든 도시들 사이에는 단 한개의 경로만이 존재하도록 이라는말이 있다. N-1개의 간선에 정점 간 단 한개의 경로만이 존재한다 하였으므로 트리구조임을 알 수 있다. 참고로 트리에서 루트 노드를 제외하고는 자신에게 들어오는 간선이 하나이므로 경로도 유일하다. 그러면 이제 트리임을 알았으므로 정점 아무거나 하나골라서 dfs를 통해 경찰서를 설치할지 말지 정해주면 된다. 경우의 수 x정점에 경찰서를 설치할 경우 자식 노드에는 경찰서를 설치해도 된다. 자식 노드에는 경..

https://www.acmicpc.net/problem/1623 🐢 설명 트리DP + 트래킹 문제이다. 문제를 정리해보면 자신의 직속상사가 참가하면 자신은 참가하지 않고, 직속상사가 불참하면 자신은 참가할 수 있으며 && 참가자들의 날나리 정도의 합이 최대가 되도록 하는 멤버 및 그때의 날나리 합을 구하면 된다. 근데 이때 사장이 참여하는 경우 / 참여하지 않는 경우 2가지에 대해 구해야 한다. 먼저, 상사의 참가여부에 부하의 참가여부가 달라지는 경우는 일반적인 트리 DP 문제로 2차원 dp배열을 통해 풀 수 있다. 상사가 참여하는 경우 부하는 참여하지 못함 상사가 참여하지 않는 경우 부하는 참여하거나 부하는 참여하지 않음 이렇게 케이스를 나눠서 dp를 채워주면 된다. 하지만 이 문제에서는 추가적으로 ..

https://www.acmicpc.net/problem/24232 🐢 설명 트리 DP 문제인데 dfs 활용이 필요한 문제이다. 처음에 어떻게 접근해야 하는지 머리를 오래 싸맸는데 결국 풀지 못해서 다른 풀이를 참고했다. 결론은 총 3번의 dfs를 통해 문제를 풀게 된다. 먼저 간선 정보를 이용해서 트리를 만들어야 하는데 이때 간선은 목적지, IN/OUT 구분값, 나중에 출력을 위한 번호 까지 총 3개의 변수를 들고 있어야 한다. 또한 주어진 정방향 간선을 adj[u].add(v) 와 같이 넣어줬다면 반대도 adj[v].add(u)를 넣어줘야 한다. 물론 위에서 말한 3가지 변수를 함께 채워서 트리를 만들었다면 어떤 노드에서 다른 모든 노드로 가는데 최소 비용이 드는지 알기위한 dfs를 돌려야 하는데 이..

https://www.acmicpc.net/problem/23887 🐢 설명 BFS + 트리DP 문제이다. 먼저 2차원 배열에 위치하는 학생들이 존재하고, 이들은 8방향으로 주위 학생들에게 자신의 유인물 한개를 제외하고 넘겨주게 된다. 이때 모두가 유인물을 받기 위해서 학생들이 몇개의 유인물을 받아야하는지 출력하면 된다. 만약 모두에게 유인물을 넘겨줄 수 없다면, 즉 8방향을 탐색해도 넘겨줄 수 없는 자리배치로 있다면 -1을 출력하면 된다. 최초에 유인물을 받는 학생이 곧 root 노드가 되고 이 학생부터 bfs를 돌면서 트리구조를 만들어주면 된다. 이때 주의할 점이 동시에 유인물을 나눠받는 학생은 번호가 낮은 학생으로부터 유인물을 받게 된다는 점이다. 따라서 Queue로 bfs를 돌 때 노드 하나당 ..

https://www.acmicpc.net/problem/2213 🐢 설명 일반적인 트리DP + 경로 추적 문제이다. 기본적으로 트리dp 문제는 2차원 dp를 이용해서 해당 정점을 사용하느냐 마느냐에 따라서 해당 노드의 가중치를 더하거나 말거나 하는 방식으로 진행된다. 이 문제에서는 서로 인접하지 않는 정점들을 골라서 최대의 가중치를 구하고 해당 정점들의 번호를 순서대로 나열해야 한다. 문제에서 말하는 독립 집합은 결국 각 정점들을 인접하지 않게 뽑았을 때 최대로 값을 가지는 정점들의 부분집합인데 이때 특정 정점이 독립집합이라면 (YES) 인접 정점은 독립집합일 수 없다. (NO) 특정 정점이 독립집합이 아니라면 (NO) 인접 정점은 독립집합일 수 있다. (YES) 인접 정점은 독립집합이 아닐 수 있다...

https://www.acmicpc.net/problem/1395 🐢 설명 인덱스드 트리 + 천천히 갱신되는 트리 활용이다. 이러한 유형의 문제들의 특징은 값의 변경이 특정 인덱스 하나가 아니라 범위로 주어진다는 특징이 있다. 하나의 값 변경에는 logN이 소요되고 범위가 1~N으로 주어지면 NlogN, 이러한 쿼리가 M번 주어지면 M * N * log N이 되어 N^2을 넘어가는 시간복잡도를 갖게된다. 따라서 시간복잡도 개선을 위해 값 변경이 이뤄지는 구간에 대해서 동일한 변경이 이뤄지는 노드들의 공통 부모에만 변경사항을 쌓아놓고 실제 변경이 필요할 때 자식노드로 변경해야할 값을 적용하도록 하는 지연 갱신 방식이 사용된다. 예를들어서 1~8번 노드가 존재한다고 하자. 이때 update(1, 8, 10)..

https://www.acmicpc.net/problem/2517 🐢 설명 자신보다 느린 사람이 앞에 있다면 모두 추월할 수 있다는 가정하에 최대 몇등을 기대할 수 있는지 계산하면 되는 문제이다. 세그먼트 트리를 이용해서 풀 수 있다. 능력 : 2, 8, 10, 7, 1, 9, 4, 15 순서 : 1, 2, 3, 4, 5, 6, 7, 8 능력 : 15, 10, 9, 8, 7, 4, 2, 1 순서 : 8, 3, 6, 2, 4, 7, 1, 5 1. 먼저 현재 달리고 있는 사람들의 순서 + 능력을 기록한다. 2. 이들 각각은 자신의 앞에 있는 자신보다 능력이 높은 사람의 수 + 1 등이 최대 기대 등수 임을 알 수 있다. 3. 위 정보를 가지고 능력순으로 정렬한다. (능력값이 클수록 능력이 좋다) 이 배열을 ..

https://www.acmicpc.net/problem/2094 🐢 설명 일반적인 인덱스 트리 문제라고 생각했지만 추가적인 아이디어가 필요한 문제였다. 경로 압축이라는 방법을 사용해야 한다. Q(Y, X)가 주어졌을 때 "Y년도 이후 X년도가 가장 많은 비가 내렸다"라는 쿼리를 증명하기 위해서는 Y년, X년, 그 사이 년도에 대해 정보를 확인해야 하는데 이때 가능한 모든 년은 -10억 ~ +10억이므로 총 20억의 크기를 갖는 배열을 필요로한다. 이는 메모리 초과가 날것이 뻔하다. 하지만 년도에 대한 정보는 50000개만 주어진다고 하였으므로 해당 년도만 Map 자료구조에 저장해서 사용하도록 하면 위 쿼리에 대해 (Trure / Flase / Maybe)를 증명할 수 있다. Map 맵을 생성하여 년도별..

https://www.acmicpc.net/problem/12099 🐢 설명 lower bound, upper bound를 사용해서 풀면 되는 문제이다. 주어진 음식 메뉴를 매운 순서로 정렬하고, 먹을 수 있는 범위인 u, v를 가지고 lower bound, upper bound를 구해준다. 이 범위내에서 먹을 수 있는 달달한 메뉴를 찾아야 하므로 반복문을 통해 x, y 범위 비교해준다. 2번에서 카운트한 개수가 곧 매운맛과 달달함이 충족된 메뉴의 개수이다. 총 Q번의 범위에 대해 N개의 메뉴들에 대해 이분탐색을 하고, 해당 범위 내에서 다시 탐색을 하게 된다. 따라서 대략 O(QN)의 시간 복잡도를 갖게 된다. 🐢코드 public class 점심메뉴_12099 { static int N; static ..

https://www.acmicpc.net/problem/23830 🐢 설명 아주 간단한 이분탐색 문제이다. 결국 K를 찾기 위해 가능한 범위를 지정한 후 해당 범위내에서 K값을 지정해보고 이때의 평균값과 선생님이 원하는 S값과의 비교를 통해 범위를 조정해가면 된다. 평균을 높이기 위해서는 결국 K를 올려야 하므로 left = mid + 1, 평균을 낮추기 위해서는 K를 낮추기 위해 right = mid 로 해주면 된다. 가능한 가장 작은 K를 구해달라 하였으므로 lower bound로 구하면 된다. 여기서 놓칠 수 있는 부분은 문제의 첫 문장에 양의 정수 K라고 하였으므로 K의 하한 범위를 0이 아닌 1로 잡아줘야 한다. 🐢코드 public class 제기차기_23830 { static int N; s..