[크래프톤 정글 5기] week02 알고리즘 주차 열두번째 날, 다익스트라 알고리즘(최단 경로 알고리즘), B-Tree

크래프톤 정글

 
 
 
다익스트라(dijkstra) 알고리즘(최단 경로 알고리즘)
- 그래프에서 한 정점까지의 최단 경로를 구하는 알고리즘
- 이 과정에서 도착 정점 뿐만 아니라, 모든 다른 정점까지 최단 경로로 방문한다.
- 최단 경로를 구하는 과정에서, “각 노드에 대한 현재까지의 최단 거리” 정보를 항상 저장하고 갱신한다.
- 매번 가장 비용이 적은 노드를 선택하는 것을 반복하기 때문에 그리디 알고리즘으로 분류되기도 한다.

- 방향/무방향 그래프인지는 상관없다.
 
다익스트라 알고리즘 동작과정
- 우선순위 큐 사용을 위해 파이썬 heapq를 사용한다. 최소 힙으로 동작하기 때문에 항상 최단 거리를 pop하게 된다.
1. 최단 거리 테이블을 전부 INF(무한)으로 초기화한다. ( 일반적으로는 INF = int(1e9) 이다.)
2. 출발 노드를 설정하고 큐에 넣는다. 출발노드 거리는 0으로 하며, ( 거리, 노드 ) 튜플 형태로 넣어야 한다. heapq 특성 상 튜플 형태로 저장하면 첫번째 원소를 기준으로 큐를 구성하기 때문이다.
3. 큐에서 노드를 꺼낸다. (우선순위큐라서 알아서 거리 짧은거 나온다)
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 기존의 최단 거리보다 짧을 경우, 최단 거리 테이블을 갱신한다. 갱신되었다면 갱신된 비용과 노드를 큐에 넣는다.
5. 큐가 빌 때까지 3번과 4번을 반복한다.
 
파이썬 다익스트라 알고리즘 연습 코드

import heapq

import sys

INF = int(1e9)

input = sys.stdin.readline

N, E = map(int, input().split())  # 노드갯수, 간선갯수

start = int(input())  # 출발 노드의 번호

graph = [[] for _ in range(N + 1)]

for _ in range(E):

    a, b, c = map(int, input().split())  # 출발노드, 도착노드, 비용

    graph[a].append((c, b))  # (비용, 도착노드)

distance = [INF] * (N + 1)  # 최단경로 저장할 리스트

def dijkstra(start):  # 시작 노드번호를 인자로 받는다

    queue = []

    heapq.heappush(queue, (0, start))  # 거리0, 시작노드번호 큐에 삽입

    distance[start] = 0  # 최단거리 리스트에 시작노드 거리 추가

    while queue:  # 큐가 빌 때까지 진행한다

        dist, here = heapq.heappop(queue)  # 큐에서 노드 꺼내기(거리, 노드)

        if distance[here] < dist:  # 최단거리값이 현재 꺼낸 거리보다 작다면 넘기기

            continue

        for i in graph[here]:  # 꺼낸 노드의 인접 노드에 대하여 반복

            cost = dist + i[0]  # 현재노드거리 + 다음노드까지의 거리를 계산

            if cost < distance[i[1]]:  # 계산했는데 최단거리보다 짧다면 갱신한다

                distance[i[1]] = cost

                heapq.heappush(queue, (cost, i[1]))  # 갱신했으니 큐에 추가하기

dijkstra(start)

for i in range(1, N + 1):

    if distance[i] == INF:

        print("INFINITY")

    else:

        print(distance[i])

# 6 11

# 1

# 1 2 2

# 1 3 5

# 1 4 1

# 2 3 3

# 2 4 2

# 3 2 3

# 3 6 5

# 4 3 3

# 4 5 1

# 5 3 1

# 5 6 2

 
해당 코드의 결과값은 "0 2 3 1 2 4" 이다.
 
1번 노드부터 각 노드까지의 최단 경로값을 출력한 것이다.
2번 노드까지는 2이고 6번 노드까지는 4이다.
 
B-Tree
- 대량의 데이터를 효율적으로 저장하고 검색하는 데 사용되는 자료구조, 디스크 기반의 시스템에서 높은 성능을 보장한다.
- DB 또는 파일 시스템에서 널리 사용된다.
- 데이터를 노드에 저장하고, 노드들을 “트리 형태로 구성”한다. 각 노드는 여러 개의 자식을 가질 수 있다.
- 하나의 노드에 여러 개의 데이터를 저장한다.
 
차수가 p인 B-Tree의 특성
- pointer : 각 노드가 자식을 가리키는 포인터
1. 적어도 노드의 반은 채워야 한다.
- root와 leaf를 제외한 모든 노드의 pointer 수 = 서브트리 수 = 최소 p/2개, 최대 p개
2. root는 pointer를 2개 이상 가져야 한다. -> root의 서브트리의 수는 2 이상이다.
3. 모든 leaf는 같은 레벨이다.(균형 트리이다)
4. 노드의 key 개수
- leaf가 아닌 노드 : pointer 수 -1 개 = 서브트리 수 -1 개
그럴수밖에 없는 게, 포인터 사이사이에 key가 들어간다.
- leaf 노드 : 최소 (p / 2) -1 개 / 최대 p - 1 개
5. 한 노드 내의 key는 오름차순 정렬되어 있다.
 
B-Tree, key
- 각 노드는 하나 이상의 키를 가질 수 있다.
- 키들은 오름차순 정렬되어 있다. -> 더욱 효율적으로 데이터를 찾을 수 있음
- 키는 트리의 탐색/삽입에 사용되며, 효율적으로 데이터를 탐색할 수 있게 한다.
- 각 노드의 키값은 해당 노드가 표현하는 값의 범위를 나타낸다.
- 키 값은 해당 노드에서 관리하는 데이터의 최솟값이 될 수 있다.
- 노드엔 키와 함께 해당 키에 대응하는 데이터(값)가 저장된다.
- 키-값 쌍은 데이터베이스에서 레코드로써 사용될 수 있다.