넘치게 채우기

BOJ - 케빈 베이컨의 6단계 법칙문제 유형: 플로이드-워셜문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교..

https://www.acmicpc.net/problem/28703BOJ - 28703 - Double It문제 유형: 정렬, 우선순위 큐, 슬라이딩 윈도우, 그리디문제 난이도: Gold III시간 제한: 1초메모리 제한: 1024MB 문제양의 정수로 이루어진 길이가 N$N$인 배열 A1,⋯,AN이 주어집니다. 당신은 원하는 만큼 다음 조작을 할 수 있습니다.배열에서 원하는 수 하나를 골라서 2를 곱합니다.조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요. 입력첫 줄에 배열의 길이 N이 주어집니다. (1≤N≤200000)둘째 줄에 N개의 양의 정수 A1,A2,⋯,AN이 주어집니다. (1≤Ai≤10^9) 출력조작 이후 A1,⋯,AN의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하..

https://www.acmicpc.net/problem/1477BOJ - 휴게소 세우기문제 유형: 이진 탐색, 매개변수 탐색(parametric search)문제 난이도: Gold IV시간 제한: 2초메모리 제한: 128MB 문제다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 ..

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/description/leetcode - Construct Binary Tree from Preorder and Postorder Traversal문제 유형: 트리, 분할 정복문제 난이도: Medium 문제Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstr..

https://www.acmicpc.net/problem/1114BOJ - 통나무 자르기문제 유형: 이진 탐색, 매개 변수 탐색문제 난이도: Gold I시간 제한: 2초메모리 제한: 128MB 문제벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나누려고 한다.통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자. 입력첫째 줄에 세 정수 L, K, C가 주어진다. 둘째 줄에는 통나무를 자를 수 있는 위치가 주어진다. 출력..

https://leetcode.com/problems/recover-a-tree-from-preorder-traversal/description/leetcode - Recover a Tree From Preorder Traversal문제 유형: 스택, 트리, dfs, 문자열 처리문제 난이도: Hard 문제We run a preorder depth-first search (DFS) on the root of a binary tree.At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node.  If the depth of a node is D..

https://www.acmicpc.net/problem/16975BOJ - 수열과 쿼리 21문제 유형: 세그먼트 트리(with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 512MB 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다.2 x: Ax 를 출력한다. 입력첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 1,000,000)셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.넷째 줄부터 M개의 줄에는 쿼리가 한 줄..

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/description/?envType=daily-question&envId=2025-02-21leetcode - Find Elements in a Contaminated Binary Tree문제 유형: 트리, 해시문제 난이도: Medium 문제Given a binary tree with the following rules:root.val == 0For any treeNode:If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1If treeNode.val has a..

https://www.acmicpc.net/problem/10999BOJ - 구간 합 구하기 2문제 유형: 세그먼트 트리 (with lazy propagation)문제 난이도: Platinum IV시간 제한: 2초메모리 제한: 256MB 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째부터 4번째 수에 6을 더하면 1, 2, 9, 10, 5가 되고, 여기서 2번째부터 5번째까지 합을 구하라고 한다면 26을 출력하면 되는 것이다. 그리고 그 상태에서 1번째부터 3번째 수에 2를 빼고 2번째부터 5번째까지 합을 구하라고 한다면 22가 될 것이다. 입력첫째 줄에 수의 개수 N(1 ≤ N ≤..

https://www.acmicpc.net/problem/2533BOJ - 사회망 서비스(SNS)문제 유형: 트리, 다이나믹 프로그래밍문제 난이도: Gold III시간 제한: 3초메모리 제한: 256MB 문제페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다.예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다.   친구 관계..