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

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

문제 링크 : https://www.acmicpc.net/problem/3356 문제라디오 방송국은 메시지를 여러 청취자에게 전송한다. 모든 청취자가 메시지를 확실히 받게 하기 위해서 메시지를 계속해서 반복 전송한다.한 청취자가 받은 메시지가 주어진다. 항상 청취자가 받은 메시지의 길이는 방송국에서 보낸 메시지의 길이보다 크거나 같다. 이때, 라디오 방송국에서 보낸 메시지를 구하는 프로그램을 작성하시오.즉, 입력으로 S가 주어졌을 때, S가 S' + S' + ... + S'의 부분 문자열이 되는 가장 짧은 부분수열 S'를 구하는 프로그램을 작성하시오. 입력첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,0..

문제 링크 : https://www.acmicpc.net/problem/13506 문제문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.입력첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 106을 넘지 않는 자연수이다.출력가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T..