ITPE * JackerLab

개요그래프(Graph)는 객체(정점, Vertex)와 이들 사이의 연결 관계(간선, Edge)를 표현하는 비선형 자료구조로, 소셜 네트워크, 지도, 통신망, 관계형 데이터 등 현실 세계의 다양한 구조를 표현하는 데 사용된다. 방향성, 가중치, 순환 여부에 따라 다양한 그래프가 존재하며, 탐색, 최단 경로, 최소 신장 트리, 위상 정렬 등의 알고리즘이 활용된다.1. 그래프의 구성 요소 구성 요소 설명 정점(Vertex)데이터를 저장하는 노드 (점)간선(Edge)정점 간의 연결 관계 (선)인접 정점특정 정점과 직접 연결된 정점차수(Degree)정점과 연결된 간선의 수2. 그래프의 분류분류 기준유형설명방향성방향 그래프간선에 방향이 있음 (A → B) 무방향 그래프간선에 방향이 없음 (A — B)가중치가중치 ..

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

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

개요경로 탐색 알고리즘(Pathfinding Algorithm)은 시작 지점에서 목표 지점까지 도달하는 최적의 경로를 찾는 알고리즘이다. 이는 그래프 이론을 기반으로 하며, 다양한 조건(최단 거리, 최소 비용, 장애물 회피 등)에 따라 여러 알고리즘이 활용된다. 게임 개발, 내비게이션, 네트워크 라우팅, 인공지능 등 다양한 분야에서 필수적인 요소이며, 최적화된 탐색을 통해 성능과 정확도를 향상시킬 수 있다. 본 글에서는 주요 경로 탐색 알고리즘의 개념, 특징, 시간 복잡도 및 활용 사례를 중심으로 설명한다.1. 개념 및 정의경로 탐색은 그래프의 정점(Vertex)과 간선(Edge) 구조를 바탕으로 출발 노드에서 도착 노드까지 이동 가능한 경로를 찾는 연산이다. 경로의 최단 거리, 최소 비용, 경유지 조건..

개요비선형 자료구조는 데이터 간 관계가 일대일(one-to-one)이 아닌 계층적 또는 망형 구조로 표현되는 구조를 말한다. 대표적으로 트리(Tree)와 그래프(Graph)가 있으며, 복잡한 관계성, 네트워크 구조, 계층적 데이터 표현에 효과적이다. 선형 구조보다 연산이 복잡하지만, 현실 세계의 다양한 문제 해결에 핵심적인 역할을 한다. 본 글에서는 트리와 그래프의 개념, 유형, 주요 연산, 활용 사례를 체계적으로 설명한다.1. 개념 및 정의 자료구조 정의 특징 트리(Tree)계층적 구조로 부모-자식 관계를 갖는 노드 집합비순환, 루트에서 시작, 서브트리 구성 가능그래프(Graph)정점(Vertex)과 간선(Edge)으로 구성된 네트워크 형태순환 허용, 방향성/가중치 여부에 따라 다양화비선형 구조는 ..