4Legs_Archives

최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 위와 같은 예시 트리 구조에서, 13, 15번 정점의 최소 공통 조상은 5번 정점이 된다. 마찬가지로, 13, 11번 정점의 최소 공통 조상은 1번 정점(Root)이 된다. LCA를 선형 탐색으로 구하기 : O(Depth) 트리에서 이러한 최소 공통 조상을 찾으려면 어떤 방식을 사용해야 할까? 가장 단순한 방법으로는, 두 포인터를 두고 가리키는 정점이 같아질 때까지 부모 노드로 거슬러 올라가면 될 것이다. 즉 Parent[x]를 정점 x의 부모 노드라 할 때, x = Parent[x] 연산을 반복하면 될 것이다. 하지만 구하고자 하는 두 정점의 ..

문제 링크 : www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 게임을 무한히 할 수 있는 경우는 어떤 경우일까? 일련의 순서로 각 칸을 방문할 때, 이미 한 번 방문했던 칸을 다시 방문할 수 있다면 게임을 무한히 진행할 수 있다. 즉, 게임판 내에서 사이클이 발생하는 경우이다. 따라서, 제시된 2차원 배열의 각 칸을 정점으로 하는 그래프를 구성한 후 1번 정점으로부터 시작해 백트래킹을 통해 최대로 갈 수 있는 거리를 구하면 된다. (이 과정에서 사이클을 발견..

문제 링크 : www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 보석의 개수가 최대 14개이므로, 어떤 보석을 주운 상태인지 비트마스크를 통해 나타낼 수 있음을 캐치하자. 보석이 있는 섬에 도착했을 때, 보석을 주운 후 다음 섬으로 이동할 수도 있고 줍지 않고 이동할 수 있다. 위와 같은 예제 그래프에서, 1번 노드에서 출발해 최대로 보석을 주웠을 때의 개수는 4이다. 경로는 다음과 같다. ① 1번 섬에서 보석을 줍지 않고 5번 섬으..

문제 링크 : www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 다음과 같은 그래프에서, 파란색 간선을 최소로 사용하는 스패닝 트리를 찾아보자. 파란색 간선을 최소로 사용했을 때의 스패닝 트리이다. 이는 곧, 예시 그래프에서 스패닝 트리를 구성하기 위해서는 최소 2개의 파란색 간선이 필요하다는 것을 의미한다. 즉 5-7, 6-8의 파란색 간선을 사용하지 않고서는 예시 그래프의 스패닝 트리를 구성할 수 없다. 그렇다면 마찬가지로 이번에는 파란색 간선을 최..

문제 링크 : 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개의 정점이 포함되어..