Developer Wony Story

최단 경로 문제

• 두 노드를 잇는 가장 짧은 경로를 찾는 문제
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 최단 경로 문제
   • 그래프 내의 특정 노드 u에서 출발, 또 다른 특정 노드 v에 도착하는 가장 짧은 경로 찾는 문제
2. 단일 출발 최단 경로 문제
   • 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
3. 전체 쌍 최단 경로
   • 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제

다익스트라 알고리즘

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제에 적절

다익스트라 알고리즘 로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며 최단 거리를 갱신하는 기법
• 다익스트라 알고리즘은 BFS와 유사
  •  첫 정점부터 각 노드 간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드 간의 가장 짧은 거리를 해당 배열에 업데이트
• 우선순위 큐를 활용 : 우선순위 큐는 Min Heap방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
  1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
     • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장(inf)
     • 우선순위 큐에 (첫 정점, 0)만 먼저 넣음
  2. 우선순위 큐에서 노드를 꺼냄
     • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점만 꺼내짐
     • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교
     • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우 배열에 해당 노드의 거리를 업데이트
     • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다
       -> 결과적으로 너비 우선 탐색과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
       -> 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다 더 긴 거리를 가진 경우에 해당 노드와 인접한 노드 간의 거리 계산을 하지 않음
  3. 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복

알고리즘 구현

graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

import heapq

def dijkstra(graph, start):
    distances = { node: float('inf') for node in graph }
    distances[start] = 0
    pq = []
    heapq.heappush(pq, [distances[start], start])
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node]:
            continue
        
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(pq, [distance, adjacent])
                
    return distances

*A부터 F까지의 최단 경로 출력 코드

import heapq

def dijkstra(graph, start, end):
    distances = {node: [float('inf'), start] for node in graph}
    distances[start][0] = 0
    pq = []
    heapq.heappush(pq, [distances[start][0], start])
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)
        
        if current_distance > distances[current_node][0]:
            continue
            
        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[adjacent][0]:
                distances[adjacent] = [distance, current_node]
                heapq.heappush(pq, [distance, adjacent])
    
    path = end
    path_output = [end]
    while distances[path][1] != start:
        path_output.append(distances[path][1])
        path = distances[path][1]
    path_output.append(start)
    path_output = list(reversed(path_output))
    
    return path_output
    
result = dijkstra(graph, 'A', 'F')
print(result)
print("->".join(result))

"""

['A', 'D', 'E', 'F']
A->D->E->F

"""

시간 복잡도

• 과정 1: 각 노드마다 인접한 노드 간선(E)들을 모두 검사 => O(E)
• 과정 2: 우선순위 큐에 노드/거리 정보를 넣고 삭제하는 과정 => O(ElogE)
• 과정 1 + 과정 2의 시간을 합치면 결국 O(ElogE)

BFS와 DFS란?

• 너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색
• 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색
• 시간 복잡도는 정점의 수(V)와 간선의 수(E)를 더한 O(V + E)
• 파이썬에서는 딕셔너리와 리스트 자료구조를 활용해서 구현 가능

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

너비 우선 탐색(BFS)

- 큐의 역할을 하는 visited와 need_visit을 이용해 구현

- 방문한 노드는 visited에, 방문할 노드는 need_visit에 추가

def bfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop(0)
        if node not in visited:
            visited.appned(node)
            need_visit.extend(graph[node])
    
    return visited

깊이 우선 탐색(DFS)

- 큐의 역할을 하는 visited, 스택의 역할을 하는 need_visit을 이용해 구현

def dfs(graph, start_node):
    visited = list()
    need_visit = list()
    
    need_visit.append(start_node)
    
    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    
    return visited

병합 정렬이란?

재귀 용법을 활용한 정렬 알고리즘으로 배열을 절반으로 잘라나가고 이를 다시 정렬된 배열의 형태로 합병하며 정렬함.

알고리즘 구현

병합 정렬은 배열을 나누는 함수, 나누어진 배열을 하나로 합치는 함수 2가지를 구현해야 함

1. merge 함수

def merge(left, right):
    merged = list()
    left_index, right_index = 0, 0
    
    while len(left) > left_index and len(right) > right_index:
        if left[left_index] > right[right_index]:
            merged.append(right[right_index])
            right_index += 1
        else:
            merged.append(left[left_index])
            left_index += 1
    
    while len(left) > left_index:
        merged.append(left[left_index])
        left_index += 1
        
    while len(right) > right_index:
        merged.append(right[right_index])
        right_index += 1
        
    return merged

2. merge_split 함수(실질적인 병합 정렬 역할의 함수)

def merge_split(data):
    if len(data) <= 1:
        return data
    
    mid = len(data) // 2
    left = merge_split(data[:mid])
    right = merge_split(data[mid:])
    
    return merge(left, right)

시간 복잡도

각 단계별로 O(N)으로 실행되고, 그 단계들은 logN개만큼 만들어지므로 O(logN)의 시간 복잡도를 가진다.

결국 이 모든 과정을 통합하면 O(NlogN)이라는 시간 복잡도가 나오게 된다.

1. 퀵 정렬이란?

• 기준점(Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 에디터는 오른쪽으로 모아서 정렬을 하는 것
• 각 왼쪽, 오른쪽으로 나눈 것은 재귀 용법을 통해 다시 왼쪽, 오른쪽으로 나눔
• 반환하는 값은 [정렬된 왼쪽 리스트] + [Pivot] + [정렬된 오른쪽 리스트]

2. 알고리즘 구현

def qsort(data):
    if len(data) <= 1:
        return data
    left, right = list(), list()
    pivot = data[0]
    for index in range(1, len(data)):
    	if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])
    return qsort(left) + [pivot] + qsort(right)

파이썬의 list comprehension을 사용한다면 위의 코드보다 짧게 구현이 가능해진다.

def qsort(data):
    if len(data) <= 1:
    	return data
    pivot = data[0]
    left = [ item for item in data[1:] if pivot > item ]
    right = [ item for item in data[1:] if pivot <= item ]
    return qsort(left) + [pivot] + qsort(right)

3. 시간복잡도

일반적으로는 O(N logN)이지만, 최악의 경우인 맨 처음 pivot이 배열 내에서 가장 크거나 가장 작으면 모든 데이터를 비교하는 상황이 나오므로 O(N^2)이 될 수 있다.

1. 삽입정렬이란?

두번째 인덱스부터 시작하여 해당 인덱스 앞에 있는 데이터부터 비교해서 그 값이 더 크다면 값을 서로 교환.

2. 구현코드

def insertion_sort(data):
	for stand in range(len(data)-1):
    		for idx in range(stand+1, 0, -1):
            		if data[idx] < data[idx-1]:
                		data[idx], data[idx-1] = data[idx-1], data[idx]
                        else:
                		break
	return data

3. 시간복잡도

• 최악의 경우: O(N^2)
• 완전 정렬이 된 경우: O(N)

탐색할 자료를 두 그룹으로 나누고 찾으려는 데이터가 있을만한 곳을 탐색하는 방법이다.

자세하게 설명하자면 주어진 리스트가 있다고 하자.  여기서 리스트는 반드시 정렬된 상태여야 한다.

우선 리스트의 중간값이 찾으려는 값인지 찾고 찾으려는 값이 중간값보다 작으면 다시 왼쪽으로, 크면 오른쪽으로 좁혀가며 찾아간다. 

1. 분할 정복 알고리즘(Divide & Conquer)

• Divide: 주어진 문제를 작은 단위로 나눈다.
• Conquer: 작게 나누어진 문제를 해결하고 점점 상위 단계의 문제를 해결해 나간다.

이진 탐색도 분할 정복 알고리즘의 형식으로 해결한다. 

2. 코드 구현

def binary_search(data, search):
    if len(data) == 1 and data[0] == search:
        return True
    if len(data) == 1 and data[0] != search:
        return False
    if len(data) == 0:
        return False
    
    mid = len(data) // 2
    if data[mid] == search:
        return True
    elif data[mid] > search:
        return binary_search(data[:mid], search)
    elif data[mid] < search:
        return binary_search(data[mid + 1:], search)