아래 글 내용에서 이어지는 내용이므로 아래 글을 보고 오는 것을 추천한다. https://seongmoahn.tistory.com/107 8-3. [C/C++] 힙(Heap) 구현 힙이란? 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙을 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 큰/작은 완전 seongmoahn.tistory.com 힙에서의 삽입 연산 힙에 새로운 요소가 들어오면, 일단 완전 이진트리의 조건을 만족하는 마지막 위치에 삽입한다. 그러면 대부분의 경우 힙 트리의 조건을 만족하지 않을 것이다. 그래서 삽입 후에 부모 노드와 비교하며 조건의 맞는 자리를 찾는다. 삽입 연산의 구현 삽입 연산의 알고리즘을 알아보자. ins..

힙이란? 힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙을 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 큰/작은 완전 이진 트리이다. 이진 탐색 트리와 달리 힙 트리는 중복된 값을 허용한다. 앞에서 힙은 반 정렬의 상태를 유지한다고 했었다. (최대)힙은 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰/작은 값을 효율적으로 찾아내기만 하면 되는 것이기 때문에 전체 요소들을 정렬할 필요는 없다. 왼쪽 그림과 같이 부모 노드의 키 값이 자식 노드의 키 값보다 큰 경우를 최대 힙(max heap)이라고 부른다. 오른쪽 그림과 같이 부모 노드의 키 값이 자식 노..

우선순위 큐의 구현 방법 우선순위 큐를 구현하는 방법은 여러가지가 있다. (배열, 연결 리스트, 힙 등) 배열을 이용하는 방법 정렬되지 않은 배열을 이용하는 방법 정렬되지 않은 배열을 사용하면 삽입 연산은 간단하다. 그냥 기존 요소들 맨 끝에 새로운 데이터를 붙이면 된다. 따라서 시간 복잡도는 O(1)이 된다. 그러나 삭제 연산의 경우는 요소들을 처음부터 끝까지 검사하면서 우선순위가 가장 높은 요소를 찾아야 한다. 배열이 정렬되어 있지 않기 때문이고, 이때 시간 복잡도는 O(n)이 된다. 삭제를 한다고 끝이 아니다. 삭제한 요소 뒤에 있는 요소들을 앞으로 한 칸씩 이동시키는 작업도 필요하다. 정렬된 배열을 이용하는 방법 정렬이 되어 있는 배열에 새로운 요소를 삽입하는 경우 기존 요소들과 우선순위를 비교하..

우선순위 큐란? 우선순위 큐를 알아보기 전에 롯데월드의 매직패스에 대해 이야기해보자. 롯데월드에서 놀이기구를 타기 위해서는 줄을 서서 순서를 기다려야 한다. 이 순서는 선입선출의 특징을 갖는 큐와 같다. 그런데 롯데월드에는 매직패스라는 시스템이 있다. 기본적으로 먼저 줄을 선 사람이 먼저 놀이기구를 타게 되지만 매직패스를 구입한 사람은 줄을 기다리지 않고 빠르게 기구를 탈 수 있다. 이 사람이 대기줄에서 우선순위를 갖게 되는 것이다. 롯데월드의 매직패스와 같은 개념이 우선순위 큐이다. 우선순위 큐도 일단 큐 자료구조기 때문에 큐와 동일하게 선입선출로 동작한다. 하지만 우선순위(priority)를 갖는 데이터가 큐에 삽입된다면 그 데이터가 다른 데이터들보다 먼저 삭제된다. 컴퓨터에서도 우선순위의 개념이 필..

이진 탐색 트리의 성능 분석 트리의 높이가 h라고 할 때 탐색/삽입/삭제 연산의 시간 복잡도는 O(h)가 된다. 비교적 이상적인 구조라고 할 수 있는 포화 이진 트리나 완전 이진 트리를 생각했을 때 노드의 개수가 n개라면 ⌈log2(n+1)⌉의 높이를 갖는다. 이런 경우 이진 탐색 트리의 연산 시간 복잡도는 O(log2(n))가 된다. O(log2(n))의 수치는 선형 탐색의 시간 복잡도 O(n)과 비교했을 때 엄청나게 효율적인 것을 알 수 있다. 하지만 이것은 이진 탐색 트리의 구조가 비교적 이상적일 때의 얘기이다. 만약 한쪽으로 치우친 이진 탐색 트리인 경우 트리의 높이 h는 노드의 개수 n개와 같아진다. 이 경우 이진 탐색 트리의 연산 시간 복잡도는 선형 탐색과 동일한 O(n)이 된다. 이진 탐색 ..

이진 탐색 트리의 삭제 연산 앞 내용과 이어지므로 앞 내용을 보지 않았다면 아래 링크를 통해 보는 것을 추천한다. https://seongmoahn.tistory.com/101 7-3. [C++] 이진 탐색 트리의 삽입 연산 이진 탐색 트리의 삽입 연산 앞 내용과 이어지므로 앞 내용을 보지 않았다면 아래 링크를 통해 보는 것을 추천한다. https://seongmoahn.tistory.com/100 7-2. [C++] 이진 탐색 트리의 탐색 연산 이진 탐색 트 seongmoahn.tistory.com 이진 탐색 트리의 연산 중 삭제 연산이 가장 복잡하다. 삽입 연산과 마찬가지로 삭제 연산도 트리를 먼저 탐색해야 한다. 그리고 삭제 연산은 다음 3가지 경우를 고려해야 한다. 삭제하려는 노드가 단말 노드인 ..

이진 탐색 트리의 삽입 연산 앞 내용과 이어지므로 앞 내용을 보지 않았다면 아래 링크를 통해 보는 것을 추천한다. https://seongmoahn.tistory.com/100 7-2. [C++] 이진 탐색 트리의 탐색 연산 이진 탐색 트리의 탐색 연산 앞 내용과 이어지므로 앞 내용을 보지 않았다면 아래 링크를 통해 보는 것을 추천한다. https://seongmoahn.tistory.com/99 7-1. [C++] 이진 탐색 트리란? 탐색이란? 탐색(search)은 seongmoahn.tistory.com 이진 탐색 트리에 새로운 노드를 삽입하기 위해서는 먼저 탐색을 수행해야 한다. 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하며, 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 되기 ..

이진 탐색 트리의 탐색 연산 앞 내용과 이어지므로 앞 내용을 보지 않았다면 아래 링크를 통해 보는 것을 추천한다. https://seongmoahn.tistory.com/99 7-1. [C++] 이진 탐색 트리란? 탐색이란? 탐색(search)은 컴퓨터 응용 중 가장 중요한 것들 중 하나이다. 컴퓨터에는 데이터들이 저장되어 있고 이 데이터들 중에서 필요한 데이터를 찾아내는 작업은 빈번한 작업이다. 컴퓨터에 seongmoahn.tistory.com 이진 탐색 트리에서 어떤 키 값을 가진 노드를 찾기 위해서는 먼저 주어진 키 값과 현재 루트 노드의 키 값을 비교해야 한다. 찾으려는 키 값과 현재 트리의 루트 노드의 키 값을 비교한다. 비교한 결과가 같으면 탐색은 종료된다. 찾으려는 값이 루트 노드의 값보다 ..