기록

시간 복잡도(Time Complexity)

시간 복잡도는 알고리즘이 입력 코기(n)에 따라 얼마나 많은 연산을 수행하는지를 수학적으로 표현한 것이다.

보통 알고리즘의 효율성과 실행 속도를 평가하기 위해 사용된다.

시간 복잡도는 주로 세 가지 표기법으로 분류된다.

빅-오(Big-O)

최악의 경우(Worst Case)를 나타내며, 가장 많이 사용되는 표기법이다. 알고리즘이 가장 오래 걸리는 상황에서의 연산 횟수를 설명한다.

빅-오메가(Big-Ω)

최선의 경우(Best Case) 를 나타내며, 가장 적게 걸리는 상황에서의 연산 횟수를 설명한다.

빅-세타(Big-Θ)

상한과 하한이 같을 때 사용되며, 정확한 수행 시간을 나타낸다.

예시

다음은 1~100 사이에서 무작위 숫자를 뽑고, 해당 숫자를 찾을 때까지 순회하는 알고리즘이다.

import random

randNumber = random.randrange(1, 101)

for i in range(1, 101):
    if i == randNumber:
        print(i)
        break

Best Case

뽑은 숫자가 1일 경우, 단 1번만에 찾는다 → Ω(1)

Average Case

1 일 때 1번

2 일 때 2번

...

n 일 때 n번

전체 평균 횟수를 계산하면 1 + 2 + ... + n으로 등차수열을 계산하면 n(n + 1) / 2, 이는 입력 크기 n이 커질수록 선형적으로 증가하므로, Average Case는 O(n)으로 표현한다.

Worst Case

뽑은 숫자가 100일 경우, 100번 순회 → O(n)

A* 알고리즘

주어진 출발점에서 목표지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.

최단 경로를 찾는다는 공통점을 가지지만, A*는 데이크스트라에 휴리스틱(Heuristic)이라는 개념을 추가하여 효율성을 높인 알고리즘이다. 본래 A 알고리즘이라고 불렸지만 적절한 휴리스틱에 따라서 최적의 알고리즘이 되기 때문에 A* 알고리즘이라 불린다.

데이크스트라와 관계

A*알고리즘은 데이크스트라 알고리즘의 확장 버전이라고 볼 수 있다. 데이크스트라에서 사용하는 시작점으로부터의 실제 거리 g(n)에 목표점까지의 예상 거리 h(n)라는 휴리스틱을 더한 값을 우선순위 기준으로 사용한다.

f(n) = g(n) + h(n)

g(n) : 시작점에서 현재 노드 n까지의 실제 비용

h(n) : 현재 노드 n에서 목표 노드 goal까지의 휴리스틱 비용(예상 비용)

f(n) : 시작점에서 n을 거쳐 goal까지 가는 총 예상 비용

휴리스틱 h(n)이 핵심 역할을 하며, 이 값이 얼마나 목표에 가깝게 추정하느냐에 따라서 A*의 효율성이 결정된다.

휴리스틱

가장 대표적으로 사용되는 두 가지 방법으로 맨해튼 거리(Manhattan Distance)와 유클리드 거리(Euclidean Distance)가 있다.

두 가지 방법 모두 특히 격자 기반의 길 찾기 문제나 2D/3D 공간에서의 최단 경로 탐색에 자주 활용된다.

맨해튼 거리(Manhattan Distance)

격자에서 한 점에서 다른 점까지 가로 또는 세로로만 이동할 수 있을 때의 최단 거리를 의미한다. 마치 도시의 블록을 따라 이동하는 것과 같다고 하여 맨해튼 거리 또는 택시 거리라고 불린다.

계산은 두 점 (x1, y1) , (x2, y2)가 있을 때 두 점 사이의 맨해튼 거리는 |x1 - x2| + |y1 - y2|이다.

이동이 수직(상하) 또는 수평(좌우)으로만 가능한 경우와 각 이동에 대한 비용이 모두 동일할 때 적합하다. (미로, 체스, 격자 등)

유클리드 거리(Euclidean Distance)

가장 일반적인 직선거리 개념으로 두 점을 잇는 가장 짧은 선의 길이이다.

두 점 (x1, y1) , (x2, y2) 사이의 유클리드 거리는 피타고라스의 정리를 사용하여 계산된다.

√ (x1 - x2)^2 + (y1 - y2)^2

대각선 이동이 가능한 경우, 이동 비용이 거리에 비례하는 경우에 사용하기 적합하다.

허용성

A* 알고리즘에서 휴리스틱 함수가 가져야 할 중요한 속성으로, 최단 경로를 정확하게 찾을 수 있는 여부를 보장하는 기준, 즉 A* 알고리즘의 정확성을 보장하는 핵심 조건이다.

허용 가능한 휴리스틱 함수는 어떤 노드에서 목표 노드까지의 예상비용이 실제 최단 거리보다 절대로 크지 않아야 한다.

h(n) ≤ 실제 최단 거리

h(n) : 현재 노드 n에서 목표 노드까지의 휴리스틱 비용

실제 최단 거리 : 현재 노드 n에서 목표 노드까지의 실제 최단 거리

A* 알고리즘이 최단 경로를 항상 찾을 수 있도록 보장하기 때문에 허용 가능한 휴리스틱을 사용하는 것이 중요하다.

최단 경로 보장

만약 휴리스틱이 실제 거리보다 과대평가한다면, 때때로 실제 최단 경로가 아닌 다른 경로를 최단 경로로 착각하여 탐색을 조기에 종료할 수 있다. 하지만 허용 가능한 휴리스틱은 항상 실제보다 같거나 작은 값을 예측하므로 항상 실제 최단 경로를 놓치지 않고 탐색하기 된다.

효율성과 균형

허용성은 정확성을 보장하지만, 너무 보수적인 휴리스틱은 A*가 데이크스트라처럼 넓은 영역을 탐색하게 만들어 효율성이 떨어질 수 있다. 따라서 이성적인 휴리스틱은 허용 가능하면서도 실제 최단 거리에 최대한 가까운 값을 예측하여, 최단 경로를 보장하면서도 탐색 효율성을 극대화하는 것이다.

예) 격자에서 가로/세로 이동만 가능하다고 가정할 때, 맨해튼 거리는 두 점 사이의 실제 최단 거리와 동일하거나 더 짧다. 장애물이 없는 최단 경로는 항상 맨해튼 거리보다 길거나 같을 수 없기 때문에 허용 가능한 휴리스틱이다.

예) 두 점 사이의 가장 짧은 직선거리는 유클리드 거리이다. 실제 경로가 장애물 때문에 직선으로 갈 수 없다면, 실제 경로는 유클리드 거리보다 길어질 수밖에 없으며 유클리드 걸리도 실제 최단 거리보다 과대평가하지 않으므로 허용 가능한 휴리스틱이다.

데이크스트라(Dijkstra) 알고리즘

데이크스트라 알고리즘은 그래프에서 꼭짓점(노드) 간의 최단 경로를 찾는 알고리즘이다.

기본적으로 단일 출발점(Single-Source)에서 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 데 활용되며, 음의 가중치(negative weights)가 없는 그래프에서만 정확하게 동작한다.

데이크스트라 기본 형태 (선형 탐색 방식)

데이크스트라 알고리즘의 초기 형태는 우선순위 큐를 사용하지 않고, 일반적인 배열 또는 리스트를 사용하여 구현되었다. 이 방식은 매 단계마다 방문하지 않은 노드 중에서 시작점으로부터의 거리가 가장 짧은 노드를 선형 탐색하여 찾아낸다.

시간 복잡도

- 그래프에 V개의 노드가 있을 때, 매번 가장 짧은 노드를 찾기 위해 O(V) 시간이 소요된다.

- 가장 짧은 노드 선택과정을 총 V번 반복하기 때문에, 전체 시간 복잡도는 O(V * V) = O(V^2)이 된다.

플로우(일반 배열/리스트 사용)

기본 형태에서는 일반 배열/리스트를 사용하여 구현했는데 이 경우 그래프의 모든 노드를 방문하면서 각 노드를 방문할 때마다 짧은 거리를 찾는 과정이 필요한데 이때 V개의 노드가 있다면 모든 노드를 순회하는 작업이 O(V)의 시간이 걸리고 여기서 매 반복마다 O(V)의 시간이 소요되는 '가장 짧은 거리 노드 선택' 과정이 총 V번 반복되기 때문에 전체 시간 복잡도는 O(V^2)이 된다.

플로우

dist[] : 각 노드까지의 최단 거리를 저장, infinity 초기화
visited[] : 각 노드를 방문했는지 여부, false 초기화
start_node ( dist = 0 )

그래프의 노드 V개를 모두 방문할 때까지 다음 동작을 반복한다.

min_dist = infinity
closest_node = -1;
visited == false 인 노드(index i) 
- dist[i] < min_dist : min_dist = dist[i], closest_node = i

선택된 노드는 방문 처리를 하고 visited [closest_node] = true, 이 노드의 최단 거리는 확정됨

만약 closest_node == -1이라면 모든 노드가 방문되었거나 연결되지 않은 경우로 반복을 종료한다.

이후 인접 노드 거리를 갱신한다.

closest_node와 연결된 모든 인접 노드에 대해서

visited == false && 
dist[closest_node] + edge_weight(closest_node, neighbor) < dist[neighbor]
(인접 노드를 거치는 것이 현재 저장된 최단 거리보다 더 짧다면 최단 거리를 갱신)

모든 반복이 끝나면 최종적으로 dist [] 배열에는 시작 노드로부터 각 노드까지의 최단 거리가 저장된다.

우선순위 큐를 활용한 개선된 데이크스트라

데이크스트라 알고리즘의 효율성을 높이기 위해 가장 짧은 거리 노드 선택 과정을 개선한 방식으로 우선순위 큐(Priority Queue)를 사용한다.

우선순위 큐는 선입선출 방식인 일반적인 큐와 달리 데이터들이 우선순위를 가지고 있어, 가장 높은(또는 낮은) 우선순위를 가진 데이터가 먼저 나가는 자료구조이다.

시간복잡도

- 우선순위 큐는 가장 작은 값 추출(extract_min) 및 값 삽입(insert) 연산을 각각 O(log N) (N은 큐에 있는 원소의 개수)의 시간 복잡도로 수행한다.

- 간선의 개수를 E라고 할 때, 각 간선이 한 번씩 큐에 삽입될 수 있으므로, 전체 시간 복잡도는 O((V+E)logV) 또는 O(ElogV)로 개선된다.

플로우

dist[] : 최단 거리 저장 배열, 무한대 초기화
pq(priority_queue) : 우선순위 큐, (거리, 노드) 튜플로 저장, 가장 거리가 짧은 튜플이 항상 최상단에 정렬
시작 노드 : pq <- (0, start_node) 삽입

pq에서 거리 값이 가장 작은 튜플을 추출, 짧은 경로가 발견되어 처리되었다면 확정된 노드를 불필요하게 재처리하는 것을 방지하기 위해서 무시하고 다음 반복으로 넘긴다.

current_dist > dist[current_node] continue

인접 노드 거리 갱신, 현재 방문 중인 노드와 인접한 노드들에 대해서 해당 간선의 가중치에 대해 반복

dist[current_node] + edge_weight < dist[neighbor]
dist[neighbor] = dist[current_node] + edge_weight
pq <- (dist[neighbor], neighbor) insert

current_node를 경유할 때 인접한 노드까지의 거리가 현재 저장된 값보다 더 짧다면 해당 값으로 갱신하고 거리와 노드를 우선순위 큐에 저장한다.

pq가 완전히 비워지게 되면 dist [] 배열에는 시작 노드에서 다른 모든 노드까지의 최단거리가 저장된다.