📂 자료구조/트리

세그먼트 트리(Segment Tree)

1. 개념 🛫 세그먼트 트리(Segment Tree)란 여러 개의 데이터가 존재할 때 특정 구간의 합을 구하는 데 사용하는 자료구조이다. 트리 종류 중 하나로 이진트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. O(log N) 2. 동작방식 🚁 세그먼트 트리를 이용하기 위해서는 우선 '구간 합 트리'를 생성해야 한다. 그리고 '구간 합을 구하는 함수'와 '원소를 수정하는 함수'를 이용하여 구간 합을 구하고 특정 원소를 수정할 수 있다. '1 9 3 8 4 5 5 9 10 3 4 5'라는 12개의 원소를 가진 배열이 주어졌을 때 세그먼트 트리를 이용하여 구간 합을 구해보자. 1. 구간 합 트리 생성하기 '구간'은 원래 데이터 범위를 반씩 분할하는 것으로 설정한다. 최상단 노드..

[자료구조] 힙(Heap)

1. 정의 🐳 힙(Heap)이란 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 힙의 특징 완전 이진트리의 일종이다. 반정렬 상태이다. 최대힙(Max Heap) 또는 최소힙(Min Heap)에 따라서 루트 노드가 항상 가장 큰 값이거나 가장 작은 값을 유지하기 때문이다. 중복된 값을 허용한다. 힙의 종류 최대 힙 (Max Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 형식 최소 힙 (Min Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 형식 2. 동작 방식 🐟 인덱스 0 1 2 3 4 5 6 7 8 값 - 9 7 6 4 5 1 3 8 Heap은 배열을 통해 쉽게 구현이 가능하다. 그 이유는 힙이 완전 이진트리이..