트리 (Tree)트리의 정의트리는 한 개 이상의 노드로 이루어진 유한 집합으로서노드 중에는 루트(root)라고 하는 노드가 하나 있고나머지 노드들은 n개의 분리 집합 T1, T2, ..., Tn으로 분할 될 수 있다. 이때, 분리 집합 T1, T2, ..., Tn은 각각 하나의 트리이며 루트의 서브트리라고 한다.트리의 구조 및 용어트리 용어차수(degree): 어떤 노드의 자식 개수리프(leaf) 또는 단말(terminal) 노드: 차수가 0인 노드자식(children): 어떤 노드 X의 서브트리의 루트들부모(parent): 어떤 노드 X형제(sibling): 부모가 같은 자식들트리의 차수(degree of tree): 그 트리에 있는 노드의 최대 차수조상(ancestor): 루트에서 그 노드까지의 경로..

이중 연결 리스트 (Doubly Linked List)기존 연결 리스트는 단순히 한 방향으로만 이동할 수 있었다. 양방향에 대한 포인터를 가지는 노드를 사용하면 양방향으로 이동할 수 있는 이중 연결 리스트를 구현할 수 있다.양방향 노드template class BidirectionalNode{ public: BidirectionalNode(T data) { this->data = data; } T data; BidirectionalNode* left = nullptr; BidirectionalNode* right = nullptr;};노드 삽입양쪽 노드에 대한 포인터 처리만 해주면 된다.// 삽입void Insert(Bidir..

연결 리스트의 다항식 표현연결 리스트의 각 노드가 한 개의 항을 표현하게 하면 노드를 이어 붙여 다항식을 표현할 수 있다.Term 구조체각 항을 나타내기 위해 구조체를 사용계수지수Set 함수: 구조체의 값을 설정// 각 항을 나타내는 구조체struct Term{ int coef; // 계수 int exp; // 지수 Term Set(int c, int e) { coef = c; exp = e; return *this; }};연결 리스트단순 연결 리스트를 사용한다. 각 노드는 data(coef, exp)와 next로 구성된다.SinglyLinkedList poly; // 다항식 => data(coef, exp), next로 구성다항식 클래스다..

연결 스택 (Linked Stack)연결 리스트를 사용해 스택을 구현한 것스택에 Push 할 때는 새로운 노드의 포인터를 top을 가리키게 해 스택의 맨 위에 올라오게 한 후, 새로운 노드를 top으로 설정한다.Pop하는 경우 top을 다음 노드로 옮긴 후, 맨 위에 있는 노드를 삭제한다.코드#include "../Node.hpp"#include template class LinkedStack{public: bool IsEmpty() { if (top == nullptr) return true; else return false; } Node* Top() { if (!IsEmpty()) ..

가용 공간 리스트 (Available-Space List)기존 단순 연결 리스트와 원형 리스트에서의 노드를 생성하고 삭제하는데 시간이 소요된다. 만약 삭제된 노드를 다른 장소에 유지한다면 노드를 새로 생성하고 삭제하는 시간을 O(1)로 줄일 수 있다. 이를 구현하기 위해선 삭제된 노드를 연결해놓을 리스트가 필요한데, 이를 가용 공간 리스트라 한다.Node* av = nullptr; // available-space list노드 생성과 삭제가용 공간 리스트가 있다면, 노드의 생성과 삭제에 new와 delete를 사용하지 않고 가용 공간 리스트에서 노드를 가져오는 함수를 사용하면 된다.// 가용 공간 리스트(av)에서 사용할 노드 가져옴// new 키워드로 노드 객체 생성하는 것 대신 사용Node* GetN..

단순 연결 원형 리스트 (Singly Linked Circular List)기존 연결 리스트에서 마지막 노드의 포인터가 첫 번째 노드를 가리키게 하면 된다.원형 리스트의 마지막 노드 검사기존 단순 연결 리스트에서는 마지막 노드를 검사하기 위해 포인터가 nullptr인지 검사하면 됐지만, 원형 리스트에서는 포인터가 head인지 검사하면 된다.원형 리스트의 삽입기본적인 작동 방식은 단순 연결 리스트와 같으나, 다음 경우에는 따로 처리를 해줘야 한다.리스트의 맨 앞에 삽입하는 경우, 마지막 노드의 포인터가 새로 삽입한 노드를 가리키게 한 후 head로 설정만약 맨 마지막 노드를 가리키는 rear가 있는 경우, rear의 포인터가 새 노드를 가리키게 설정해주면 O(1)으로 삽입 가능리스트의 맨 뒤에 삽입하는 경..

연결 표현배열을 사용한 순차 저장 방법은 임의의 원소에 접근하거나 스택이나 큐에 원소를 삽입하거나 삭제하는 것과 같은 작업에 적합하다.하지만 삽입, 삭제가 자주 일어나거나 리스트의 크기가 변하는 경우 매우 불리한 구조가 된다. (예를 들어, 배열의 경우 원소 하나를 삭제하면 뒤에 있는 모든 원소를 앞으로 당겨야 하고, 리스트의 크기를 변경하려면 새로운 공간을 할당받은 후 기존 데이터를 모두 복사해야 함) 연결된(linked) 표현의 특징은 다음과 같음각 원소들이 메모리의 어떤 곳에나 위치할 수 있음 (물리적으로 순차적인 위치에 존재할 필요 없음)각 원소와 함께 그 다음 원소를 가리키는 주소 또는 위치를 저장함 (포인터 또는 링크라 함)연결 리스트는 배열과 비교해 동적 크기 조정이 가능한 것이 장점단순 연..

후위 표기법우리가 평소에 쓰는 수식 표기법은 중위 표기법(infix notation)이다. 하지만 연산자에는 우선순위가 있기 때문에 컴퓨터에서는 이를 후위 표기법(postfix notation)으로 변환해 매우 쉽게 수식을 계산할 수 있다. 후위 표기법은 연산자가 피연산자들 뒤에 온다.중위 표기법: A/B-C + D*E - A*C후위 표기법: AB/C-DE*AC*-후위 표기법은 다음과 같은 이유로 계산을 쉽게 만든다.괄호의 필요성이 없어짐연산자 우선순위의 의미가 없어짐infix에서 postfix로 변환하면서 연산자 계산 순서까지 순서대로 들어오기 때문에 계산 과정에서는 단순히 왼쪽부터 쭉 읽어나가면 된다.중위 표현법 -> 후위 표현법 변환해당 변환 과정에서 연산자를 저장하는 스택이 중요하게 사용된다.연산..