4Legs_Archives

문제 링크 : www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net [필요한 개념 : LCA (이분 탐색)] 최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상 (최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을 의미한다. 위와 같은 예시 트리 구조에서, 13, 15번 4legs-study..

문제 링크 : www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제에서 제시된 그래프가 트리임에 주목하자. 트리에서는 두 정점을 잇는 경로가 유일하기 때문에, LCA를 통해 트리에서 두 정점의 거리를 구할 수 있다. 최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상 (최소 공통 조상 (LCA, Lowest Common Ancestor) 최소 공통 조상은 트리 구조에서 임의의 두 정점이 갖는 가장 가까운 조상 정점을..

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

문제 링크 : 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)가 된다. 즉, 트리의 형태와 상관없이 각 리프 노드(피연산자 노드)까지 도달했을 때, 해당 피연산자가 최종 식에서 어떤 부호를 갖는지만 파악하면 문제를 쉽게 해결할 수 있다. 만약 최종 식에서..

[서론] 크기가 1000인 배열이 있다. 이 배열의 각 원소는 1부터 10까지의 수이다. 이때 i번째 원소부터 j번째 원소까지의 합을 구하고 싶다. 어떤 방법이 좋을까? 가장 먼저 떠오르는 것은 누적합을 이용한 방법일 것이다. Sk를 Arr[0] ~ Arr[k] 까지의 모든 원소의 합이라 정의할 때, 누적합을 이용해, 구간 (i, j)의 구간합을 Sj - S(i - 1) 로 O(1)에 구할 수 있다. 이 때, Arr의 원소 중 일부가 변경된다면 어떻게 될까? 올바른 구간합을 구하기 위해서는, 누적합을 저장해 놓은 배열을 다시 갱신해야 할 것이다. 배열의 크기가 N이고, 배열값의 변경이 M회 일어날 때 Worst Case에 시간복잡도는 O(NM)이 된다. 이는 N, M의 크기가 어느 정도 커지면 시간 효율..