공작소

문제 링크 : 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의 ..

문제 링크 : https://www.acmicpc.net/problem/1498 문제어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다. 예를 들어 ab는 주기문이 아니지만, abab는 (ab)^2으로 표현할 수 있으므로 주기문이 된다.문자열 S(2 ≤ S의 길이 ≤ 1,000,000)가 주어졌을 때, S의 앞에서부터 i개의 문자가 주기문의 형태가 되는 경우를 찾으려 한다. 가능한 경우가 여럿일 경우에는 n이 최대가 되는 경우를 구하려고 한다. S는 알파벳 소문자로만 이루어져 있다.문자열 S가 주어졌을 때, 가능한 i, n 쌍을 모..

문제 링크 : https://www.acmicpc.net/problem/11438 문제N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.풀이 과정https://readytojoin.tistory..

문제 링크 : https://www.acmicpc.net/problem/11437 문제N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.입력첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.출력M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.풀이 과정https://readytojoin.tistory.c..

최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘은 트리 구조 안에서 특정 정점 두 개의 공통 조상 정점 중 가장 가까운 공통 조상 정점을 찾는 알고리즘이다. 단순히 두 정점의 깊이를 맞춘 뒤 한 칸씩 동시에 올라가다가 마주치는 공통 조상이 최소 공통 조상인지라 쉽게 구할 수 있지만, 이동해야 할 정점이 많은 경우 희소 배열을 이용해 빠르게 최소 공통 조상을 구할 수 있다. LCA먼저, 7번 정점과 11번 정점의 공통 조상을 찾아보자.  7번 정점과 11번 정점이 공통으로 가지는 조상 정점은 1번 정점, 2번 정점, 4번 정점이 있다. 이 정점들은 모두 7번 정점과 11번 정점에서 시작해서 루트를 향해 올라가다가 마주칠 수 있는 공통되는 정점이다. 그 중에서도 시작 지점과 가..