이진 트리(Binary Tree)하나의 노드가 자식 노드를 2개까지만 가질 수 있는 트리예시수식을 트리 형태로 표현하는 계산하는 수식 이진 트리(Expression Binary Tree)아주 빠른 데이터 검색을 가능하게 하는 이진 탐색 트리(Binary Search Tree)이진 트리의 종류노드의 최대 차수가 2임모든 이진 트리의 자식 노드 수는 0, 1, 2 중 하나포화 이진 트리(Full Binary Tree): 잎 노드를 제외한 모든 노드가 자식을 둘 씩 가진 이진트리잎 노드들이 모두 같은 깊이에 위치한다는 특징을 가짐완전 이진 트리(Complete Binary Tree): 잎 노드들이 트리 왼쪽부터 차곡차곡 채워져 있는 트리포화 이진 트리로 진화하기 전 단계임트리의 노드를 가능한 완전한 모습으로 ..

트리 ADT트리(Tree)란?나무를 닮은 자료구조HTML이나 XML 문서를 다룰 때 사용하는 DOM, 운영체의 파일 시스템 등이 트리 구조로 이루어져 있음트리의 구성요소트리는 뿌리, 가지, 잎 세 가지 요소로 이루어져 있다.세 가지 요소 모두 똑같은 노드이지만 어디에 위치하는지에 따라 불리는 이름이 달라진다뿌리 : 트리 자료구조의 가장 위에 있는 노드를 가리킴가지 : 뿌리와 잎 사이에 있는 모든 노드를 말함잎 노드(단말 노드) : 가지의 끝에 있는 마지막 노드를 잎 노드(단말 노드)라고 한다.부모, 자식 형제 관계가 존재한다. 위 그림을 봐보자노드 B, C, D를 보면 B에서 C와 D가 뻗어 나오는데 이때 B는 C와 D의 부모(Parent)이고, C와 D는 B의 자식(Children)이다.그리고 한 부모..

컨테이너 어뎁터(container adaptor)이미 존재하는 컨테이너를 기반으로 만들어진 컨테이너에 대해 알아본다각 자료구조에 대한 기본적인 내용은 이미 알고있다고 가정하고 글을 작성합니다!래퍼를 제공하는 이유코드에 의미를 부여의도하지 않는 함수를 실수로 사용하지 못하도록 제한특별한 인터페이스를 새롭게 제공std::stackLIFO 구조를 사용하기 때문에 스택은 컨테이너의 한쪽 끝에서만 데이터를 삽입/삭제한다벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다push_front()로 맨 앞 원소에 접근할 수 있기 때문에 벡터나 덱을 직접 사용하기에는 문제가 있다이와 달리 std::stack을 사용하여 작성된 소스 코드는 어떤 작업을 하고 있는지 직관적으로 알..

std::deque배열 기반 컨테이너와 리스트 기반 컨테이너 두 가지 방식이 섞여있는 형태각각의 장점을 적당히 가지고 있다vector에서 push_front(), pop_front() 에서 비용이 많이 드는 단점을 극복할 수 있다deque : 양방향 큐(double-ended-queue)의 약자덱의 구조C++ 표준은 덱의 동작에 있어 다음 조건을 만족해야 한다고 규정한다.push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야 함모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작해야 함덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작해야 하며, 실제로는 최대 n / 2 단계로 동작하며 여기서 n은 덱의 크..

std::list복습std::forward_list는 기본적인 형태로 구현된 연결 리스트임리스트 끝에 원소 추가, 역방향 이동, 리스트 크기 반환 등의 기능을 제공하지 않음빠른 원소 삽입이 필요한 모든 경우에 어울리는 container는 아니다.std::forward의 단점을 보완하기 위해 c++에서 std::list를 제공한다std::list양쪽 방향으로 연결된 리스트, 즉 이중 연결 리스트(doubly-linked-list) 구조로 되어 있다.따라서 더 많은 기능을 제공한다. (메모리는 조금 더 많이 사용한다)// 이중 연결 리스트 노드 기본 형태struct doubly_linked_list_node{ int data; doubly_linked_list_node* next; doubl..

Iterator(반복자)반복자는 포인터와 비슷하지만, STL container에 대한 공통의 interface를 제공한다.반복자를 이용한 연산은 어떤 컨테이너에서 정의된 반복자인지에 따라 결정된다.배열과 벡터의 경우 연속된 자료 구조를 사용하기 때문에 지정 위치의 원소에 바로 접근할 수 있다.이러한 반복자를 임의 접근 반복자(random access iterator)라고 한다.std::foward_list의 경우 역방향 이동을 제공하지 않으며, 이전 노드로 이동하려면 처음부터 다시 찾아가야 한다.증가 연산만 가능하며, 이러한 반복자를 순방향 반복자(foward iterator) 라고 한다.반복자 타입에 따라 사용할 수 있는 함수advance()반복자와 거리 값을 인자로 받고, 반복자를 거리 값 만큼 증가..

std::forward_liststd::array, std::vector와 같은 연속된 자료구조는 데이터 중간에 자료를 추가, 삭제하는 작업이 매우 비효율적임따라서 연결 리스트 기반 컨테이너가 등장함연결 리스트를 구성하는 중에 포인터와 관련된 버그 양산을 막기 위해 연결 리스트 wrapper class인 std::forward_list 클래스를 제공함std::forward_list의 기본적인 기능연결 리스트의 성능을 유지하면서 기본적인 기능을 제공함성능 유지를 위해 전체 리스트 크기를 반환하거나, 첫 번째 원소를 제외한 나머지 원소에 직접 접근하는 기능을 제공하지 않음front() 함수는 제공하지만, 거꾸로 움직이는 back() 함수는 제공하지 않음원소의 삽입, 삭제, 순서 뒤집기, 분할을 위한 기능은 ..

std::vectorstd::array의 단점std::array의 크기는 컴파일 시간에 결정되는 상수이어야 한다.런타임 중에 변경할 수 없다.크기가 고정되어 있어서 원소를 추가/삭제할 수 없다.항상 스택 메모리를 사용한다. 메모리 할당 방법을 바꿀 수 없다따라서 가변 크기의 데이터를 처리할 수 있는 컨테이너가 필요하다 --> std::vectorstd::vector - 가변 크기 배열배열 기반으로 구현되어 있다초기화 과정에서 데이터의 크기를 제공하지 않아도 된다std:array의 '고정 크기' 문제를 해결한다벡터를 초기화 하는 몇 가지 방법// 크기가 0인 벡터 선언std::vector vec;// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언std::vector vec = { 1, 2, 3, 4, ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.