metamong-data 님의 블로그

개요깊이 우선 탐색(Depth-First Search, DFS)은 그래프나 트리 자료구조에서 루트 노드(또는 임의의 시작 노드)에서 시작하여 한 분기(branch)를 최대한 깊게 탐색한 후, 더 이상 깊이 갈 수 없을 때 다른 분기로 이동하여 탐색을 계속하는 방법입니다. 즉, 가능한 한 깊이 내려간 후, 더 이상 내려갈 곳이 없으면 이전 노드로 돌아와 다른 경로를 탐색하는 방식입니다.동작 원리시작 노드를 방문하고, 해당 노드를 방문 처리합니다.현재 노드에 인접한 노드들 중 방문하지 않은 노드가 있다면, 그 노드를 선택하여 재귀적으로 DFS를 수행합니다.방문하지 않은 인접 노드가 없다면, 이전 노드로 돌아갑니다.모든 노드를 방문할 때까지 위 과정을 반복합니다.이러한 과정을 통해 DFS는 한 경로를 따라 최..

개요너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리에서 루트 노드(혹은 다른 임의의 노드)에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 방식입니다.동작 원리시작 노드를 방문하고, 해당 노드를 큐(Queue)에 삽입합니다.큐에서 노드를 꺼내어(dequeue) 해당 노드에 인접한 방문하지 않은 모든 노드를 큐에 삽입(enqueue)하고, 방문 처리를 합니다.2번 과정을 큐가 빌(empty) 때까지 반복합니다.이러한 과정을 통해 BFS는 시작 노드로부터 가까운 노드부터 차례대로 탐색하게 됩니다.특징최단 경로 보장: BFS는 가중치가 없는 그래프에서 두 노드 사이의 최단 경로를 보장합니다.구현의 복잡성: BFS..

📌 개요해시(Hash)는 키(Key)를 해시 함수(Hash Function)로 변환하여 빠르게 값을 찾는 자료구조입니다.특히 문자열 해싱(String Hashing) 은 문자열을 정수 값으로 변환하여 검색, 비교 연산을 효율적으로 수행하는 방법입니다.✅ 해시의 주요 특징검색, 삽입, 삭제 연산이 평균 O(1)해시 충돌(Collision)을 해결하는 기법 필요문자열 비교 연산을 O(N) → O(1)로 최적화 가능 (문자열 해싱)📌 해시 테이블 (Hash Table)1. 해시 테이블 개념해시 테이블(Hash Table)은 키(Key) → 값(Value) 형태로 데이터를 저장하며, 해시 함수(Hash Function) 를 이용해 데이터를 저장할 위치를 결정합니다.2. Python 딕셔너리(Dictionar..

📌 개요트리(Tree)는 계층적 구조를 표현하는 비선형 자료구조입니다.각 요소(노드, Node)는 부모와 자식 간의 관계를 가지며, 루트(Root)에서 시작하여 가지를 뻗어나가는 형태를 가집니다.✅ 트리의 특징:순환(Cycle)이 없는 그래프계층적 구조 (부모-자식 관계)DFS, BFS 등 다양한 탐색 방법 존재이진 탐색 트리(BST), 힙(Heap), AVL 트리 등 다양한 응용 가능📌 트리의 기본 개념1. 트리의 기본 용어용어설명노드(Node)트리의 각 요소루트 노드(Root Node)트리의 최상위 노드부모 노드(Parent Node)특정 노드의 상위 노드자식 노드(Child Node)특정 노드의 하위 노드형제 노드(Sibling Node)같은 부모를 가진 노드들잎 노드(Leaf Node)자식이 ..

📌 개요큐(Queue)는 FIFO(First In, First Out) 구조를 따르는 선형 자료구조입니다.즉, 먼저 들어온 요소가 먼저 처리됩니다.큐의 확장 개념으로 우선순위 큐(Priority Queue) 가 있으며, 이는 요소의 우선순위를 고려하여 처리 순서를 결정하는 큐입니다.✅ 큐와 우선순위 큐의 차이점자료구조삽입(Enqueue)삭제(Dequeue)정렬 기준일반 큐 (Queue)O(1)O(1)선입선출 (FIFO)우선순위 큐 (Priority Queue)O(log N)O(log N)우선순위 높은 요소 먼저📌 큐 (Queue)1. 큐의 특징FIFO(First In, First Out) 방식삽입(Enqueue)과 삭제(Dequeue) 연산 제공스택(Stack)과 반대 개념BFS(너비 우선 탐색), ..

개요스택(Stack)은 후입선출 (LIFO, Last-In First-Out) 구조를 따르는 자료구조입니다.즉, 마지막에 추가된 요소가 가장 먼저 제거되는 방식으로 동작합니다.스택은 메모리 관리, 재귀 함수 실행, 괄호 검사, 문자열 역순 출력, 백트래킹(Backtracking) 등 다양한 알고리즘에서 활용됩니다.파이썬에서는 list 또는 collections.deque를 사용하여 스택을 구현할 수 있습니다.스택의 특징LIFO(Last-In, First-Out)가장 나중에 삽입된 데이터가 가장 먼저 제거됨.기본 연산Push: 스택에 데이터를 삽입 ($O(1)$)Pop: 스택에서 최상위(top) 데이터를 제거 및 반환 ($O(1)$)Peek(Top): 스택의 최상위 데이터를 조회 (삭제 X) ($O(1)$..

개요배열(Array)은 같은 자료형을 가진 요소들을 연속적인 메모리 공간에 저장하는 자료구조입니다. 배열을 사용하면 여러 개의 데이터를 하나의 변수처럼 다룰 수 있으며, 인덱스를 이용하여 특정 요소에 접근할 수 있습니다.배열은 대부분의 프로그래밍 언어에서 기본적으로 제공하는 자료구조이며, 고정된 크기를 가지는 경우가 일반적입니다. 그러나 일부 언어에서는 동적으로 크기를 조정할 수 있는 배열도 제공합니다.배열의 특징연속적인 메모리 공간 사용배열의 요소들은 메모리에 연속적으로 배치되므로, 인덱스를 이용한 접근 속도가 빠릅니다.임의의 위치에 있는 원소를 $O(1)$ (상수 시간)에 접근할 수 있습니다.고정된 크기일반적인 배열은 선언 시 크기가 결정되며, 이후 변경할 수 없습니다.크기를 변경하려면 새로운 배열을..

개요문자열(String)은 문자(character)들의 연속된 시퀀스를 나타내는 자료구조로, 텍스트 데이터를 저장하고 처리하는 데 사용됩니다. 대부분의 프로그래밍 언어에서 문자열은 문자 배열(Array of characters)의 형태로 구현됩니다.문자열은 불변(immutable)한 경우가 많아, 한 번 생성되면 내용을 변경할 수 없는 특징을 가지며, 다양한 문자열 처리 알고리즘이 존재합니다.문자열의 특징연속된 메모리 공간 사용 배열과 마찬가지로, 문자열도 연속적인 메모리 공간에 저장됩니다.따라서 특정 인덱스에 있는 문자에 $O(1)$의 시간 복잡도로 접근할 수 있습니다.불변성 (Immutable) 대부분의 언어에서 문자열은 불변(Immutable)합니다. 즉, 한 번 생성된 문자열은 변경할 수 없습..

📌 개요누적합(Prefix Sum) 배열은 배열의 특정 구간 합을 빠르게 계산하기 위한 자료구조입니다.일반적으로 배열에서 여러 개의 구간 합을 반복적으로 구해야 하는 문제에서 유용합니다.✅ 누적합 배열을 사용하는 이유:단순한 구간 합 계산은 O(N) → 여러 번 반복하면 비효율적누적합 배열을 이용하면 O(1)로 구간 합을 계산할 수 있음미리 계산한 값을 활용하여 빠른 질의(Query) 처리 가능📌 누적합 배열 개념배열 A의 누적합 배열 S 를 다음과 같이 정의합니다.S[i]=A[0]+A[1]+...+A[i]S[i] = A[0] + A[1] + ... + A[i]즉, S[i]는 배열 A의 0번 인덱스부터 i번 인덱스까지의 합을 의미합니다.✅ 특정 구간 [L, R] 의 합을 구하는 공식sum(L,R)=S..

📌 개요그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.그래프는 정점 간의 연결 관계를 표현하는 데 사용되며, 다양한 실생활 문제(지도 네비게이션, SNS 관계망, 네트워크 등)에서 활용됩니다.✅ 그래프의 특징정점(Vertex, Node)과 간선(Edge)으로 구성방향성(Directed, Undirected), 가중치(Weighted, Unweighted) 여부에 따라 종류가 나뉨DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 등의 탐색 방법이 존재최단 경로 탐색, 최소 신장 트리(MST) 등의 알고리즘에서 활용됨📌 그래프의 용어용어설명정점(Vertex, 노드)그래프의 구성 요소간선(Edge)정점 간의 연결인접(Adjacent)두 정점이 직접 연결된 상태차수(..