힙(Heap) 힙의 특징은 다음과 같다. - 최대 원소에 즉각적으로 접근할 수 있다. O(1) - 원소 삽입과 삭제에 대해 O(logN)의 시간복잡도를 만족한다. 이러한 특징을 만족하기 위해 완전이진트리(Complete Binary Tree)를 이용한다. * 완전 이진트리: 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식이 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드 존재 위와 같은 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없다. 그렇기 때문에 메모리 사용 측면에서 효율적이다. 부모노드에서 자식노드로 이동하는 것은 배열의 인덱스 계산으로 쉽게 이루어진다. 예를 들어, 부모 노드의 인덱스가 i라면, 자식 노드의 인덱스는 2 * i + 1, 2 * i + 2이다. 반대로 자..
https://dev-haram.online/67 [2. 트리, 힙, 그래프] 이진 검색 트리(Binary Search Tree) 이진 검색 트리 (Binary Search Tree) 이진 검색 트리는 다음과 같은 속성을 갖는 이진 트리이다. - 부모 노드의 값 >= 왼쪽 자식 노드의 값 - 부모 노드의 값 18, 15 < 18, 17 < 18 이기 때문에 위 그림처럼 17 dev-haram.online 앞선 게시글에서 이진 검색 트리에 대해 정리했다. 이진 검색 트리의 시간 복잡도에 대해 서술할 때, 트리의 삽입 순서에 따라 시간 복잡도가 달라진다고 언급했었다. 이를 조금 더 자세히 살펴보면, 위 그림에서 왼쪽 트리와 오른쪽 트리를 비교해보면, 오른쪽 트리가 더 균형이 잡혀있다고 할 수 있다. 균형 트..
이진 검색 트리 (Binary Search Tree) 이진 검색 트리는 다음과 같은 속성을 갖는 이진 트리이다. - 부모 노드의 값 >= 왼쪽 자식 노드의 값 - 부모 노드의 값 18, 15 < 18, 17 < 18 이기 때문에 위 그림처럼 17의 오른쪽 하위노드에 18이 삽입된다. BST에서 원소 삭제하기 BST에서 원소를 삭제할 때에는 단순히 노드를 삭제하는 것 뿐만 아니라, 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 해야 한다. 이를 위해서 첫 번째단계로 삭제할 노드를 찾는다. 이후에는 해당 노드의 자식 노드에 따라 수행할 행동이 달라지게 된다. 1) 삭제할 노드의 자식 노드가 없는 경우: 단순히 해당 노드를 삭제하면 된다. 2) 삭제할 노드의 자식 노드가 하나인 경우: 노드 삭제 후, 부..
선형 자료 구조로 표현할 수 없는 대표적인 문제로 계층적 문제(hierarchical problem)와 순환 종속성(cyclic dependency) 문제가 있다. 회사의 조직도, 대학의 교과 과정 계층도 등은 계층적으로 데이터를 표현해야 한다. 이 때 사용하는 자료 구조는 트리 (tree)이다. 위 그림처럼 트리는 계층을 구성한다. 데이터가 저장된 부분은 노드(node)라고 부르고, 노드와 노드 사이를 잇는 선을 edge라고 부른다. 가장 맨 위에 나타나는 노드를 root node라고 한다. 트리의 기본 구조에 대한 요약이었고, 트리의 원소를 순회하는 방법은 세 가지로 나뉜다. 전위 순회 (preorder traversal) 이 방법은 현재 노드를 먼저 방문하고, 그 다음은 현재 노드의 왼쪽 하위 노드..
컨테이너 어댑터(container adaptor) 기존의 컨테이너를 변형하여 꼭 필요한 인터페이스만을 제공하여 만든 컨테이너로, C++에서 제공하는 컨테이너 어댑터는 std::stack, std::queue, std::priority_queue가 있다. std::stack std::stack은 std::deque을 기본 컨테이너로 사용한다. 데이터 처리와 보관을 위해 LIFO(Last In First Out, 후입선출) 구조를 사용하고 한쪽 끝에서만 데이터의 삽입과 삭제가 이루어진다. 벡터와 덱에서 이러한 기능을 기본적으로 지원하지만, 직접 스택처럼 사용하기에는 기능이 너무 많다. 그래서 의도하지 않은 동작과 코드를 잘못 작성하는 경우를 방지하기 위해 스택에 꼭 필요한 인터페이스만을 제공한다. 아래 코드..
std::deque 벡터는 가변 길이 배열이고, push_front() 또는 pop_front() 같은 함수는 비용이 많이 든다. (다 하나씩 밀어줘야 함) std::deque를 통해 이런 단점을 극복할 수 있다. (double-ended queue) 덱(deque)의 구조 - push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 한다. - 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 한다. - 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n/2 단계로 동작한다. (n: 덱의 크기) - 덱은 자료구조가 벡터와 비슷하지만 앞쪽과 뒤쪽으로 보두 확장할 수 있다. -..
std::list std::forward_list는 아주 기본적인 형태로 구현된 연결 리스트이다. 리스트 끝에 원소 추가, 역방향 이동, 리스트 크리 반환 등의 기능은 제공하지 않는다. (메모리와 성능 유지를 위해) forward_list는 반복자의 기능도 적다. 이러한 forward_list의 단점을 보완하기 위해 C++ 은 std::list를 제공한다. std::list는 양쪽 방향으로 연결된 이중 연결 리스트(doubly-linked list) 구조로 되어 있어 더 많은 기능을 제공하지만 메모리는 조금 더 사용한다. struct doubly_linked_list_node{ int data; doubly_linked_list_node* next; doubly_linked_list_node* prev;..
std::forward_list 배열, 벡터 같은 연속된 자료 구조에서는 데이터 중간에 자료를 추가하거나 삭제하는 작업이 매우 비효율적이다. std::forward_list는 C++에서 제공하는 기본적인 연결 리스트에 대한 래퍼 클래스이다. 원소의 삽입, 삭제, 순서 뒤집기, 분할 등의 기능은 제공하지만 성능 유지를 위해 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 접근하는 기능은 제공하지 않는다. vector와 마찬가지로 사용자 지정 할당자를 지정하여 메모리 관리를 더욱 효율적으로 수행할 수 있다. 원소 삽입 원소 삽입은 노드 포인터 조작으로 구현되므로 삽입 후 다른 원소를 이동할 필요가 없다. 그렇기 때문에 배열 기반 구조에서의 삽입 함수에 비해 매우 빠르게 동작한다. 리스트..
