ITPE * JackerLab

개요프림 알고리즘(Prim Algorithm)은 그래프에서 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는 대표적인 그리디 알고리즘으로, 하나의 정점에서 시작하여 인접한 최소 비용 간선을 반복적으로 선택하며 트리를 확장하는 방식이다. 네트워크 설계, 회로 최적화 등 다양한 분야에서 활용된다.1. 개념 및 정의프림 알고리즘은 하나의 시작 정점을 선택한 후, 현재 트리에 포함된 정점들과 인접한 간선 중 최소 비용 간선을 선택하여 점진적으로 MST를 구성하는 방식이다. 크루스칼 알고리즘과 달리 노드 중심 접근 방식을 사용한다.2. 특징항목설명비고노드 중심 방식시작 정점 기준 확장크루스칼과 차별화그리디 알고리즘최소 간선 선택 반복최적해 보장우선순위 큐 활용최소 간선 선택성능 최적화한줄..

개요크루스칼 알고리즘(Kruskal Algorithm)은 그래프에서 최소 비용으로 모든 정점을 연결하는 최소 신장 트리(MST, Minimum Spanning Tree)를 찾는 대표적인 그리디 알고리즘이다. 간선을 비용 기준으로 정렬한 후 사이클이 발생하지 않는 범위 내에서 선택하는 방식으로 동작하며, 네트워크 설계 및 최적화 문제에서 널리 활용된다.1. 개념 및 정의크루스칼 알고리즘은 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한 뒤, 가장 작은 간선부터 선택하면서 사이클을 형성하지 않는 경우에만 트리에 포함시키는 방식이다. 이를 위해 Union-Find(Disjoint Set) 자료구조가 필수적으로 사용된다.2. 특징항목설명비고그리디 알고리즘최적 선택 반복전역 최적 보장간선 중심 처리노드가 아..

개요플로이드-워셜(Floyd-Warshall) 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 효율적으로 구하는 알고리즘이다. 다익스트라나 벨만-포드와 달리 단일 시작점이 아닌 전체 정점 간의 경로를 계산하며, 동적 계획법(Dynamic Programming) 기반으로 3중 반복문을 통해 구현된다. 네트워크 분석, 지도 서비스, 경로 최적화 등에서 광범위하게 활용된다.1. 개념 및 정의Floyd-Warshall 알고리즘은 가중치가 있는 방향 그래프에서 정점 i에서 j로 가는 최단 거리 d[i][j]를, 중간 정점 k를 거쳐 최적화해 나가는 방식이다. 음수 가중치는 가능하나, 음수 사이클은 허용되지 않는다.2. 알고리즘 동작 원리 단계 설명 1단계거리 행렬 d[i][j]를 초기화 (자기 자신은 0,..

개요벨만-포드(Bellman-Ford) 알고리즘은 음수 가중치 간선이 있는 그래프에서도 시작 노드로부터의 최단 경로를 찾을 수 있는 알고리즘이다. 다익스트라와 달리 우선순위 큐를 사용하지 않고, 간선 정보를 반복적으로 갱신하는 방식으로 동작한다. 또한, **음수 사이클(Negative Cycle)**의 존재 여부도 탐지할 수 있어, 금융 모델, 네트워크 분석 등에서도 유용하게 활용된다.1. 개념 및 정의벨만-포드 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하되, 음수 간선이 존재해도 정확한 결과를 보장한다. 각 간선을 V-1번 반복하면서 최단 거리를 갱신하며, 마지막 반복에서 거리값이 줄어들 경우 음수 사이클 존재로 간주한다.2. 알고리즘 동작 원리 단계 설명 1단계시작 정점의..

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

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

개요자료구조 알고리즘은 다양한 형태의 데이터를 저장하고 조작하기 위해 설계된 알고리즘으로, 효율적인 연산과 최적화된 문제 해결을 가능하게 한다. 이 알고리즘들은 배열, 스택, 큐, 트리, 그래프 등 특정 자료구조의 특성을 활용하여 구현되며, 소프트웨어 성능 향상에 직접적인 영향을 미친다. 본 글에서는 자료구조 알고리즘의 개념, 분류, 주요 알고리즘, 시간 복잡도 분석, 활용 사례를 중심으로 체계적으로 소개한다.1. 개념 및 정의자료구조 알고리즘은 특정 자료구조의 구조적 특성을 활용하여 데이터를 탐색, 삽입, 삭제, 정렬, 탐색 등의 연산을 수행하는 알고리즘이다. 문제 해결의 핵심 로직으로, 프로그래밍 전반에 걸쳐 필수적인 역할을 한다.2. 알고리즘 분류 분류 설명 주요 자료구조 탐색 알고리즘원하는 데..