봉황대 in CS

최소 신장 트리 (Minimum Spanning Tree, MST) 최소 신장 트리는 주어진 그래프의 모든 정점을 연결하는 부분 그래프 중, 그 가중치의 합이 최소인 트리를 말한다. * 부분 그래프(Subgraph) : 주어진 그래프에서 일부 정점과 간선만을 선택하여 구성한 그래프 더 쉽게 말하자면 가장 적은 비용으로 모든 노드를 연결한 그래프를 말하며, 이때 사이클이 발생하면 안 된다. * 정점 = 노드 * 간선 = 비용 = 가중치 (그래프에서 선에 해당하는 부분) 동일한 그래프에서 최소 신장 트리는 여러 개가 나올 수 있다. 가중치의 합이 최소이기만 하면 되기 때문이다. 최소 신장 트리를 구하기 위한 알고리즘은 2가지가 존재하며, 각각 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이다...

최소 신장 트리(Minimum Spanning Tree, MST)에 대해서 찾아보다가 이를 구현하는 두 가지 방법 중 크루스칼(Kruskal) 알고리즘의 기본 베이스가 Union-Find 임을 보고, 먼저 Union-Find에 대해서 공부한 후 정리해보고자 한다. Union-Find Union-Find 알고리즘은 여러 개의 노드가 존재할 때 두 개의 노드를 선택한 후, 현재 이 두 노드가 서로 같은 그래프에 속하는지를 판별하는 알고리즘이다. Disjoint Set Disjoint Set(분리 집합)은 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조인데, 이 Disjoint Set을 표현할 때 사용하는 알고리즘이 바로 Union-Find 알고리즘이다. 이 알고리즘은 전체 집합..

배낭 문제 (Knapsack Problem) 배낭 문제란, 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭 문제에는 2가지 경우가 있다. 1. 분할 가능 배낭 문제 (Fractional Knapsack Problem) - 짐을 쪼갤 수 있는 경우 2. 0-1 배낭 문제 (0-1 Knapsack Problem) - 짐을 쪼갤 수 없는 경우 짐을 쪼갤 수 있는 경우에는 그리디 알고리즘을 통해 해결할 수 있다. (가치가 가장 큰 물건부터 담고, 남은 무게만큼 물건을 쪼개는 방식) 짐을 쪼갤 수 없는 경우에는 동적 계획법(Dynamic Programming, DP)을 통해 해결할 수 있다. 브..

플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 ) 즉, (1) 정점 a에서 정점 b로 가는 최소 비용과 (2) 정점 a에서 정점 k로 가는 비용 + 정점 k에서 정점 b로 가는 비용을 비교하여 더 적은 비용을 가지는 쪽을 취하는 것이다. N개의 노드가 있을 때, N번만큼의 단계를 반복하여 점화식에 따라 2차원 리스트를 갱신하기 때문에 동적 계획법(Dynamic Programming) 알고리즘에 속한다. ( ↔︎ 다익스트라 : 탐욕(그리디) 알고리즘 ) * 동적 계획법(Dynamic Programming, D..

너비 우선 탐색 (Breadth-First Search, BFS) 인접한 노드를 먼저 탐색하는 방식 (매 단계에서 가능한 경우의 수들을 모두 확인하면서 탐색) * 최대한 넓게 이동하여 더 이상 옆으로 갈 곳이 없을 경우 아래로 이동 1. Queue를 통해 구현 2. 최단 경로를 찾을 때 주로 사용 탐색 경로를 결과로 출력한다고 하면 BFS의 파이썬 구현 코드는 다음과 같다. * 양방향 큐(deque) 사용 # N×N 2차원 배열 dy = (-1, 0, 1, 0) dx = (0, 1, 0, -1) # 방문한 노드일 경우 True / 방문하지 않은 노드일 경우 False visited = [[False for _ in range(N)] for _ in range(N)] def BFS(r, c): q = de..