ITPE * JackerLab

개요힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드와 자식 노드 간의 우선순위 조건을 만족하는 구조이다. 최소 힙(Min Heap)은 부모 노드 ≤ 자식 노드, 최대 힙(Max Heap)은 부모 노드 ≥ 자식 노드의 조건을 만족한다. 주로 **우선순위 큐(Priority Queue)**로 활용되며, 삽입/삭제 모두 평균 O(log n)의 성능을 제공한다.1. 힙의 구조 및 특징 항목 설명 트리 구조완전 이진 트리(왼쪽부터 채움)힙 조건부모 노드 ≥ 자식 노드 (최대 힙), ≤ (최소 힙)저장 방식배열 인덱스 기반 표현 (root: index 0)사용 용도우선순위 큐, 정렬 알고리즘 (Heap Sort) 등2. 힙의 배열 표현노드 위치인덱스 관계부모 노드i왼쪽 자식2i + 1오른쪽 자식2i..

개요큐(Queue)는 먼저 들어간 데이터가 먼저 나오는 선입선출(First-In, First-Out, FIFO) 구조를 가지는 선형 자료구조이다. 데이터는 **뒤(Rear)**에서 삽입되고, **앞(Front)**에서 삭제되며, 일상적인 줄서기, 프로세스 스케줄링, 버퍼 처리 등에 널리 사용된다. 파이썬에서는 collections.deque, 리스트, 큐 모듈 등을 통해 구현할 수 있다.1. 개념 및 정의 항목 설명 구조선형적, 한쪽에서는 삽입, 반대쪽에서는 삭제 수행주요 연산enqueue(삽입), dequeue(삭제), peek(앞 요소 확인), isEmpty원리FIFO (First-In, First-Out)2. 큐 연산 동작 예시초기: []enqueue(10) → [10]enqueue(20) → [..

개요힙 정렬(Heap Sort)은 힙(Heap) 자료구조를 기반으로 하는 비교 기반 정렬 알고리즘이다. 최대 힙(Max Heap) 또는 최소 힙(Min Heap)을 이용해 최댓값(또는 최솟값)을 반복적으로 추출하고, 이를 배열의 끝에 삽입하는 방식으로 동작한다. **시간 복잡도가 항상 O(n log n)**으로 일정하며, **제자리 정렬(in-place)**이 가능하다는 장점이 있다.1. 개념 및 정의힙 정렬은 다음 두 단계로 이루어진다:배열을 힙 구조(완전 이진 트리)로 구성 (heapify)루트 노드(최댓값 또는 최솟값)를 추출한 뒤, 남은 요소로 힙 재구성 → 정렬 반복일반적으로 최대 힙을 사용해 오름차순 정렬을 수행한다.2. 동작 원리 단계 설명 1단계입력 배열을 최대 힙 구조로 변환2단계힙의 ..

개요다익스트라(Dijkstra) 알고리즘은 그래프 상에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다. 가중치가 있는 그래프에서 각 정점까지의 최소 비용을 계산하며, 우선순위 큐를 사용해 탐색 효율을 극대화한다. GPS 내비게이션, 네트워크 라우팅, 교통망 분석 등 다양한 실무 분야에서 핵심적으로 사용된다. 본 글에서는 다익스트라 알고리즘의 개념, 동작 원리, 구현 방식, 시간 복잡도, 활용 사례를 체계적으로 정리한다.1. 개념 및 정의다익스트라 알고리즘은 음수 간선이 없는 가중치 그래프에서 시작 노드로부터 모든 노드까지의 최단 경로를 구하는 탐색 알고리즘이다. 각 정점까지의 거리를 지속적으로 업데이트하며, 우선순위 큐(Priority Queue)를 사용해 가장 짧은 ..