본문 바로가기

문제 노트/백준

 (102)
세 수의 합( BOJ 2295 ) 문제 : https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 문제 파악하기 N개의 숫자로 이루어진 집합 U에서 3개의 숫자를 적절하게 선택해서 집합 U에 있는 값 중 만들 수 있는 가장 큰 값을 만드는 문제입니다. N의 개수가 최대 1,000개이기 때문에 O(n3)알고리즘으로는 시간초과가 나오게 됩니다. 그렇다면 어떤 알고리즘을 사용해서 시간 복잡도를 줄일 수 있을까요? 여기서는 3개의 숫자의 합을 ..
1의 개수 세기( BOJ 9527 ) 문제 : https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 문제 파악하기 주어진 자연수 A, B 사이의 모든 숫자를 이진수로 표현했을 때, 사용되는 모든 1의 개수를 세는 프로그램입니다. 이렇게 특정 구간 내에 조건을 만족하는 값의 개수를 세는 문제에서는 주로 누적합을 구하는 알고리즘을 활용해서 문제를 해결하며, 이번 문제 역시 비슷한 방식을 사용하면 문제를 해결할 수 있습니다. 여기서 말하는 누적합을 구하는 알고리즘이란..
레이스( BOJ 1508 ) 문제 : https://www.acmicpc.net/problem/1508 1508번: 레이스 첫째 줄에 N, M, K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, M은 K보다 작거나 같다. 또, K는 2보다 크거나 같고, 50보다 작거나 같다. 둘째 줄에 심판이 있을 수 있는 K개의 위치가 주어 www.acmicpc.net 문제 파악하기 M명의 심판을 배치하는 여러 가지 경우 중, 가장 가까운 심판 사이의 거리가 최대인 경우를 구하는 문제입니다. 만약 모든 경우의 수를 조사한다면, 최악의 경우 1,000,000개 자리 중 50명의 심판을 배치하는 모든 가짓수를 조사해야 합니다. 터무니없이 많기 때문에 문제를 조금 바꿀 필요가 있습니다. 문제를 최적화 문제에서 결정문제로 바꿔봅시다. ..
Cereal( BOJ 18878 ) 문제 : https://www.acmicpc.net/problem/18878 18878번: Cereal Farmer John's cows like nothing more than cereal for breakfast! In fact, the cows have such large appetites that they will each eat an entire box of cereal for a single meal. The farm has recently received a shipment with $M$ different types of cereal $(1\ www.acmicpc.net 문제 파악하기 소들이 자신의 선호도 순위대로 시리얼을 먹거나 시리얼을 포기할 때, 0마리 ~ (i-1)마리 소가 앞에서부..
불만 정렬( BOJ 5012 ) 문제 : https://www.acmicpc.net/problem/5012 5012번: 불만 정렬 정렬 알고리즘의 상한(upper bound)은 n2이다. 이 사실은 쉽게 증명할 수 있다. 올바른 순서가 아닌 임의의 두 원소(ai > aj, i aj > ak(i
숨바꼭질 5( BOJ 17071 ) 문제 : https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 파악하기 수빈이가 동생을 찾는데 걸리는 최소 시간을 구하는 문제입니다. 동생은 매초 1만큼 가속을 받아 이동하며, 수빈이는 현재 위치에서 ±1 또는 x2 만큼 이동할 수 있습니다. 이 문제에서 중요한 점은 수빈이가 항상 최선의 동선으로만 이동하지 않는다는 것입니다. 예를 들어, 수빈이가 17에 있으며 동생이 5에 있다고 가정해봅시다. 이 경우, ..
대기업 승범이네( BOJ 17831 ) 문제 : https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 문제 파악하기 승범이네 회사의 사원들 중 멘토와 멘티를 적절하게 선택해서 최대의 시너지 효과를 구하는 문제입니다. 승범이네 회사 구조는 트리 구조로 되어있으며 사수와 부사수 관계를 가지고 있는 사원을 멘토-멘티로 선정할 수 있습니다. 결국 이 문제는 현재 노드와 자식 노드를 멘토-멘티로 선정할 것인지, 아니면 현재 노드를 제외할지 탐색해야 하는 문제로 바꿀 ..
Degree Bounded Minimum Spanning Tree( BOJ 20927 ) 문제 : https://www.acmicpc.net/problem/20927 20927번: Degree Bounded Minimum Spanning Tree 제약에 맞는 Spanning Tree가 존재한다면 첫 번째 줄에 YES를 출력하여라. 이후 해당 Spanning Tree 의 간선을 $N-1$개의 줄에 걸쳐 출력한다. 간선을 출력하는 순서는 상관없으며, 각 간선을 출력할 때는 www.acmicpc.net 문제 파악하기 N개의 정점을 모두 연결하는 트리 중 가중치의 값이 가장 작은 트리의 모양을 찾는 문제입니다. 얼핏 보면 Spanning Tree 알고리즘 문제처럼 보이지만 이 문제는 한 가지 조건이 더 주어집니다. 바로 각각의 노드가 가질 수 있는 차수가 제한되어 있습니다. 그렇기에 기존의 크루스칼..

티스토리툴바