데이터 분석 기술 블로그

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 ..

삽입 정렬"각 요소를 적절한 위치에 삽입하며 정렬하는 방식"현재 요소를 앞쪽 정렬된 부분과 비교하여 올바른 위치에 삽입거의 정렬된 데이터에서 빠르게 동작(O(n))하지만, 일반적으로 비효율적(O(n²))삽입 정렬 동작 원리첫 번째 요소는 이미 정렬된 상태로 간주두 번째 요소를 앞쪽 정렬된 부분과 비교하여 적절한 위치에 삽입세 번째 요소도 앞쪽 정렬된 부분과 비교하여 삽입이 과정을 마지막 요소까지 반복# Pseudo CodeFUNCTION InsertionSort(arr) FOR i FROM 1 TO length(arr) - 1 key = arr[i] j = i - 1 WHILE j >= 0 AND arr[j] > key DO arr[j + 1..