자료구조 썸네일형 리스트형 세그먼트 트리 라이브러리 개발(C++) #1 지금까지는 세그먼트 트리 문제 풀 때마다 새로 구현했었는데, 오늘 엉겁결에 세그먼트 트리 라이브러리를 개발해 보았습니다. 지금까지 사용해 본 C++ STL을 떠올리면서 최대한 비슷하게 만드려 노력했는데 충분히 쓰기 편한지는 모르겠네요ㅠㅠ 구간 쿼리와 점 업데이트를 처리할 수 있고 구간 업데이트는 아직 처리하지 못합니다. 멤버 변수 T* tree - 세그먼트 트리를 나타낼 배열(을 동적할당할 포인터)입니다. T* arr - 세그먼트 트리에 저장할 원소들을 담은 배열(을 동적할당할 포인터)입니다. int size, cap - 각각 원래 배열의 크기, 세그먼트 트리 배열의 크기를 나타냅니다. T(*oper)(T, T) - 세그먼트 트리의 리프 노드가 아닌 노드의 값은 두 자식 노드의 값을 덧셈, min/max.. 더보기 세그먼트 트리 소개 세그먼트 트리는 구간에 대한 연산을 $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];.. 더보기 트리 기초(의미, 구현, 용어, 종류) 지난 게시물에서 그래프에 대해 공부했습니다. 트리는 그래프의 특수한 형태입니다. 정말정말 다양하게 활용될 수 있는 재미있는 자료구조입니다. 트리란? 사이클이 없는 연결 그래프를 트리라고 부릅니다. 가중치와 방향 여부는 별로 중요하지 않습니다. 무슨 말인지 모르겠다면 지난 게시물을 참고하세요. 해당 형태의 그래프가 나무를 뒤집어 놓은 모양과 비슷해 트리라고 이름이 붙었다고 합니다. 트리의 용어 기본적으로는 그래프의 용어를 그대로 사용합니다. 보통 '정점' 대신 '노드'라는 용어를 많이 쓰는 것 같습니다. 루트 노드 : 트리의 맨 꼭대기에 위치할 정점을 이야기합니다. 임의로 설정할 수 있습니다. 부모/자식 노드 : 이웃한 두 정점 중 루트 노드와 더 가까운 정점이 부모, 다른 정점이 자식이 됩니다. 형제 노.. 더보기 그래프 기초(의미, 분류, 구현 방법) 기초소개 그래프는 자료구조의 일종으로, 배열과 달리 데이터간의 관계를 나타낼 수 있는 자료구조입니다. 형태에 따라 각기 다른 특성을 가지고 있기 때문에 여러 세부 분류로 나뉘기도 합니다. 그래프란? 데이터에 해당하는 정점과 정점을 이으며 정점끼리의 관계를 나타내는 간선으로 이루어진 자료구조입니다. 위 그림처럼 생긴 자료구조입니다. 이 그래프는 무엇을 나타내는 그래프일까요? 정점을 사람, 간선을 친구 관계로 표현한다면 집단에서 친구인 사람들을 표현하는 그래프가 됩니다. 정점을 도시, 간선을 길으로 생각한다면 지도처럼 도시 사이를 이동하는 경로를 표시하는 그래프가 됩니다. 이처럼 정점과 간선을 적절히 설정한다면 그래프가 많은 것들을 나타내도록 할 수 있습니다. 간선의 방향 방향은 일방 통행 도로처럼 간선에서.. 더보기 이전 1 다음
