데이터 분석 기술 블로그

상황에 따라 가장 적절한 정렬 알고리즘을 선택해야 한다.퀵 정렬(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) 병합 정렬의 시간복잡도경우시간복잡도최선 (이..

힙(Heap) 메모리 개념컴퓨터의 메모리는 "스택(Stack)과 힙(Heap)" 두 영역으로 나뉜다.메모리 구조설명스택(Stack) 메모리함수 호출 시 지역 변수, 매개변수가 저장됨 (작은 용량, LIFO 구조)힙(Heap) 메모리동적 할당된 데이터가 저장됨 (크기가 크지만, 관리 필요) Heap Overflow는 힙 메모리를 과도하게 사용하여 발생스택(Stack)과 다르게 힙은 직접 해제해야 함 (메모리 관리 필요)2025.01.20 - [데이터 사이언스/알고리즘] - Stack OverflowHeap Overflow 발생 원인메모리 과다 할당 (너무 많은 객체 생성)너무 큰 리스트(배열)를 할당하면 메모리가 초과됨메모리 누수(Memory Leak)객체가 해제되지 않고 계속 남아있으면 메모리 부족 발생..

스택(Stack) 메모리 개념컴퓨터의 메모리는 "스택(Stack)과 힙(Heap)" 두 영역으로 나뉜다. 메모리 구조 설명 스택(Stack) 메모리함수 호출 시 지역 변수, 매개변수가 저장됨 (작은 용량, LIFO 구조)힙(Heap) 메모리동적 할당된 데이터가 저장됨 (크기가 크지만, 관리 필요) 스택 메모리는 한정적이며, 너무 많이 사용하면 Stack Overflow 발생2025.01.20 - [데이터 사이언스/알고리즘] - Heap OverflowStack Overflow 발생 원인무한 재귀(Recursive Function)재귀 호출이 계속 발생하면서 스택이 꽉 참너무 깊은 재귀 호출너무 깊이 호출하면 스택 메모리가 초과됨비효율적인 재귀 알고리즘 (예: 피보나치)중복된 계산이 많아 스택을 과도하게..

퀵 정렬"피벗(Pivot)을 기준으로 작은 값과 큰 값을 나누면서 정렬하는 빠른 정렬 알고리즘"분할 정복(Divide & Conquer) 방식 사용평균 시간복잡도 O(n log n) → 빠른 정렬 방법 중 하나실제로 가장 많이 사용되는 정렬 알고리즘 중 하나퀵 정렬 동작 원리피벗(Pivot) 선택리스트에서 특정한 요소를 피벗으로 선택 (보통 첫 번째, 마지막, 중간 값 중 하나) 분할(Partitioning)피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동재귀 호출(Recursion)왼쪽과 오른쪽 리스트를 다시 퀵 정렬 수행크기가 1 이하가 되면 정렬 종료 # Pseudo CodeFUNCTION QuickSort(arr) IF length(arr) pivot THEN ..