분류 전체보기

문제 설명N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.      제한 사항      풀이문제를 요약하면, LCA를 찾는 문제이다.LCA란 최소 공통 조상을 의미한다.예시에 주어진 트리를 보자.주어진 트리는 위와 같이 생겼고, 6번과 11번의 LCA는 2번이다. LCA를 구하는 유명한 방법은 두 가지이다.두 노드의 레벨을 동일하게 맞춘 뒤, 한 칸씩 위로 올라가며 LCA 탐색오일러 투어를 통한 LCA 탐색 첫 번째 방법은 부모 노드와 깊이를 모두 기록해야 된다.조금 번거롭다고 생각하여 간..

문제 설명트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1167      제한 사항      풀이문제를 요약하면, 트리의 지름을 구하는 것이다.트리의 지름이란 트리에 있는 노드 간의 거리가 가장 먼 두 노드의 거리를 말한다.트리의 지름을 구하는 방법은 크게 두 가지이다.DFS를 이용하는 방법DP를 이용하는 방법DFS를 이용하는 방법은 간단하다.임의의 노드를 고른 뒤 DFS를 통해 가장 먼 노드를 찾아낸다.가장 먼 노드는 트리의 지름에 포함되는 노드이다.따라서, 그 노드에서 가장 먼 노드를 다시 구하면 그 거리가 트리의 지름이 된다. 이를 증명하는 것은 간단하다.트리의 지름..

문제 설명LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.      제한 사항      풀이문제를 요약하면 LCS를 구하는 것이다.LCS는 최장 공통 부분 수열을 의미한다. 최장 공통 부분 수열은 두 개의 문자열 혹은 배열에서 가장 긴 공통된 부분을 의미한다.예를 들어 보자.ACAYKP, CAPCAK 두 개의 문자열의 LCS는 ACAK이다. 그렇다면, 이를 어떻게 구해내는지 알아보자.LCS는 DP를 이용하여 간단하게 구해낼 수 있다.이차원 배열을 통해 메모이제이션을 한다.두 문자열의 각 위치를 비교하며 같을 때와 다..

문제 설명수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.      제한 사항      풀이문제를 요약하면, 주어진 배열에서 가장 긴 증가하는 부분 수열을 뽑는다.그 길이와 요소를 출력해야 한다. 우선, 가장 긴 증가하는 부분 수열을 뽑는 과정은 다음과 같다.배열을 하나씩 탐색하며 해당 요소 이전에 나온 자신보다 작은 요소 중 가장 긴 부분 수열을 뽑은 뒤 자신을 추가하면 가장 긴 증가하는 부분 수열이 된다.예를 들어 보자.30을 탐색하는 과정에서 20은 [10, 20]으로 가장 긴 증가..

문제 설명색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자.  먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 ..

문제 설명피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.      제한 사항      풀이피보나치 수열을 구하는 문제는 간단하다.설명에 나온대로 i-1, i-2를 더하면 된다. 하지만, 해당 문제에서는 N이 굉장히 크다.즉, $O(N)$만에 답을 구해도 시간초과라는 것이다. 해당 문..

문제 설명알파벳 대문자가 한 칸에 한 개씩 적혀있는 N×M 크기의 문자판이 있다. 편의상 모든 문자는 대문자라 생각하자. 예를 들어 아래와 같은 문자판을 보자.이 문자판의 한 칸(아무 칸이나 상관없음)에서 시작하여 움직이면서, 그 칸에 적혀 있는 문자들을 차례대로 모으면 하나의 단어를 만들 수 있다. 움직일 때는 상하좌우로 K개의 칸까지만 이동할 수 있다. 예를 들어 K=2일 때 아래의 그림의 가운데에서는 'X' 표시된 곳으로 이동할 수 있다.반드시 한 칸 이상 이동을 해야 하고, 같은 자리에 머물러 있을 수 없다. 또, 같은 칸을 여러 번 방문할 수 있다.이와 같은 문자판과 K, 그리고 하나의 영단어가 주어졌을 때, 이와 같은 영단어를 만들 수 있는 경로가 총 몇 개 존재하는지 알아내는 프로그램을 작성..

문제 설명0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.1 ≤ i 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.      제한 사항      풀이문제를 요약하면, N의 각 자릿수를 K번 교환하여 만들 수 있는 최댓값을 구하는 문제이다. 처음에는 N의 각 자릿수를 정렬하여 최대한 비슷하게 만드는 방식으로 문제를 풀려했었다.k번의 교환을 통해 0번째부터 k번째 수를 확정해가면 된다 생각했다.하지만, 이 방법은 반만 정답이다.만약 k가 N의 자릿수보다 많다면 곤란해진다.따라서, 해당 방법이 아닌 다른 방법이 필요하다. k-1번째 교환에서 큰 수를 만들었다 하여도 k번째에 더 작아질 수 있다.반대..

문제 설명각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.각 공항들간 티켓가격과 이동시간이 주어질..

문제 설명V개의 마을과 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.https://www.acmicpc.net/problem/1956      제한 사항      풀이문제를 요약하면..