데이터 분석 기술 블로그

깊이 우선 탐색 DFS"그래프 탐색 기법 중 하나로, 한 노드에서 출발하여 최대한 깊이 들어간 후 다시 돌아오는 방식"재귀(Recursion) 또는 스택(Stack)으로 구현 가능한 경로를 끝까지 탐색한 후, 다시 돌아가면서 다른 경로 탐색트리, 그래프, 미로 탐색 등에서 많이 사용됨DFS 동작 원리시작 노드에서 가능한 한 깊이 내려감더 이상 갈 곳이 없으면 되돌아옴 (Backtracking)모든 노드를 방문할 때까지 반복# Pseudo CodeFUNCTION DFS(node): 방문[node] = True # 현재 노드를 방문 처리 출력(node) # 노드 방문 FOR 모든 인접 노드 in node의 이웃 리스트: IF 방문[인접 노드] == False THEN ..

이진 탐색"정렬된 리스트에서 중간 값을 기준으로 범위를 좁혀가며 탐색하는 알고리즘"탐색할 때마다 범위를 절반으로 줄이므로 매우 빠름시간복잡도: O(log n) (탐색 범위가 계속 반으로 줄어듦)정렬된 데이터에서만 사용할 수 있음! (정렬이 안 되어 있으면 사용 불가)이진 탐색 동작 원리리스트가 정렬되어 있어야 한다.중간 값을 기준으로 찾고자 하는 값과 비교찾는 값이 중간 값보다 작으면 왼쪽으로, 크면 오른쪽으로 탐색 범위 축소이 과정을 반복하여 값을 찾음# Pseudo CodeFUNCTION BinarySearch(arr, target) left = 0 right = length(arr) - 1 WHILE left ≤ right DO mid = (left + right) / ..

선형 탐색"배열이나 리스트에서 처음부터 끝까지 하나씩 확인하면서 원하는 값을 찾는 탐색 알고리즘"순차적으로 모든 요소를 확인하는 방식시간복잡도: O(n) (최악의 경우, 모든 요소를 확인해야 함)구현이 쉽지만 데이터 크기가 커질수록 비효율적선형 탐색 동작 원리리스트(배열)의 첫 번째 요소부터 순차적으로 확인찾고자 하는 값이 나오면 탐색 종료끝까지 찾지 못하면 "없음" 반환# Pseudo CodeFUNCTION LinearSearch(arr, target) FOR i FROM 0 TO length(arr) - 1 DO IF arr[i] == target THEN RETURN i # 찾으면 인덱스 반환 END FOR RETURN -1 # 찾지 못하면 -1 ..

상황에 따라 가장 적절한 정렬 알고리즘을 선택해야 한다.퀵 정렬(Quick Sort) → 일반적으로 가장 빠른 정렬 (O(n log n), 평균적)병합 정렬(Merge Sort) → 항상 안정적인 성능 보장 (O(n log n), 최악 포함)힙 정렬(Heap Sort) → 추가 메모리 없이 정렬 가능 (O(n log n), 안정 정렬 X) 상황 추천 정렬 알고리즘 일반적인 경우 (랜덤 데이터)퀵 정렬 (Quick Sort)이미 정렬된 데이터병합 정렬 (Merge Sort)Stable Sort(안정 정렬)이 필요할 때병합 정렬 (Merge Sort)추가 메모리 없이 정렬해야 할 때힙 정렬 (Heap Sort)우선순위 정렬이 필요할 때힙 정렬 (Heap Sort)Linked List를 정렬해야 할 때병합 ..

Heapify"힙 속성을 유지하도록 트리를 정리하는 과정"최대 힙(Max Heap) → 부모 노드가 항상 자식보다 크거나 같아야 함최소 힙(Min Heap) → 부모 노드가 항상 자식보다 작거나 같아야 함Heapify 과정이 있어야 힙이 유지되고, 힙 정렬이 가능함Heapify의 역할힙이 깨졌을 때(힙 속성이 위반될 때) 이를 복구하는 과정최대 힙에서는 부모보다 큰 자식이 있으면 Swap → 힙 속성을 유지최소 힙에서는 부모보다 작은 자식이 있으면 Swap → 힙 속성을 유지완전 이진 트리(Complete Binary Tree) 형태를 유지하면서 실행Heapify의 시간복잡도 힙의 높이(트리 깊이)만큼 Swap이 필요 → O(log n)완전 이진 트리 구조이므로 높이는 log n 수준으로 유지됨따라서 H..

완전 이진 트리"모든 노드가 왼쪽부터 순서대로 채워진 이진 트리(Binary Tree)"왼쪽부터 차례대로 채워지는 특성이 있음마지막 레벨을 제외한 모든 레벨이 가득 차 있어야 함완전 이진 트리의 특징왼쪽부터 노드가 채워짐마지막 레벨을 제외한 모든 레벨이 꽉 차 있어야 함높이(Depth)가 log n 수준으로 유지됨

힙 정렬"힙(Heap) 자료구조를 이용해 정렬하는 알고리즘"완전 이진 트리(Complete Binary Tree) 기반의 힙(Heap) 구조 사용최대 힙(Max Heap) → 내림차순 정렬 / 최소 힙(Min Heap) → 오름차순 정렬시간복잡도 O(n log n) → 퀵 정렬처럼 빠르지만, 안정 정렬(Stable Sort)이 아님제자리 정렬(In-place Sort) 가능 → 추가 메모리 사용 X (O(1))2025.01.20 - [데이터 사이언스/알고리즘] - 완전 이진 트리 (Complete Binary Tree)힙 정렬의 동작 원리힙 생성(Heapify) → 주어진 배열을 힙 구조로 변환최댓값(또는 최솟값) 추출 → 루트 노드(가장 큰/작은 값)를 배열의 끝으로 이동힙 속성 복구 → 남은 힙을 다..

병합 정렬"분할 정복(Divide and Conquer) 방식으로 동작하는 정렬 알고리즘"배열을 반으로 나눈 후 각각 정렬하고, 다시 합치는 과정퀵 정렬처럼 O(n log n) 시간복잡도를 가지며, 안정적인 정렬 방식추가적인 메모리 공간(O(n))을 사용해야 하는 단점이 있음병합 정렬 동작 원리3가지 과정 (Divide → Conquer → Merge)분할(Divide)리스트를 반씩 나누어 최소한의 단위(한 개의 요소)가 될 때까지 재귀적으로 나눔정복(Conquer)분할된 리스트를 개별적으로 정렬병합(Merge)정렬된 두 개의 리스트를 하나의 정렬된 리스트로 병합 # Pseudo CodeFUNCTION MergeSort(arr) IF length(arr) 병합 정렬의 시간복잡도경우시간복잡도최선 (이..