봉황대 in CS

백준 2224번을 풀며 플로이드-와샬 알고리즘을 사용할 때 주의해야 할 점을 깨닫게 되었고, 이를 잊지 않기 위해서 이렇게 글로 남긴다. 플로이드-와샬 알고리즘 이 알고리즘이 무엇인지에 대해서는 이전에 작성한 글을 참고하길 바란다. [알고리즘] 플로이드-와샬(Floyd-Warshall) 알고리즘 플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모 eunajung01.tistory.com 문제 2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전..

정렬 알고리즘들에 대하여 알아보던 중, 합병 정렬(merge sort)과 퀵 정렬(quick sort)이 분할 정복 알고리즘 중 하나임을 깨닫고 먼저 분할 정복에 대해 정리하기 위하여 이 글을 작성한다. 분할 정복 (Divide-and-Conquer) '쪼개서 풀고 합하기' : 문제를 잘게 쪼개는 분할(Divide) + 문제를 풀어서 합하는 정복(Conquer) 분할 정복이란, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다. 즉, 문제를 작은 2개의 문제로 분리한 후 각각을 해결한 다음, 그 결과들을 모아서 원래의 문제를 해결하는 전략을 말한다. (Top-down, 하향식 접근법) 조건 1. 문제를 쪼개 나가는 과정에서, 큰 문제와 작은 문제의 구조가 동일하거나 비슷해야 한다. =..

최소 신장 트리 (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..