ITPE * JackerLab

개요A* 알고리즘(A-star)은 그래프 상에서 출발 지점부터 목표 지점까지의 최적 경로를 효율적으로 탐색하기 위한 알고리즘으로, 실제 경로 비용(g)과 목적지까지의 추정 비용(h)을 합산하여 우선순위를 판단하는 휴리스틱 기반 최단 경로 탐색 알고리즘이다. 경로의 정확성과 탐색 속도 간의 균형을 이뤄, 게임 개발, 로봇 경로 계획, 내비게이션 등에서 널리 사용된다.1. 개념 및 정의A* 알고리즘은 다음 공식을 기준으로 노드의 우선순위를 평가한다:f(n) = g(n) + h(n)g(n): 시작 노드에서 현재 노드까지의 실제 거리(비용)h(n): 현재 노드에서 목표 노드까지의 휴리스틱(예상 비용)f(n): 현재 노드를 지나 목표까지의 전체 추정 비용이렇게 계산된 f(n)이 가장 작은 노드를 우선적으로 탐색한..

개요플로이드-워셜(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)를 사용해 가장 짧은 ..

개요DFS(Depth-First Search)는 트리(Tree)나 그래프(Graph) 구조에서 한 방향으로 깊이 탐색을 진행한 뒤, 더 이상 갈 수 없을 때 되돌아오는(Backtracking) 방식의 탐색 알고리즘이다. 재귀 또는 스택 기반으로 구현되며, 경로 탐색, 조합 생성, 백트래킹, 연결 요소 탐색 등에 널리 사용된다. 본 글에서는 DFS의 개념, 구현 방식, 시간 복잡도, BFS와의 차이, 실전 활용 사례 등을 다룬다.1. 개념 및 정의DFS는 시작 노드에서 한 방향으로 가능한 깊이까지 탐색하고, 막히면 이전 지점으로 되돌아가 다시 탐색을 이어가는 방식의 탐색 알고리즘이다. 트리 순회(preorder, postorder)나 그래프의 미방문 노드 전체 탐색 등에 사용된다.2. DFS 탐색 방식 단..