트리 썸네일형 리스트형 세그먼트 트리 소개 세그먼트 트리는 구간에 대한 연산을 $O(logN)$만에 처리할 수 있는 자료구조입니다. 난이도 높은 문제에서 다양한 방식으로 활용되는 자료구조이기도 합니다. 구조 이진 트리의 형태이며, 각 노드는 특정 구간의 값을 저장하고 있습니다. 이 값은 구간의 합, 최솟값 등 다양한 값이 될 수 있습니다. 루트 노드는 전체 구간에 대한 값을 저장하며, 루트 노드에서 멀어질수록 담당하는 구간이 작아지다 리프 노드에 도달하면 원소 하나만을 담당하게 됩니다. 연산 기본적으로 원소 하나를 변경하는 연산과 특정 구간의 값을 구하는 연산을 처리할 수 있습니다. 구간 합을 구하는 세그먼트 트리의 코드를 예시로 설명하겠습니다. 원소 변경 1 2 3 4 5 6 7 8 9 10 void change(int now, int l.. 더보기 유니온 파인드 트리(분리 집합) 소개 유니온 파인드 트리는 교집합이 없는 여러 집합들을 나타내는 자료구조입니다. 집합을 합치는 연산과 원소가 속해 있는 집합을 구하는 연산을 상수 시간에 처리할 수 있습니다. 구조 유니온 파인드 트리는 여러 개의 트리가 모여 있는 구조입니다. 각각의 트리는 집합 하나를 나타내며, 트리의 루트 노드의 번호가 해당 집합을 대표합니다. 배열에서 각 노드의 부모 노드 번호를 저장하고 있으며, 배열에서 재귀함수를 통해 부모 노드를 타고 올라가 루트 노드를 찾는 방식으로 구현합니다. 구현 i번 노드가 속해 있는 집합의 루트 노드를 구하는 find(i) 연산과 i, j번 노드가 속해 있는 두 집합을 합치는 union(i, j) 연산을 구현해야 합니다. find 연산 1 2 3 4 5 6 int par[100005];.. 더보기 트리 기초(의미, 구현, 용어, 종류) 지난 게시물에서 그래프에 대해 공부했습니다. 트리는 그래프의 특수한 형태입니다. 정말정말 다양하게 활용될 수 있는 재미있는 자료구조입니다. 트리란? 사이클이 없는 연결 그래프를 트리라고 부릅니다. 가중치와 방향 여부는 별로 중요하지 않습니다. 무슨 말인지 모르겠다면 지난 게시물을 참고하세요. 해당 형태의 그래프가 나무를 뒤집어 놓은 모양과 비슷해 트리라고 이름이 붙었다고 합니다. 트리의 용어 기본적으로는 그래프의 용어를 그대로 사용합니다. 보통 '정점' 대신 '노드'라는 용어를 많이 쓰는 것 같습니다. 루트 노드 : 트리의 맨 꼭대기에 위치할 정점을 이야기합니다. 임의로 설정할 수 있습니다. 부모/자식 노드 : 이웃한 두 정점 중 루트 노드와 더 가까운 정점이 부모, 다른 정점이 자식이 됩니다. 형제 노.. 더보기 백준 13306번 트리 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 풀이 마지막에 받은 쿼리부터 역순으로 실행하는 것이 풀이의 핵심입니다. 트리의 간선을 끊는 동작은 처리하기 어렵지만, 두 정점을 잇는 연산은 유니온 파인드를 통해 쉽게 할 수 있기 때문입니다. 따라서 트리에서 간선을 하나씩 끊는 것이 아니라 모든 정점이 연결되지 않은 상태에서 쿼리를 역순으로 보며 각 쿼리에 대해 다음과 같이 실행합니다. 쿼리 1 : 0 b 원래 명령과 반대.. 더보기 이전 1 다음
