공작소

문제 링크 : https://www.acmicpc.net/problem/10423 풀이 과정목표는 모든 도시를 발전소가 설치된 도시와 연결하는 것, 연결할 때 케이블을 최소 비용으로 설치하는 것이다. 도시를 최소 비용으로 연결하기 위해 최소 스패닝 트리 알고리즘을 사용하지만, 모든 도시가 발전소와 단순히 "연결"되어 있기만 하면 되므로 이 알고리즘을 살짝 변형시켜주면 된다. 1. 크루스칼 알고리즘 변형하기 먼저, 기본 크루스칼 알고리즘의 전체적인 실행 순서에 대해 알아보자.n개의 노드가 있을 때, m개의 간선들을 비용 기준으로 오름차순 정렬한다.정렬된 간선들을 차례대로 순회하면서, 간선이 연결하는 두 노드가 다른 부모 노드를 바라볼 때 (그룹이 다를 때) 두 노드를 연결한다.2번으로 n - 1 개의 간선..

문제 링크 : https://www.acmicpc.net/problem/1477 풀이 과정처음 접근 방법은, 최대 길이 구간의 중간에 휴게소를 설치하는 아이디어였다. 예를 들면, n = 4, l = 700 이고휴게소 위치 :  100  200  500  600구간 길이 :  100  100  300  100  100일 때,최대 길이 구간인 200 ~ 500 중간에 휴게소를 설치하여휴게소 위치 :  100  200 (350) 500  600구간 길이 :  100  100  150  150  100  100 다음과 같이 최대 길이 구간을 찾고, 그 구간을 분할하는 걸 m번 반복할 생각이였다. 하지만 이 아이디어는 최적의 방법이 아니다. 중간 설치 아이디어 문제점 : 균일하게 나누는 것이 더 최적이다.예를 들..

문제 링크 : https://www.acmicpc.net/problem/5214 풀이 과정역 하나하나마다 간선을 연결하는 것은 너무 비효율적이다. 한 하이퍼튜브 안에서 모든 역은 연결되어 있기 때문이다.한 하이퍼튜브가 서로 연결하는 역의 개수 K의 최대 제한이 1000이므로, 각 하이퍼튜브마다 K(K-1) 개의 단방향 간선을 생성해야 하는 일이 발생한다. 한 하이퍼튜브 안에서 단번에 다른 하이퍼튜브로 갈 수 있는 방법이 필요하다.  바로 하이퍼튜브 정점을 따로 만드는 것이다. 하이퍼튜브 정점을 따로 만들면, 한 하이퍼튜브 안에 있는 역 정점들은 하이퍼튜브 정점 한 개를 거쳐서 바로 연결되고, 다른 하이퍼튜브 안에 있는 역 정점 또한 하이퍼튜브 정점을 거쳐서 바로 연결될 수 있다. 이 아이디어가 있으면, ..

문제 링크 : https://www.acmicpc.net/problem/24520 문제신촌 왕국에는 1번부터 N번까지 N개의 마을이 있고 N-1개의 도로가 서로 다른 두 마을을 연결하고 있다. 모든 마을은 도로를 통해 다른 마을로 갈 수 있고, 이때 마을 내에서의 이동 거리는 무시할 수 있다.현재 신촌 왕국은 "대칭병"의 대유행으로 혼란을 겪고 있다. 대칭병은 어떤 것이든 대칭을 이루지 않으면 심신이 불편해져 일상생활을 할 수 없게 만드는 병이다. 대칭병의 여파는 엄청났는데 심지어 사람과 사람 간의 만남조차 어렵게 됐다. 신촌 왕국의 두 사람이 만나는 상황을 생각해보자. 약속 장소가 둘 중 한 사람의 마을에 더 가깝다면 아주 불편해진다. 따라서 두 사람이 사는 각 마을까지의 거리가 정확히 같은 곳을 약속..

문제 링크 : https://www.acmicpc.net/problem/13511 문제N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다.아래의 두 쿼리를 수행하는 프로그램을 작성하시오.1 u v: u에서 v로 가는 경로의 비용을 출력한다.2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같다.입력첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v와 간선의 비용 w가 주어진다.다음 줄에는 쿼리의 개수 M (1 ≤ ..

문제 링크 : https://www.acmicpc.net/problem/3176 문제N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다.총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000)다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양의 정수이다.다음 줄에는 K가 주어진다. (1 ≤ K ≤ 100,..

문제 링크 : https://www.acmicpc.net/problem/1761 문제N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.입력첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 입력된다. 두 점 사이의 거리는 10,000보다 작거나 같은 자연수이다.정점은 1번부터 N번까지 번호가 매겨져 있다.출력M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.풀이 과정https://readytojoin.tistory.com/entry/..

문제함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.f1(x) = f(x)f(n+1)(x) = f(fn(x))예를 들어 f4(1) = f(f(f(f(1))))이다.n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오.입력첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m)출력주어지는 n, x마다 fn(x)를 출력한다...

문제 링크 : https://www.acmicpc.net/problem/27504 문제상대음감은 음을 절대적인 높이로 구분하는 것이 아닌 어떤 음과의 상대적인 높이로 음을 인식하는 능력을 말한다. 상대음감은 절대음감에 비해 불리한 점이 있지만, 노래를 찾을 때 어렴풋한 멜로디 만으로도 노래를 찾을 수 있다는 장점이 있다.기령이는 이러한 점에서 착안하여 상대음감의 노래찾기 서비스를 만들려고 한다. 노래찾기 서비스는 데이터베이스에 노래의 음 데이터를 갖고 있으며 사용자가 멜로디를 입력했을 때 그 멜로디가 데이터베이스의 노래에 포함되어 있으면 해당 노래를 안내해 주는 서비스이다. 상대음감의 노래찾기 서비스는 상대적인 멜로디가 포함되어 있어도 일치하는 것으로 판단해 노래를 안내해준다. 즉, 찾으려는 멜로디가 a..

문제 링크 : https://www.acmicpc.net/problem/3779 문제아스키 코드가 97이상 126이하인 N개의 문자로 이루어진 문자열 S가 주어진다. 문자열 S의 모든 접두사에 대해, 각각의 접두사가 주기적인 문자열인지 아닌지 알고 싶다. 다시 말해 2 ≤ i ≤ N을 만족하는 각각의 i에 대해, 길이가 i인 문자열 S의 접두사가 어떤 문자열 A에 대해 AK 형태로 표현할 수 있는 가장 큰 K > 1을 알아내려 한다.AK란 문자열 A가 K번 연속되어있는 문자열을 의미한다. A = "abad"이고, K = 3인 경우 AK = "abadabadabad"이다.입력입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 줄로 이루어진다. 테스트 케이스의 첫 번째 줄에는 문자열 S의 ..