Data Structure & Algorithm

Algorithm : 어떤 문제를 해결하기 위한 절차나 방법을 순서대로 정리한 것. 문제를 해결하는 명확한 규칙이나 로직. <좋은 알고리즘의 특징> 1. 명확성 (Clarity) → 모호하지 않고 명확해야 함 2.입력 (Input) → 0개 이상의 입력을 받을 수 있어야 함 3. 출력 (Output) → 최소한 1개 이상의 출력이 있어야 함 4. 유한성 (Finiteness) → 일정한 단계 안에서 반드시 종료되어야 함 5. 효율성 (Efficiency) → 가능하면 적은 자원(CPU, 메모리)으로 빠르게 실행되어야 함

Data Structure : 데이터를 효율적으로 저장하고, 관리하며, 사용할 수 있도록 구성하는 방법. 데이터를 어떤 방식으로 저장할지, 어떻게 빠르게 접근하고 수정할지 정하는 것. 데이터 구조를 잘 선택하면 시간과 공간을 절약하면서 더 효율적으로 프로그램을 짤 수 있음. 크게 선형 구조(Linear Structure) 와 비선형 구조(Non-Linear Structure) 로 나뉨. 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등 여러 가지 데이터 구조가 있음

Linear Data Structure : 데이터가 일렬(순차적)로 저장되는 구조. 각 요소가 앞뒤로 연결되어 있으며, 데이터 접근 방식이 일정함. <대표적인 선형 구조 종류> 1. 배열(Array) → 연속된 메모리에 데이터를 저장하는 구조 2. 연결 리스트(Linked List) → 노드들이 포인터로 연결된 구조 3. 스택(Stack) → LIFO(Last In, First Out) 구조 4, 큐(Queue) → FIFO(First In, First Out) 구조 5. 덱(Deque) → 양쪽에서 삽입/삭제가 가능한 큐

Array : 같은 종류(자료형)의 데이터를 연속된 메모리 공간에 저장하는 자료구조. <배열의 특징> 1. 인덱스(Index)로 데이터에 접근 가능 → O(1) 시간에 원하는 요소 찾을 수 있음 2. 고정된 크기 → 선언 시 크기를 정해야 함(동적 배열 제외) 3. 연속된 메모리 할당 → 데이터가 한 번에 저장되므로 캐시 효율이 좋음 4. 삽입/삭제가 비효율적 → 중간에 삽입/삭제하려면 요소들을 이동해야 함(O(n)).

Time Complexity : 시간 복잡도는 알고리즘이 실행되는 데 걸리는 시간의 증가율을 수학적으로 나타낸 것. 입력 크기 n에 따른 실행 시간 증가율을 분석. 입력 크기가 커질수록 비효율적인 알고리즘은 실행 시간이 기하급수적으로 증가. 시간 복잡도는 보통 빅오 표기법을 사용하여 표현하며, O(1), O(n), O(n log n), O(n²), O(2ⁿ) 등이 있음

Big-O Notation : 빅오 표기법은 입력이 무한히 커질 때 실행 시간의 증가율을 나타내는 표기법 1. O(1) : 입력 크기에 상관없이 일정한 시간 ex) 배열에서 특정 인덱스 값 접근 2. O(log n) : 로그 증가, 입력이 2배 증가해도 실행 시간은 조금만 증가 ex) 이진 탐색(Binary Search) 3. O(n) : 입력 크기에 비례하는 실행 시간 ex) 단순 반복문(배열 순회) 4. O(n log n) : 보통 효율적인 정렬 알고리즘 ex) 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) 5. O(n²) : 중첩 반복문으로 실행 시간 급증 ex) 버블 정렬, 선택 정렬 6. O(2ⁿ) : 입력이 증가할수록 지수적으로 증가 ex) 피보나치(재귀)7. O(n!) : 가장 비효율적인 경우 ex) 순열(모든 경우 탐색)

Linked List : 연결 리스트. 노드(Node)들이 포인터를 이용해 서로 연결된 선형 데이터 구조. 배열과 달리 메모리상에서 연속되지 않아도 됨 → 동적으로 크기를 조절할 수 있음 → 메모리를 효율적으로 사용 가능. 중간 삽입/삭제가 빠름 → O(1) (배열은 O(n)). 인덱스 접근 불가 → 특정 위치의 노드를 찾으려면 처음부터 순회해야 함(O(n)). 추가적인 포인터 저장 공간 필요 → 메모리 사용량 증가. <Linked List의 종류> 1. 단일 연결 리스트(Singly Linked List) : 한 방향(다음 노드)으로만 연결됨, 각 노드가 데이터 + 다음 노드를 가리키는 포인터로 구성됨 2. 이중 연결 리스트(Doubly Linked List) : 각 노드가 이전(prev)과 다음(next) 포인터를 가짐 → 양방향 이동 가능 3. 원형 연결 리스트(Circular Linked List) : 마지막 노드가 다시 첫 번째 노드를 가리킴 → 리스트의 끝이 없음, 반복적인 작업(예: 음악 재생 목록, 캐시 관리)에 유용, 끝이 없어서 주의해야 함

Pointer : 메모리 주소를 저장하는 변수. 즉, 어떤 변수의 주소를 가리키는 변수. 일반 변수는 데이터를 저장하지만, 포인터 변수는 "메모리 주소"를 저장함. *(애스터리스크)를 사용하여 선언함. &(앰퍼샌드)를 사용하여 변수의 주소를 가져올 수 있음. <포인터의 개념 정리> 1. & : 변수의 메모리 주소를 반환 2. * : 포인터가 가리키는 값을 가져옴 3. int* p; : p는 int 타입 변수의 주소를 저장하는 포인터. <포인터의 활용> 1. 포인터를 이용한 값 변경 : 포인터를 이용해 변수 값을 직접 변경할 수 있음 2. 동적 메모리 할당 (new, delete) : new로 동적 메모리를 할당하고 delete로 해제해야 함 3. 배열과 포인터 : 배열의 이름은 첫 번째 요소의 주소를 가리키므로 포인터처럼 동작함

Dynamic Memory : 동적 메모리는 프로그램 실행 중(runtime)에 메모리를 할당하는 방식. 즉, 컴파일 시 크기가 정해지는 정적 메모리(Static Memory) 와 달리, 필요할 때 메모리를 할당하고, 사용이 끝나면 해제할 수 있음. new로 할당, delete로 해제 (배열은 new[], delete[]). 힙(Heap) 메모리를 사용하며, 해제하지 않으면 메모리 누수가 발생할 수 있음. 스마트 포인터를 사용하면 자동으로 메모리 관리 가능

Smart Pointer : 스마트 포인터는 C++에서 동적 메모리를 자동으로 관리해 주는 포인터. 즉, new와 delete를 직접 사용하지 않고도 자동으로 메모리를 해제할 수 있음. <왜 스마트 포인터를 사용할까?> 1. 메모리 누수 방지 → delete를 깜빡해도 자동으로 해제됨 2. 예외 발생 시에도 안전 → 예외가 발생해도 메모리 해제 보장됨 3. 직접 delete를 호출할 필요 없음 → 코드가 깔끔해짐. <C++ 스마트 포인터 종류 (memory 헤더 필요)> 1. unique_ptr : 단독 소유, 다른 포인터에 할당 불가 2. shared_ptr : 여러 개의 포인터가 같은 객체를 공유 3. weak_ptr : shared_ptr와 함께 사용, 참조만 가능

Memory Leak : 메모리 누수란 할당한 동적 메모리를 해제하지 않아서 사용되지 않는 메모리가 계속 남아있는 현상. 즉, new로 할당한 메모리를 delete하지 않으면 메모리가 반환되지 않아 점점 쌓이게 됨. 반드시 delete 또는 delete[]로 해제해야 함. <메모리 누수가 발생하는 이유> 1. 할당한 메모리를 delete 또는 free()로 해제하지 않음 2. 포인터 변수를 잃어버림 → 더 이상 접근할 방법이 없음 3. 반복문이나 함수 호출에서 계속 동적 메모리를 할당하고 해제하지 않음

Node : 노드는 데이터와 다른 노드와의 연결 정보를 포함하는 기본 단위. 특히 연결 리스트(Linked List), 트리(Tree), 그래프(Graph) 같은 자료구조에서 핵심 요소로 사용됨. 노드의 연결 방식에 따라 다양한 자료구조가 만들어짐. <노드의 기본 구조> 1. 데이터(Data) → 저장할 값 2. 포인터(링크, 주소) → 다음 노드(또는 여러 노드)를 가리키는 주소

Stack : 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조. 즉, 나중에 들어온 데이터가 먼저 나감. <Stack의 주요 연산(시간 복잡도는 모두 O(1))> 1. push(x) : 스택에 요소 x를 추가 2. pop() : 스택의 최상단 요소 제거 3. top() : 스택의 최상단 요소 확인 4. empty() : 스택이 비어 있는지 확인 <Stack의 활용 예시> 1. 재귀 함수 호출 (함수 콜 스택). 2. 괄호 검사 ((), {}가 올바르게 열리고 닫히는지 체크) 3. 후위 표기법 계산 (Reverse Polish Notation, RPN) 4. DFS(깊이 우선 탐색, Depth-First Search) 알고리즘

Queue : 큐는 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조. 즉, 먼저 들어온 데이터가 먼저 나감. <큐의 주요 연산(시간 복잡도는 모두 O(1))> 1. push(x) / enqueue(x) 2. pop() / dequeue() : 큐의 앞에서 요소 제거 3. front() 큐의 맨 앞 요소 확인 4. empty() : 큐가 비어 있는지 확인. <큐의 활용 예시> 1. BFS(너비 우선 탐색, Breadth-First Search) 2. 운영체제의 프로세스 스케줄링 3. 네트워크 패킷 처리 4. 프린터 작업 대기열

Deque, Double-Ended Queue : 덱은 양쪽(앞과 뒤)에서 삽입/삭제가 모두 가능한 큐. 즉, 스택(Stack)과 큐(Queue)의 특성을 모두 가짐. <덱의 주요 연산(시간 복잡도는 모두 O(1))> 1. push_front(x) : 앞쪽에 요소 추가 2. push_back(x) : 뒤쪽에 요소 추가 3. pop_front() : 앞쪽 요소 제거 4. pop_back() : 뒤쪽 요소 제거 5. front() : 앞쪽 요소 확인 6. back() : 뒤쪽 요소 확인. <덱(Deque)의 활용 예시> 1. 슬라이딩 윈도우 (Sliding Window) 2. 스케줄링 및 캐시 관리 (LRU Cache) 3. BFS(너비 우선 탐색)에서 최적화된 큐 4. 문자열 회문 검사 (양쪽에서 비교 가능)

Non-Linear Data Structure : 비선형 구조. 데이터가 일렬로 정렬되지 않고, 여러 개의 연결 관계를 가질 수 있는 자료구조. 즉, 각 데이터가 여러 개의 노드와 연결될 수 있는 구조를 의미. <주요 비선형 자료구조> 1. 트리(Tree) : 계층적(부모-자식) 구조, ex) 이진 트리, 이진 탐색 트리(BST), 힙 2. 그래프(Graph) : 노드(정점)와 간선(연결)으로 이루어진 구조, ex) 소셜 네트워크, 길 찾기 알고리즘 3. 힙(Heap) : 최댓값 또는 최솟값을 빠르게 찾는 구조, ex) 우선순위 큐, 힙 정렬 4. 트라이(Trie) : 문자열 검색을 빠르게 수행하는 자료구조, ex) 자동완성 기능, 사전 검색

Tree : 트리는 계층적(Hierarchical) 구조를 가지는 비선형 자료구조. 즉, 부모-자식 관계를 가지며, 한 노드에서 여러 개의 노드로 뻗어나가는 형태임. 그래프(Graph)의 한 종류로, "사이클이 없는 연결 그래프(Acyclic Connected Graph)". <트리의 특징> 1. 하나의 루트(Root) 노드에서 시작 2. 사이클이 없음 (순환 구조 X) 3. 두 노드를 연결하는 유일한 경로가 존재. <트리의 주요 개념> 1. 루트 노드 (Root Node) : 트리의 시작점 2. 부모 노드 (Parent Node) : 다른 노드를 포함하는 노드 3. 자식 노드 (Child Node) : 부모 노드 아래 연결된 노드 4. 형제 노드 (Sibling Node) : 같은 부모를 가진 노드들 5. 리프 노드 (Leaf Node) : 자식이 없는 노드 6. 깊이 (Depth) : 루트에서 특정 노드까지의 거리 7. 높이 (Height) :특정 노드에서 리프까지의 최대 거리. <트리의 종류> 1. 이진 트리 (Binary Tree) : 각 노드가 최대 2개의 자식을 가짐 2. 이진 탐색 트리 (BST, Binary Search Tree) : 왼쪽은 작은 값, 오른쪽은 큰 값 저장 3. 균형 이진 트리 (Balanced Binary Tree) : 트리의 높이가 최소화된 형태 (AVL 트리, 레드-블랙 트리) 4. 완전 이진 트리 (Complete Binary Tree) : 왼쪽부터 노드가 채워짐 5. 트라이(Trie) : 문자열 탐색에 최적화된 트리. <트리(Tree)의 활용 예시> 1. 이진 탐색 트리(BST) → 정렬된 데이터 저장 및 탐색 2. 파일 시스템 → 폴더 구조 (부모-자식 관계) 3. 트라이(Trie) → 자동완성, 사전 검색 4. 힙(Heap) → 우선순위 큐, 힙 정렬 5. HTML DOM 구조 → 웹 페이지 요소 계층 구조

Binary Tree : 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 자료구조. 즉, 부모 노드는 왼쪽 자식과 오른쪽 자식 최대 2개의 자식만 가질 수 있음. <이진 트리의 특징> 1. 각 노드의 자식 노드는 최대 2개 2. 계층적(Hierarchical) 구조를 가짐 3. 재귀적으로 정의 가능 (트리는 자기 자신을 포함하는 구조) 4. 순회(Traversal) 방식이 중요 → (전위, 중위, 후위 순회). <이진 트리 종류> 1. 완전 이진 트리 (Complete Binary Tree) 2. 포화 이진 트리 (Full Binary Tree) 3. 균형 이진 트리 (Balanced Binary Tree) 4. 이진 탐색 트리 (BST, Binary Search Tree)

Traversal : 순회는 트리(Tree)나 그래프(Graph) 같은 자료구조의 모든 노드를 방문하는 과정을 의미

Preorder Traversal : 전위 순회. 루트 → 왼쪽 → 오른쪽 순서로 방문. 루트를 먼저 방문하므로 복사, 계층 구조 출력 등에 유용

Inorder Traversal : 1. 왼쪽 → 루트 → 오른쪽 순서로 방문 2. 이진 탐색 트리(BST)에서 중위 순회를 하면 정렬된 결과를 얻을 수 있음

Postorder Traversal : 후위 순회. 왼쪽 → 오른쪽 → 루트 순서로 방문. 트리 구조 삭제, 후위 표기법 계산 등에 유용

Level Order : 레벨 순회. 위에서 아래로, 왼쪽부터 오른쪽으로 탐색. 너비 우선 탐색(BFS) 방식으로 진행. 큐(Queue) 자료구조를 이용하여 구현 가능

BST(Binary Search Tree) : 이진 탐색 트리. 이진 트리(Binary Tree)의 한 종류로, 탐색을 효율적으로 수행할 수 있도록 정렬된 구조를 가지는 트리임. 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼. 중위 순회(Inorder Traversal)를 하면 항상 오름차순으로 정렬됨. 탐색, 삽입, 삭제 연산을 평균적으로 O(log n) 시간에 수행 가능. <이진 탐색 트리의 주요 연산> 1. 탐색(Search) : 원하는 값 찾기, 탐색 연산은 BST의 규칙(왼쪽 < 부모 < 오른쪽)을 활용 2. 삽입(Insert) : 새로운 값 추가, 새로운 값을 삽입할 때 BST 규칙(왼쪽 < 부모 < 오른쪽)을 유지해야 함 3.삭제(Delete) : 특정 값 제거, 1) 자식이 없는 노드 삭제 (리프 노드 삭제) → 그냥 제거 2) 자식이 하나인 노드 삭제 → 부모와 자식을 직접 연결 3) 자식이 둘인 노드 삭제 → 중위 후속자(Inorder Successor, 오른쪽 서브트리의 최솟값)와 교체 후 삭제

Skewed Tree : 편향 트리는 한쪽 방향으로만 노드가 치우쳐 있는 이진 트리를 의미. 즉, 균형이 맞지 않아서 탐색, 삽입, 삭제 연산이 비효율적으로 수행되는 트리. 왼쪽 편향 트리(Left Skewed Tree) → 모든 노드가 왼쪽 자식만 가짐. 오른쪽 편향 트리(Right Skewed Tree) → 모든 노드가 오른쪽 자식만 가짐. <편향 트리의 문제점> 1. 탐색(Search), 삽입(Insert), 삭제(Delete) 연산이 최악의 경우 O(n)까지 증가 2. BST(Binary Search Tree)의 장점인 O(log n) 탐색 속도를 유지하지 못함 3. 거의 연결 리스트(Linked List)와 비슷한 성능이 됨 <해결책> AVL 트리, 레드-블랙 트리 같은 균형 BST 사용

Search : 탐색은 주어진 데이터 구조에서 특정 값을 찾는 과정을 의미. 즉, 배열, 리스트, 트리, 그래프 등에서 원하는 값을 효율적으로 찾는 알고리즘을 사용함 1. 선형 탐색(Linear Search) : 정렬되지 않은 데이터에서 사용할 수 있음, 순차적으로 하나씩 확인하기 때문에 O(n) 시간이 걸림 2. 이진 탐색(Binary Search) : 정렬된 데이터에서 절반씩 줄여가며 탐색 (O(log n)), 정렬된 배열에서만 사용 가능 3. 트리 탐색 → 이진 탐색 트리(BST)나 균형 트리에서 탐색 (O(log n)), 이진 탐색 트리(BST)에서 탐색은 왼쪽/오른쪽 방향으로 진행 4. 해시 탐색(Hash Search) : 해시 테이블을 이용한 빠른 탐색 (평균 O(1), 최악 O(n))

Sorting : 정렬은 데이터를 특정 순서(오름차순 또는 내림차순)로 정리하는 과정. 즉, 숫자, 문자열, 객체 등을 비교하여 정해진 순서대로 배열하는 것. 오름차순(Ascending Order), 내림차순(Descending Order)

Bubble Sort : 버블 정렬. 인접한 두 요소를 비교하여 큰 값을 오른쪽으로 이동. 느리지만 구현이 쉬움 (O(n²))

Selection Sort : 선택 정렬. 가장 작은 값을 찾아서 왼쪽부터 차례로 배치 O(n²). 실제로 잘 안 씀

Insertion Sort : 삽입 정렬. 이미 정렬된 부분에 새 요소를 적절한 위치에 삽입. 거의 정렬된 경우 O(n)까지 최적화 가능

Merge Sort : 병합 정렬. 분할 정복(Divide & Conquer) 방식 사용. 안정 정렬(Stable Sort), O(n log n)

Quick Sort : 퀵 정렬. 기준점(Pivot)을 설정하고, 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬. 빠르지만 최악의 경우 O(n²) (이미 정렬된 데이터)

Heap Sort : 힙 정렬. 힙(Heap) 자료구조를 이용한 정렬, O(n log n). 최대 힙(Max Heap)에서 루트(최댓값)를 하나씩 꺼내 정렬

Radix Sort : 기수 정렬. 비교 연산 없이 자릿수별로 정렬. 숫자 정렬에 특화된 알고리즘

Subtree : 트리에서 특정 노드를 루트로 하는 부분 트리를 의미함. 즉, 트리의 일부를 떼어내도 여전히 트리 구조를 유지하는 부분 집합. <서브 트리의 활용> 1. 트리에서 특정 패턴 찾기 (서브 트리 매칭 문제) 2. 이진 탐색 트리(BST)에서 특정 범위의 값 찾기 3. 트라이(Trie)에서 특정 문자열 패턴 찾기 4. 트리 기반 데이터 구조에서 특정 구조 확인

Balanced Binary Tree : 트리의 높이를 최소한으로 유지하여 탐색, 삽입, 삭제 연산을 O(log n) 시간에 수행할 수 있도록 설계된 이진 트리. 모든 서브 트리의 높이 차이가 일정 범위 이내여야 함. 탐색, 삽입, 삭제 연산이 O(log n) 시간에 가능. 대표적인 균형 이진 트리 : AVL 트리, 레드-블랙 트리 <균형 조건> 1. 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 일정 범위 이내여야 함 2. 일반적으로 높이 차이(Height Difference, Balance Factor)가 -1, 0, 1 사이여야 함.

AVL Tree : AVL 트리는 이진 탐색 트리(BST)에서 각 노드의 왼쪽/오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지하는 균형 트리. 각 노드의 균형 인수(Balance Factor) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이. 균형 인수 값이 -1, 0, 1을 초과하면 회전(Rotation) 연산을 수행하여 균형 유지

Red-Black Tree : 균형을 유지하는 이진 탐색 트리(BST)의 한 종류로, 삽입/삭제 후에도 균형을 유지하기 위해 노드에 색상(빨강/검정)을 추가한 트리. 이 규칙을 통해 최악의 경우에도 O(log n) 탐색 성능을 보장. <레드-블랙 트리의 5가지 속성> 1. 모든 노드는 빨강 또는 검정이다 2. 루트(Root) 노드는 항상 검정이다 3. 모든 리프 노드(NULL)는 검정이다 4. 빨강 노드의 자식은 항상 검정이어야 한다. 즉, 빨강-빨강(Red-Red) 연속 불가능 5. 어떤 노드에서 리프(NULL)까지 가는 모든 경로의 검정 노드 개수는 동일해야 한다. 즉, 검정 높이(Black Height)가 일정해야 함

Complete Binary Tree : 완전 이진 트리는 왼쪽부터 차례대로 노드를 채운 이진 트리. 모든 레벨이 꽉 차 있어야 하며, 마지막 레벨만 노드가 부족할 수 있음. 마지막 레벨의 노드는 항상 "왼쪽부터 오른쪽 순서"로 채워져야 함. 힙(Heap)과 같은 자료구조에서 사용됨. <완전 이진 트리의 특징> 1. 노드 개수가 n개일 때, 루트(Root)부터 인덱스를 부여하면 배열로 쉽게 표현 가능 2. 완전 이진 트리의 높이 h는 O(log n) (n개의 노드를 가질 때) 3. 힙(Heap)에서 사용됨 → 부모/자식 관계를 인덱스로 계산 가능 4. 배열을 사용해 쉽게 구현할 수 있음.

Heap : 힙은 최댓값 또는 최솟값을 빠르게 찾을 수 있는 완전 이진 트리 기반의 자료구조. 항상 완전 이진 트리 형태를 유지해야 함. 부모 노드와 자식 노드 간의 특정한 우선순위(Heap Property)를 가짐. 삽입/삭제 연산이 O(log n)으로 빠름. 우선순위 큐(Priority Queue) 구현에 사용됨. <힙의 종류> 1. 최대 힙 (Max Heap) : 부모 노드 ≥ 자식 노드 (루트가 최댓값) 2. 최소 힙 (Min Heap) : 부모 노드 ≤ 자식 노드 (루트가 최솟값). (최댓값/최솟값 접근 시간 복잡도 O(1)). <힙의 핵심 연산> 1. 삽입(Insert) : 새로운 노드를 마지막에 추가한 후, 부모와 비교하며 위로 올림(Heapify-Up), 새로운 노드를 추가하고 재정렬 O(log n) 2. 삭제(Delete) : 루트(최댓값/최솟값) 삭제 후 재정렬 O(log n), 항상 루트(최댓값/최솟값)를 삭제한 후, 마지막 노드를 루트로 옮기고 자식과 비교하며 아래로 내림(Heapify-Down) 3. 탐색(Search) : 루트(최댓값/최솟값) 확인 O(1). <힙의 활용> 1. 우선순위 큐 (Priority Queue) 구현 2. 힙 정렬(Heap Sort) 알고리즘 3. 다익스트라 최단 경로 알고리즘 (Dijkstra’s Algorithm) 4. 최소 신장 트리(MST) - 프림 알고리즘(Prim’s Algorithm)

Graph : 그래프는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 비선형 자료구조. 즉, 여러 개의 노드가 서로 연결된 구조를 가지며, 관계를 표현하는 데 유용함. 정점(Vertex, 노드) → 데이터를 담고 있는 개체 (예: 도시, 사람). 간선(Edge, 연결선) → 정점 간의 관계를 나타내는 선 (예: 도로, 친구 관계). <그래프의 종류> 1. 방향 그래프(Directed Graph, 유향 그래프) : 간선에 방향이 있음 (A → B는 가능하지만 B → A는 불가능) 2. 무방향 그래프(Undirected Graph, 무향 그래프) : 간선에 방향이 없음 (A → B와 B → A가 동일함) 3. 가중치 그래프(Weighted Graph) : 각 간선이 특정한 가중치(비용)를 가짐. <그래프의 표현 방법> 1. 인접 행렬 (Adjacency Matrix) : 2차원 배열을 이용하여 그래프를 저장, 노드 개수가 많으면 메모리 낭비(O(V²)), 탐색 속도는 빠름 (O(1)) 2. 인접 리스트 (Adjacency List) : 각 정점이 연결된 노드 목록을 저장, 메모리 효율적(O(V + E)), 탐색 속도는 느릴 수 있음, (O(V)). <그래프 활용 예시> 1. 소셜 네트워크 (페이스북 친구 추천, 링크드인 연결) 2. 네트워크 최단 경로 (다익스트라 알고리즘, 플로이드 워셜 알고리즘) 3. 지도 경로 탐색 (구글 지도, 내비게이션) 4. 컴퓨터 네트워크 (인터넷 라우팅, DNS 탐색)

Trie, Prefix Tree : 트라이는 문자열 탐색과 자동 완성 기능을 빠르게 수행할 수 있도록 설계된 트리 자료구조. 문자의 계층적 구조를 이용하여 문자열을 저장함. 공통된 접두사(Prefix)를 효율적으로 저장하여 중복을 줄임. 삽입, 삭제, 탐색 연산을 O(M) 시간에 수행 가능 (M은 문자열 길이). <트라이 구조> 트라이는 루트 노드(Root Node)에서 시작하며, 각 간선(Edge)은 한 개의 문자(Character)를 나타냄, 단어의 끝을 나타내는 isEndOfWord 플래그가 있음. <트라이의 주요 연산> 1. 삽입 : 문자열을 트라이에 추가. 새로운 문자열을 추가할 때, 각 문자를 따라가며 노드를 생성함, 이미 존재하는 접두사(Prefix)가 있으면 해당 경로를 그대로 사용. 2. 탐색 : 특정 문자열이 존재하는지 확인. 문자열이 존재하는지 확인하려면 루트에서 시작해 한 글자씩 따라감. 마지막 노드가 isEndOfWord = true이면 해당 문자열이 존재하는 것임. 3. 삭제 : 특정 문자열을 트라이에서 제거. 문자열을 삭제할 때, 다른 단어와 공유되지 않는 노드는 제거해야 함. <트라이(Trie)의 활용> 1. 자동 완성(Auto-complete) → 검색 엔진, 입력 보조 기능 2. 사전(Dictionary) 구현 → 단어 목록 저장 및 검색 3. 접두사 검색(Prefix Search) → 검색어 추천 4. DNA 서열 분석(Bioinformatics) → 유전자 서열 저장 및 검색 5. IP 주소 검색 → 라우팅 테이블 최적화

Hash Table : 키(Key)와 값(Value)을 저장하는 자료구조로, 해시 함수를 이용하여 데이터를 빠르게 검색할 수 있음. 빠른 데이터 조회가 필요할 때 사용됨 (캐시, 검색, 데이터베이스 등). 해시테이블은 멀티스레드 지원. 해시맵은 빠르지만 스레드 안전하지 않음. <해시 테이블 동작 원리> 1. 키를 해시 함수를 통해 인덱스로 변환 2. 배열(버킷, Bucket)에 해당 위치(Index)에 데이터를 저장 3. 키를 사용해 O(1) 시간에 데이터를 찾을 수 있음. <충돌(Collision) 해결 방법> 해시 함수는 같은 인덱스를 여러 키가 가질 수 있음 → 충돌 발생. 해결방법 1. 체이닝(Chaining) : 같은 인덱스에 여러 값을 저장할 경우, 연결 리스트로 관리. 해결방법 2. 개방 주소법(Open Addressing) : 충돌이 발생하면 다른 빈 공간을 찾아 저장. 1) 선형 탐색(Linear Probing) 2) 이차 탐색(Quadratic Probing)

Bucket : 해시 테이블(Hash Table)에서 데이터를 저장하는 공간(슬롯, Slot) 단위. 즉, 해시 함수가 계산한 인덱스에 해당하는 저장 공간을 버킷 이라고 부름. 버킷 개수 = 해시 테이블 크기 (배열의 크기). 충돌 발생 시, 같은 버킷에 여러 개의 데이터가 저장될 수 있음. 버킷 크기가 크면 충돌이 적고 성능이 향상됨

Pseudocode : 슈도 코드. 프로그래밍 언어의 문법을 따르지 않고, 알고리즘을 쉽게 표현하는 방법. 즉, 사람이 이해하기 쉬운 형태로 작성한 알고리즘의 설계도. 코드를 작성하기 전에 논리를 정리하는 데 유용함

Postfix Notation, RPN : 후위 표기법. 연산자를 피연산자 뒤에 배치하는 수식 표기법. 괄호 없이 연산자의 우선순위를 명확하게 표현 가능. 스택(Stack)을 이용하여 쉽게 계산 가능. 컴퓨터, 계산기에서 연산을 수행할 때 많이 사용됨. 현대 컴퓨터에서는 전위 표기법보다 더 자주 사용됨. <중위 → 후위 표기법 변환 방법> 1. 피연산자(숫자)는 그대로 출력 2. 연산자는 스택에 저장, 우선순위에 따라 처리 3. 괄호는 특별 규칙 적용. <연산자 우선순위> 1. 괄호 () 2. 곱셈, 나눗셈 */ 3. 덧셈, 뺄셈 +- <예제 변환 과정> 중위 표기법: A + B * C. 후위 표기법: A B C * +

Inorder Successor : 중위 후속자. 이진 탐색 트리(BST)에서 현재 노드보다 "중위 순회(Inorder Traversal)"에서 바로 다음에 오는 노드를 의미. BST에서 특정 노드보다 "큰 값" 중 가장 작은 값을 가짐. 다음 방문할 노드를 찾을 때 사용됨. <중위 후속자를 찾는 방법> 1. 오른쪽 서브트리가 있으면 → 가장 왼쪽 노드가 후속자 2. 오른쪽 서브트리가 없으면 → 부모 노드 중 처음으로 큰 값이 후속자

Inorder Predecessor : 중위 선행자. 이진 탐색 트리(BST)에서 현재 노드보다 "중위 순회(Inorder Traversal)"에서 바로 이전에 오는 노드를 의미. BST에서 특정 노드보다 "작은 값" 중 가장 큰 값을 가짐. <중위 선행자를 찾는 방법> 1. 왼쪽 서브트리가 있으면 → 가장 오른쪽 노드가 선행자 2. 왼쪽 서브트리가 없으면 → 부모 노드 중 처음으로 작은 값이 선행자