4Legs_Archives

문제 링크 : www.acmicpc.net/problem/2213 2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 예제의 결과에서 알 수 있듯이, 서브트리의 부모 노드를 선택하지 않는다고 해서 반드시 자식 노드가 선택되는 것은 아니다. 이는 곧 그리디 알고리즘으로는 해결할 수 없다는 것을 의미한다. 따라서 Tree 구조에서의 DP 문제로 접근해 문제를 풀어보자. 어떤 한 서브트리에서, 문제를 두 가지 경우로 나눌 수 있다. ① 서브트리의 root 노드를 선택했을 경우 (코드의 ..

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

문제 링크 : www.acmicpc.net/problem/20121 20121번: 카드 셔플 i번째 줄에는 i번째 테스트 케이스의 최소 횟수로 셔플하는 방법을 나타내는 문자열 S = s1s2 ... sK (sj = 'X' or 'Y') 를 출력한다. sj는 j번째 셔플이 X-셔플인지 Y-셔플인지를 의미한다. 방법이 여러 가 www.acmicpc.net 위치가 K인 카드의 X셔플 후 위치는 다음과 같다. 위치가 K인 카드의 Y셔플 후 위치는 다음과 같다. 이를 통해, 같은 위치에서 Y셔플을 한 후의 위치는 항상 X셔플 후 위치의 한 칸 뒤임을 알 수 있다. (단, X셔플 후 위치가 맨 끝일 경우 Y셔플 후 위치는 맨 처음이 된다.) 이제 예제에서 처음 6번 카드에 대해 각 셔플 후 경우를 직접 찾아보자. ..

문제 링크 : 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는 식을 만족..

최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘은 아래 포스팅에서 확인할 수 있다. 최소 스패닝 트리 (MST) : 크루스칼 알고리즘 (Kruskal Algorithm) 최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽 4legs-study.tistory.com 프림 알고리즘 (Prim Algorithm) 프림 알고리즘은 최소 스패닝 트리(MST)를 구하는 알고리즘으로, 다음과 같이 동작한다. ① 최초 출발 노드와 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해 MST에 추가한다. 이제 MST에는 2개의 정점이 포함되어..

최소 스패닝 트리 (MST, Minimum Spanning Tree) 그래프의 스패닝 트리(신장 트리, Spanning Tree)란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프를 의미한다. 위와 같은 그래프에서, 양쪽의 붉은 간선으로 이어진 부분 그래프들은 모두 스패닝 트리에 해당한다. 즉, 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면, 그것이 곧 스패닝 트리이다. 스패닝 트리는 이름처럼 트리의 일종이므로, V개의 모든 정점을 연결하는 간선의 수는 V - 1개이다. 최소 스패닝 트리(MST)는 이러한 스패닝 트리 중, 간선의 가중치 합이 최소가 되는 스패닝 트리를 말한다. 이러한 최소 스패닝 트리를 구하는 알고리즘은 대표적으로 Kruskal, Prim 알고리즘이 존재한다. 이번 ..

문제 링크 : 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의 오름차순 순서를 만..