넘치게 채우기

https://www.acmicpc.net/problem/1647BOJ - 도시 분할 계획문제 유형: 최소 신장 트리문제 난이도: Gold IV시간 제한: 2초메모리 제한: 256MB 문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된..

https://leetcode.com/problems/minimum-number-of-operations-to-sort-a-binary-tree-by-level/description/leetcode - Minimum Number of Operations to Sort a Binary Tree by Level문제 유형: 정렬, 트리, bfs문제 난이도: Medium 문제You are given the root of a binary tree with unique values.In one operation, you can choose any two nodes at the same level and swap their values.Return the minimum number of operations neede..

https://www.acmicpc.net/problem/15681BOJ - 트리와 쿼리문제 유형: 트리, dfs문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자. 입력트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)이는 U와 V를 양 끝점으로 ..

https://leetcode.com/problems/find-building-where-alice-and-bob-can-meet/description/leetcode - Find Building Where Alice and Bob Can Meet문제 유형: 이진 탐색, 모노토닉 스택문제 난이도: Hard 문제You are given a 0-indexed array heights of positive integers, where heights[i] represents the height of the ith building.If a person is in building i, they can move to any other building j if and only if i  and heights[i] Yo..

https://www.acmicpc.net/problem/1197BOJ - 최소 스패닝 트리문제 유형: 최소 신장 트리, 최단 경로문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 ..

https://leetcode.com/problems/maximum-number-of-k-divisible-components/description/leetcode - Maximum Number of K-Divisible Components문제 유형: 트리, dfs, 부분합문제 난이도: Hard 문제There is an undirected tree with n nodes labeled from 0 to n - 1. You are given the integer n and a 2D integer array edges of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the t..

https://www.acmicpc.net/problem/2467BOJ - 용액문제 유형: 투 포인터문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의..

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/leetcode - Reverse Odd Levels of Binary Tree문제 유형: 이진트리, bfs문제 난이도: Medium 문제Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].Return the root of the reversed t..

https://www.acmicpc.net/problem/2166BOJ - 다각형의 면적문제 유형: 수학, 선형대수, 기하학문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. 출력첫째 줄에 면적을 출력한다. 면적을 출력할 때에는 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 출력한다. 풀이볼록 또는 오목다각형에서 순서대로 N개의 점의 좌표가 주어진다면, 신발끈 공식을 이용해서 다각형의..

https://leetcode.com/problems/max-chunks-to-make-sorted/description/leetcode - Max Chunks To Make Sorted문제 유형: 그리디, 브루트 포스문제 난이도: Medium 문제You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equa..