데이터 분석 기술 블로그

트리 (비선형)노드와 간선으로 구성된 계층적 자료 구조이진트리: 각 노드가 최대 두 개의 자식을 가짐이진 탐색 트리: 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼힙: 최소값 / 최댓값을 빠르게 찾기 위한 완전 이진트리 (게임 리더보드)삽입 / 삭제 → O(log n)탐색 → BST는 O(log n) 일반 트리는 O(n)

큐 (선형)FIFO방식으로 작동하는 선입 선출 자료구조enqueue() → 요소 삽입 O(1)dequeue() → 요소 제거 O(1)front() → 맨 앞 요소 확인 O(1)원형 큐: 배열을 재사용하여 메모리 낭비 방지 (프린트 대기열)우선순위 큐: 값의 우선순위에 따라 요소가 정렬됨( 응급실 환자 대기열)덱: 앞뒤로 삽입 / 삭제 가능 (캐시 구현)

스택 (선형)LIFO방식으로 작동하는 후입 선출 자료구조push() → 요소 삽입 O(1)pop() → 요소 제거 O(1)peek() → 가장 위의 요소 확인 O(1)재귀 함수 호출 스택, 괄호 검사 등에 활용사용 예제: 웹 뒤로 가기 / 앞으로 가기

연결 리스트 (선형)각 노드가 데이터와 다음 노드를 가리키는 포인터를 포함하는 자료구조종류로 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트배열보다 메모리 낭비가 없고 크기 변경이 용이포인터 변경만 하면 되므로 삽입 / 삭제가 빠름 → O(1)특정 인덱스 접근이 느림 → O(n)사용 예제: 텍스트 편집

배열 (선형 자료 구)동일한 데이터 타입을 가진 요소들이 연속된 메모리 공간에 저장되는 자료구조고정된 크기, 빠른 랜덤 접근인덱스를 이용한 O(1) 빠른 접근 속도삽입 / 삭제가 비효율적 → 둘 다 O(n)사용 예제: 학생 성적 목록, 월별 매출 저장

1. 최단 경로최단 경로 정의간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로하나의 시작 정점에서 끝 정점까지의 최단 경로다익스트라(dijkstra) 알고리즘 : 음의 가중치를 허용하지 않습니다.벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치 허용모든 정점들에 대한 최단 경로플로이드-워샬(Floyd-Warshall) 알고리즘2. Dijkstra 알고리즘시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식입니다.시작정점(s)에서 끝정점(t)까지의 최단 경로에 정점 x가 존재합니다.이때, 최단경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단경로로 구성됩니다.탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사합니다.

1. 최소 신장 트리(MST)그래프에서 최소 비용 문제1) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리2) 두 정점 사이의 최소 비용의 경로 찾기신장 트리n 개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리최소 신장 트리(Minimum Spanning Tree)무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리2. Prim 알고리즘하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식1) 임의 정점을 하나 선택해서 시작2) 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택3) 모든 정점이 선택될 때까지 1), 2) 과정을 반복서로소인 2개의 집합(2 disjoi..

1. 서로소 집합(Disjoint-sets)서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들입니다. 다시 말해 교집합이 없습니다.집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분합니다. 이를 대표자(representative)라 합니다.상호배타 집합을 표현하는 방법연결 리스트트리상호배타 집합 연산Make-Set( x )Find-Set( x )Union( x, y )2. 상호 배타 집합 표현  - 연결리스트3. 상호 배타 집합 표현 - 트리4. 상호 배타 집합에 대한 연산