4Legs_Archives

문제 링크 : www.acmicpc.net/problem/8916 8916번: 이진 검색 트리 각 테스트 케이스에 대해서, 입력으로 주어진 순열과 같은 트리를 만드는 순열의 개수를 9,999,991로 나눈 나머지를 출력한다. www.acmicpc.net 한 트리에서 왼쪽 자식은 모두 파란색, 오른쪽 자식은 모두 빨간색으로 칠해보자. 우선 이러한 형태의 BST(Binary Search Tree)를 구성하기 위해선 반드시 root가 처음 입력되어야 한다는 것은 자명하다. 이 때, root 노드를 제외한 나머지 노드들의 번호가 아예 존재하지 않는다고 가정할 때, 위와 같은 BST의 형태만을 만드는 것은 다음과 같다. 각 자식 노드들의 서브트리 관계와 상관없이 단지 입력만을 고려했을 때, 왼쪽 서브트리의 모든 ..

문제 링크 : www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 모든 도시에 전기가 공급되어야 하며, 한 도시가 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 점에서 MST를 구하는 문제로 접근할 수 있다. 둘 이상의 발전소에서 전기를 공급받지 않아야 한다는 것은 곧 사이클 없이 모든 정점을 잇는 것과 같기 때문이다. 단, 일반적인 MST 문제와의 차이는 아래의 예제와 같이 모든 정점이 서로 연결되어 있지는 않다..

문제 링크 : www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 정답인 a, b에 대해 제시된 수열은 항상 X(i+1) = a * Xi + b를 만족한다. 즉, 이는 일반항이다. 우리는 제시된 수열의 길이에 따라 Case를 구분할 수 있다. ① 제시된 수열의 길이가 1일 때 우리는 a, b를 특정할 수 없다. 다음 수가 아예 없기 때문이다. 이 경우 정답은 A이다. ② 제시된 수열의 길이가 2일 때 두 가지 경우로 나뉜다. 제시된 수를 29, 38이라 해보자. 이 때, a = 1, b = 9로 두었을 경우 a, b는 식을 만족..

문제 링크 : www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 이전에 포스팅했던 BOJ 1176 섞기와 동일한 접근법을 가진다. 어떠한 수들로 순열을 만들었을 때, 그 수들의 순서와 관계없이 우리는 이어붙인 수의 나머지만 알 면 된다. X개의 수를 이어붙인 큰 수를 k로 나눈 나머지가 r이라면, 그 r에 새로운 수 하나를 붙인 다른 한 수에 대한 나머지가 곧 X + 1개의 수를 이어붙인 큰 수를 k로 나눈 나머지이기 때문이다. 즉 1, 3, 5번의 수를 (3, 1, 5)의 순서로 이어붙이거나 (5,..

문제 링크 : www.acmicpc.net/problem/17501 17501번: 수식 트리 수식 트리는 루트가 있는 이진 트리로 2N-1개의 노드가 있습니다. 1번부터 N번까지 노드는 피연산자 노드이며 다른 노드들은 연산자 노드이고 2N-1번 노드가 루트입니다. 연산자 노드는 항상 두 개 www.acmicpc.net 예제 1을 수식 트리로 나타내면 아래와 같다. 노드 1 ~ 5의 피연산자 노드를 각각 미지수 X1 ~ X5로 두었을 때, 이 수식 트리의 최종 결과값은 (X1 + X3 + X5) - (X2 + X4)가 된다. 즉, 트리의 형태와 상관없이 각 리프 노드(피연산자 노드)까지 도달했을 때, 해당 피연산자가 최종 식에서 어떤 부호를 갖는지만 파악하면 문제를 쉽게 해결할 수 있다. 만약 최종 식에서..

문제 링크 : www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제에서 한 아이의 위치를 옮기는 것은 항상 맨 앞으로 보내거나, 맨 뒤로 보내는 것에 유의하자. 이렇게 위치를 옮기는 횟수를 최소화하려면, 최초 아이들의 순서에서 이미 번호 순으로 서 있는 아이들을 제외한 나머지를 옮기면 된다. 즉, 예제의 (3 7 5 2 6 1 4) 에서, 이미 3, 5, 6의 올바른 순서가 존재하므로 이들을 제외한 나머지 7, 2, 1, 4를 옮기면 1 ~ 7의 오름차순 순서를 만..

문제 링크 : www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 최장 증가 수열(LIS)에 대해 숙지하고 있다면 쉽게 해결할 수 있는 문제이다. 전체 수열의 크기가 1000으로 작기 때문에 O(N^2)의 시간복잡도를 갖는 DP를 사용할 수 있다. 수열의 한 수에 대해, 왼쪽 끝에서 그 수에서 끝나는 LIS와 오른쪽 끝에서 시작해 그 수에서 끝나는 LIS 길이의 합(-1)이 곧 바이토닉 수열의 길이가 된다. (이 때, 원래의 수는 그 바이토닉 부분 수열에서 가장 큰 값이 된다.) ..

문제 링크 : www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 문제의 부분 상황을 보자. 1, 2번 경찰차가 몇 개의 사건을 해결한 상황이다. 이제 새로운 사건이 발생했을 때, 가능한 경우는 1번 경찰차가 해결하거나, 2번 경찰차가 해결하는 두 가지가 존재한다. (부분문제) 이 때, 항상 가까운 경찰차가 문제를 해결하는 것은 최적해를 보장하지 못한다. 다음 사건의 위치를 미리 알고 있는게 아니기 때문이다. 따라서 이 문제는 다이나믹 프로그래밍으로..

문제 링크 : www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 간선들은 그 간선의 양 끝 노드에 불이 옮겨진 순간부터 타는 시간이 절반으로 줄어들게 된다. 쉽게 설명하자면 다음 그림과 같다. 정점 A에 불이 먼저 붙은 상황이다. 이 때, A와 B를 잇는 간선은 A쪽에서 먼저 타게 된다. B쪽에는 아직 불이 도착하지 않았기 때문이다. 이제 정점 B에도 불이 붙었다. 이제는 간선의 남은 길이가 양쪽에서 타..

문제 링크 : www.acmicpc.net/problem/8984 8984번: 막대기 첫 줄에는 막대기의 개수와 수평선 사이의 간격을 나타내는 두 개의 정수 N과 L이 주어진다. 여기서 N은 1 이상 100,000 이하이고, L은 1 이상 1,000,000 이하이다. 그 다음 N 개의 줄에는 각 줄마다 막대 www.acmicpc.net 위쪽 수평선의 한 점과 아래쪽 수평선의 서로 다른 10개의 점을 잇는 막대기가 있는 상황을 가정해 보자. 이들 중 가장 긴 막대기를 선택한다고 해서, 가장 긴 지그재그가 나올지는 알 수 없다. 따라서 이 문제는 그리디 알고리즘이 아닌 다이나믹 프로그래밍으로 접근해야 한다. 어떤 한 막대에서 지그재그가 끝난 상황을 생각해 보자. 이 때, 맨 마지막 막대를 기준으로 지그재그는..