정의 MST(Minimum Spanning Tree: 최소 비용 신장 트리)란, 신장 트리들 중 가장 최소한의 비용 및 가중치의 합이 가장 작은 트리를 뜻한다. 신장 트리란, 그래프에서 모든 정점에 대한 최소한의 연결만을 남긴 그래프이다. 도입 일반적으로 MST를 구하는 몇가지 알고리즘이 존재한다. 그리디 알고리즘 ...

정의 크루스칼 알고리즘이란, MST를 구하기 위해 사용되는 알고리즘이다. 동작 방식 간단히 크루스칼 알고리즘의 동작 순서에 대해 작성해보자. 주어진 모든 간선 정보에 대해 간선 비용이 낮은 순서(오름차순)로 정렬을 수행 정렬된 간선 정보를 하나씩 확인 하면서 현재의 간선이 노드들 간의 사이클을 발생시키는지 확인 만약 사이클이 발생하지 ...

정의 다익스트라 알고리즘은 DP(혹은 그리디)를 이용하여, 노드와 노드 사이의 최단 경로를 구하는 알고리즘이다. 동작 방식 간단한 다익스트라 알고리즘의 작동 방식에 대해 알아보자. 모든 노드의 이동 경로를 일단 나와있는 대로 2차원 배열을 통해 저장한다. 출발 노드를 설정한다. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. ...

정의 위상 정렬이란, 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것. 특징 먼저, 진입차수와 진출차수에 대해 알아야 한다. 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수 구현 방식 위상정렬은 DFS나 Queu...

정의 프림 알고리즘(Prim’s Algorithm)이란, MST를 구하기 위해 사용되는 알고리즘이다. 특징 프림 알고리즘의 경우, 다익스트라 알고리즘과 거이 유사한 알고리즘의 형태를 보인다. 다익스트라 알고리즘의 평가 함수에서 현재 경로까지의 이동거리를 누적하지 않고, 간선 가중치만을 이용한다면 이 프림 알고리즘이 되는 것이다. 또한, 다익스트라 알...

정의 그래프는 트리와 유사하면서 차이를 가지고 있다. 오히려 정확한 정의를 바라보자면, 트리가 그래프의 유형 중 하나라고 볼 수 있다. 그래프란, 정점(Vertex)와 변(Edge)로 구성되어 있는 자료구조형이다. 특징 그래프는 크게 두가지로 나눌 수 있는데, 이는 변에 방향성이 있는지에 따라 변한다. 유향 그래프(Directed Graph)의...

정의 도입 메모리는 네가지 영역을 가지고 있다.

문제 지도 위의 모든 나라를 색칠하는데, 인접한 나라끼리 색이 겹치지 않게끔 칠하려면 4가지 색만으로도 충분한지를 따지는 문제다. 이는 위상 정렬으로 푸는 문제이다. 관련 문제 5색정리

문제 링크 11279번 해결책 import sys class PriorityQueue: def __init__(self, capacity: int = 9999999) -> None: self.arr = [None] * capacity self.capacity = capacity self.siz...

문제 링크 18258번 해결책 import sys class Node: def __init__(self, val: int): self.val = val self.ptr = None class Queue: def __init__(self, limit: int = 1000): self.st...