Hello, Freakin world!

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 종만북의 유니온 파인드 코드를 참조한 풀이입니다. 주의할만한 몇 가지 포인트에 대해서만 짚고 가겠습니다. 1. 이름을 int형의 id값으로 변환 문자열로는 트리를 구성하기 불편하기 때문에 int형으로 변환했습니다. 2. find 연산에서의 경로 최적화 이는 중복 연산을 피하기 위해 트리의 구조를 수정하는 작업입니다. find를 수행할 때마다 루트를 찾음과 동시에 경로에 있는 노드의 parent를 모두..

힙은 특정한 규칙을 만족하도록 구성된 이진 트리입니다. 이를 사용하면 최대[최소] 원소들을 log(N)의 복잡도로 찾아낼 수 있습니다. 규칙 - 힙의 대소 관계 - 힙의 모양 규칙 힙의 대소 관계 힙의 대소 관계는 부모 자식 관계에만 적용됩니다. 형제 간의 대소 관계는 신경쓰지 않습니다. 이 규칙으로 인해 항상 최대[최소] 원소가 루트에 위치하기 때문에 빨리 찾아낼 수 있습니다. 힙의 모양 규칙 모양 규칙에는 두 가지가 있습니다 1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. 2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다. 이 두 가지의 모양 규칙이 만족하면 노드의 개수만으로 트리의 모양이 정해지기 때문에 1차원 배열로 트리를 표현할 수 있습니다..

구간 트리란? 구간 트리의 정체는 이진 트리입니다. 구간 트리 라는 이름은 그저 특정 용도로 사용되는 이진 트리의 한 형태를 나타낼 뿐입니다. 대게 구간 트리는 일차원 배열 상의 특정 구간에 대한 요청에 빠르게 대답하기 위해 사용합니다. 예를 들어, 1 2 3 4 5 라는 숫자 배열이 있다고 하겠습니다. 이 배열의 특정 구간의 합을 구한다고 할 때, 가장 간단한 방법은 그 특정 구간을 순회하면서 값을 더해나가는 겁니다. 이 경우 시간 복잡도는 O(n)이 됩니다. 만약 배열의 길이가 10억쯤 된다면 어떨까요? 컴퓨터가 1초에 1억번 정도의 루프를 돌린다고 하면 10초가 걸리겠네요. 그리고 또 이 합연산이 여러번 호출될 가능성이 있다면 어떨까요? 이 연산은 매번 합을 새로 구하기 때문에 문제가 됩니다. 구간..