전체 글

[이진 탐색 트리(Binary Search Tree)]이진 트리 기반이 탐색을 귀한 자료 구조입니다. 이진 탐색 트리의 정의● 모든 원소의 키는 유일한 키를 가진다.● 왼쪽 서브 트리 키들은 루트 키보다 작다.● 오른쪽 서브 트리의 키들은 루트의 키보다 크다.● 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.     순환적인 탐색연산순환적인 탐색 연산은 주어진 키를 가진 노드를 찾는 작업입니다. 이를 재귀적으로 수행할 수 있습니다.재귀적인 방법은 현재 노드와 키를 비교하고, 작으면 왼쪽 서브트리에서, 크면 오른쪽 서브트리에서 재귀적으로 탐색합니다. TreeNode* searchRecursive(TreeNode* root, int key) { // 루트가 없거나 루트가 키와 같으면 루트를 반환 ..

트리의 순회 방법은 주로 네 가지가 있습니다.전위 순회, 중위 순회, 후위 순회, 레벨 순회가 있습니다.  [전위 순회(Preorder Traversal)]전위 순회는 "루트 -> 왼쪽 -> 오른쪽" 순서로 노드를 방문합니다.알고리즘:1. 현재 노드를 방문한다.2. 왼쪽 서브트리를 전위 순회한다.3. 오른쪽 서브트리를 전위 순회한다.  전위 순회 구현#include using namespace std;// 노드 구조 정의struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) { data = val; left = nullptr; right = nullptr..

[트리]지금까지 리스트, 스택, 큐 등은 선형 자료 구조(linear data structure)를 알아보았습니다.이번에 알아보는 트리는 계층적인 구조(hierarchical structure)입니다. 트리의 용어루트 노드 (Root Node): 트리의 최상위 노드로, 부모 노드가 없습니다.부모 노드 (Parent Node): 자식 노드를 가지는 노드입니다.자식 노드 (Child Node): 부모 노드로부터 연결된 노드입니다.형제 노드 (Sibling Nodes): 동일한 부모를 가지는 노드들입니다.단말 노드, 리프 노드 (Leaf Node): 자식 노드가 없는 노드입니다.깊이 (Depth): 루트 노드로부터 특정 노드까지의 경로 길이입니다.높이 (Height): 특정 노드로부터 가장 깊은 리프 노드까지..

[연결 리스트로 구현한 스택] 이렇게 연결 리스트로 구현된 스택은 연결된 스택(linked stack)이라고 합니다.배열로 구현하나 연결 리스트로 구현하나 외부 인터페이스는 동일합니다.하지만 내부에서 구현에 차이가 있는데, 우선 연결 리스트를 사용해서 배열을 만들면 크기가 제한되지 않는다는 장점이 있습니다.물론 단점도 있는데 동적 메모리 할당이나 해제를 해야하므로 배열로 구현한 스택에 비해 삽입과 삭제에 시간이 더 걸립니다.  노드의 구조 정의struct Node { int data; // 데이터 필드 Node* next; // 다음 노드를 가리키는 포인터 Node(int val) { data = val; next = nullptr; }..

[원형 연결 리스트]원형 연결 리스트란 마지막 노드가 첫 번째 노드를 가리키는 리스트입니다.즉, 마지막 노드의 링크 필드가 NULL 이 아닌 첫 번째 노드의 주소를 가리키는 리스트입니다.또한 리스트의 어떤 위치에서 시작하더라도 모든 노드를 순회할 수 있습니다.  원형 연결 리스트는 리스트의 처음과 끝에 노드를 삽입하는 경우에 단순 연결 리스트보다 간단할 수 있습니다.헤드 포인터를 제일 마지막 노드를 가리키게 설정하면 마지막과 끝에 원소를 삽입하는 것이 상수 시간안에 가능합니다.   원형 연결 리스트의 앞에 원소를 삽입하는 경우    (1) 삽입할 노드의 링크 필드를 기존 원형 연결 리스트의 제일 앞 요소를 가리키게 한다.(2) 마지막 요소의 링크 필드를 새로운 노드를 가리키게 한다.  void in..

앞에서 리스트를 배열로 구현해 보았는데 이번에는 연결 리스트를 통해서 리스트를 구현해보겠습니다. [연결 리스트]연결 리스트는 각 노드 가 데이터와 다음 노드에 대한 포인터를 포함하는 구조입니다.연결 리스트는 동적 메모리 할당을 사용하므로 크기 변경이 용이하지만, 요소 접근 시간이 배열에 비해 느립니다.  연결 리스트의 구조연결 리스트의 기본 단위는 노드(Node)입니다. 각 노드는 다음과 같은 구조를 가집니다.struct Node { int data; // 데이터 Node* next; // 다음 노드를 가리키는 포인터};  공백 리스트의 생성Node* head = nullptr; // 공백 리스트는 헤드 포인터가 nullptr  노드의 생성과 연결Node* newNode = new Nod..

[리스트]리스트는 자료를 정리하는 방법 중 하나입니다.리스트에는 항목이 차례대로 저장되어 있고, 리스트의 항목은 순서 또는 위치를 가집니다. 리스트에서 가능한 연산으로는리스트에 새로운 항목을 추가한다(삽입 연산).리스트에서 항목을 삭제한다(삭제 연산).리스트에서 특정한 항목을 찾는다(탐색 연산).이 있습니다.  [리스트의 추상 자료형(ADT)]객체 : n개의 element 형으로 구성된 순서 있는 모임연산 : insert(list, pos, item) ::= pos 위치에 요소를 추가 insert_last(list, item) ::= 맨 끝에 요소를 추가 insert_first(list, item) ::= 맨 처음에 요소를 추가 delete(list, pos) ::= pos 위치에 ..

[덱 (Dequq, Double-ended Queue)]덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다. 즉, 앞과 뒤 양쪽에서 데이터를 삽입하고 삭제할 수 있습니다.하지만 여전히 중간에 삽입하거나 삭제하는 것은 불가능합니다. 덱은 양쪽 끝에서의 삽입과 삭제가 모두 필요한 경우에 유용합니다. 예를 들어, 스케줄링 문제나 슬라이딩 윈도우 알고리즘 등에서 사용됩니다.덱의 구현은 다음 예시처럼 하면 됩니다.#include #include int main() { std::deque dq; // 덱 생성 dq.push_back(1); // 덱의 뒤에 1 삽입 dq.push_back(2); // 덱의 뒤에 2 삽입 dq.push_front(0); // 덱의 앞에 0 ..

[큐 (Queue)] 큐는 FIFO(First In, First Out) 방식으로 작동하는 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다. 큐는 두 개의 포인터(front와 rear)를 사용하여 데이터의 삽입과 삭제를 관리합니다.front 는 첫 번째 요소를 가리키고 rear는 큐의 마지막 요소를 가리킵니다.큐는 순서가 중요한 작업들을 처리할 때 유용합니다. 주로 프로세스 관리, 네트워크 패킷 처리, 넓이 우선 탐색(BFS) 알고리즘 등에 사용됩니다.  [큐의 추상 자료형(ADT)]큐는 다음과 같은 연산들로 추상화할 수 있습니다.   : 큐가 비어있으면 TRUE, 아니면 FALSE 를 반환합니다.is_empty(q) ::= if(size == 0) return TRUE; e..

[동적 배열 스택]동적 배열 스택은 배열을 기반으로 한 스택 구조로, 필요에 따라 크기가 동적으로 조절되는 특징을 가지고 있습니다.C++에서는 동적 배열을 사용하여 스택을 구현할 수 있습니다.동적 배열 스택의 예제와 설명을 살펴보겠습니다.#include class DynamicArrayStack { private: int *arr; // 동적 배열 int capacity; // 배열의 최대 크기 int top; // 스택의 가장 위 인덱스 public: DynamicArrayStack(int initialCapacity = 10) { capacity = initialCapaci..