Seungsu Hwang

이진 검색 트리(BST, Binary Search Tree) - 부모 노드의 값 >= 왼쪽 자식 노드의 값 - 부모 노드의 값 left); del_all(p->right); delete p; } } BST 구현 및 실행 결과 * BST에서 중위 순회를 실행하면 오름차순으로 모든 BST의 원소를 출력한다. #include using namespace std; class bin_sch_tree { struct node { int data; node* left; node* right; }; node* root = nullptr; node* find_impl(node* curr, int val) { if (!curr) return NULL; if (curr->data == val) return curr; // ..

선형 자료구조의 단점과 비선형 자료구조 선형 구조에서는 두가지 방향(순방향과 역방향)으로 자료를 순회할 수 있다. 이러한 구조는 매우 제한적이어서 복잡한 문제에는 적용하기 어려운 경우가 많다. 선형 자료구조로 표현할 수 없는 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. (계층적 구조 -> 트리, 순환 종속성 -> 그래프로 구현) 비선형 자료구조의 트리와 트리의 특별한 형태인 힙 그리고 그래프를 통해서 좀 더 복잡한 문제를 해결할 수 있다. [데이터베이스(B-트리), 데이터 인코딩/압축(허프만 트리), 그래프 컬러링, 할당 문제, 최소 거리 문제 등] 1. 트리 트리는 노드와 노드 사이를 연결하는 엣지(Edge, 간선)를 이용하여 계층을 구성한다. 트리의 중심이 되는 노드를 루트 노드(Roo..

1. std::deque 덱(deque)은 양방향 큐(double-ended queue)의 약자로 배열 기반과 연결 리스트 기반 컨테이너가 각각 섞여있는 형태이다. 따라서 각각의 장점을 적당히 가지고 있다. C++ 표준의 덱에 따르면 덱은 양방향으로 매우 빠르게 확장할 수 있어야 하며, 모든 원소에 O(1)의 임의 접근을 제공해야 한다. 그러므로 자료구조가 벡터와 비슷하지만, 앞 뒤로 모두 확장할 수 있다는 점이 다르다. 덱은 단일 메모리 청크가 아닌 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다. 이 경우 청크의 인덱스 및 크기를 이용하여 특정 위치의 원소가 어느 청크에 저장되어 있는지 알 수 있다. 모든 메모리 청크 주소를 연속적인 메모리 구조에 저장해놓고 사용하면 O(1)의 시간 ..

반복자의 종류 반복자는 포인터와 비슷하지만, STL 컨테이너에 대해 공통의 인터페이스를 제공한다. 반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다. 예를 들어 vector나 array처럼 연속된 자료 구조의 반복자는 특정 위치의 원소에 곧바로 접근할 수 있다. 이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다. 하지만 forward_list의 경우 기본적으로 역방향으로 이동하는 기능이 없고, 바로 이전 노드로 이동하려면 맨 처음 노드부터 시작해서 찾아가야 한다. 따라서 forward_list에서는 증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(forward iterator)라고 한다. 반복자 함수: advance(), next(), p..