개발자 모드

오늘은 최단 경로를 찾는 알고리즘 중 Dijkstra 알고리즘의 단점을 보완한 Bellman-Ford 알고리즘에 대해서 알아보겠습니다. Dijkstra 알고리즘의 단점 이전 포스팅에서 말한 Dijkstra 알고리즘의 단점을 찾아보셨나요?? 여기서 간단하게 다뤄봅시다. 0번 정점을 우선 방문했습니다. 그리고 1번 정점과 2번 정점에 대해서 값을 갱신해줍니다. 이제 1번 노드를 선택할 것입니다. 가중치도 같이 갱신해줍시다. 이제 2번 정점에 갈 차례입니다!! 2번 정점에서 값을 갱신해봅시다. 이렇게 모든 노드를 방문하고 알고리즘을 종료합니다. 이제 0번 노드로부터 각 노드의 최단거리를 알았습니다. 0에서 2로 가는 최단거리는 1 0에서 1로 가는 최단거리는 -2 뭔가 이상하지 않나요?? 사실 0에서 1로 가..

오늘은 하나의 그래프 내에 정점 A에서 정점 B까지 가는 최단 경로를 구하는 알고리즘 중 하나인 Dijkstra 알고리즘에 대해서 알아보겠스빈다. Dijkstra 알고리즘이란? 앞서 말씀드린 것처럼, Dijkstra 알고리즘은 그래프 내에서 어떤 정점으로부터 다른 정점으로 갈 때의 최단 경로를 구하는 알고리즘입니다. Dijkstra 알고리즘은 Dynamic Programming에 속하기도 하고 그리디 알고리즘에 속하기도 합니다. 더보기 Dynamic Programming(동적 계획법) DP는 하나의 큰 문제를 작은 문제로 나누어서, 작은 문제들에 대한 해답을 이용해 큰 문제를 해결하는 하나의 문제해결 패러다임입니다. 그리디 알고리즘을 이용해 A에서 B로가는 경로를 구했다고 해봅시다. 그러한 경로가 A ..

오늘은 마지막으로 MST를 찾는 알고리즘 중 Sollin 알고리즘에 대해서 알아보겠습니다. Sollin 알고리즘이란? Sollin 알고리즘도 Kruskal, Prim 알고리즘과 같이 하나의 그래프에서 MST를 찾는 알고리즘입니다. Sollin은 각 정점을 하나의 트리로 간주하고, 각 트리 사이의 간선 중 가장 작은 간선을 선택하여 두 개의 트리를 하나로 이어주는 방식을 통하여 MST를 구성하는 방식입니다. 순차적으로 진행하는 Kruskal과 Prim과는 달리 한번에 진행하여 최악의 상황이 아닌 일반적인 상황에서는 굉장히 빠른 속도로 완료할 수 있다는 장점이 있습니다. 그럼 이제 그림을 통해서 확인해봅시다. 이런 그래프가 있습니다. Kruskal과 Prim에서 다뤘던 그래프와 동일합니다. 여기서 우리는 각..

오늘은 MST를 만드는 알고리즘 중 Prim 알고리즘에 대해서 알아보겠습니다. Prim 알고리즘이란? Prim 알고리즘은 MST(Minimun Spanning Tree)를 찾는 알고리즘 중 하나입니다. 임의의 시작점에서 시작하여 해당 점과 가장 가까운 정점을 추가하여 하나의 트리를 만들고, 해당 트리에서 가장 가까운 정점을 하나씩 추가하여 MST를 만드는 알고리즘입니다. 아래의 그림으로 차근차근 진행해봅시다. Kruskal의 동일한 예제를 통해 확인해봅시다. 가장 먼저 모든 정점 간의 연결이 없다고 생각하고 진행합니다. 거기서 임의의 한 정점을 뽑을건데, 음.. 저는 5번 정점을 시작으로 진행해보겠습니다. 5번 정점과 연결된 가장 가까운 정점은 거리가 2인 3번 노드입니다. 3번 노드와 하나의 트리를 이..

오늘은 최소 신장 트리를 만드는 알고리즘 중 Kruskal 알고리즘에 대해서 알아보겠습니다. Kruskal 알고리즘이란? Kruskal 알고리즘은 MST(최소 신장 트리)를 만드는 알고리즘 중 하나입니다. 이 알고리즘은 그리디 알고리즘을 이용하여 구현합니다. 각 간선마다의 weight를 고려하여 매순간 최소의 weight를 선택합니다. 그 후, 선택한 간선을 넣었을 때 사이클이 생긴다면 해당 간선을 버리는 방식으로 진행됩니다. 아래의 예시를 통해서 조금 더 자세히 알아봅시다. 이전에 MST를 다룬 글에서 예시로 들었던 그래프를 사용해보겠습니다. 각 간선마다 이러한 가중치를 가지는 그래프가 있다고 해봅시다. 우리는 우선, 각 가중치 순으로 정렬하여 우측에 정리해보겠습니다. 자, 이제 우리는 가장 작은 가중..

오늘은 Union-Find에 대해서 알아보겠습니다. Union-Find란? 서로소 집합을 위한 트리 연산의 단어인 Union과 Find를 합친 말입니다. Union은 합집합 연산을 의미하고, Find는 주어진 원소가 어느 집합에 속해있는 지를 계산하는 역할을 합니다. Union 그럼 우리는 이제 Union부터 확인해봅시다. Union은 두 트리를 하나의 트리로 만드는 것을 의미합니다. 이 때 우리는 rank라는 개념으로 Union을 진행합니다. (rank는 간단하게, 트리의 높이라고 생각해도 무방합니다.) rank가 큰 트리 아래에 rank가 작은 트리를 붙여넣는 과정인데, 그림으로 확인해봅시다. 우리는 루트가 6과 4인 트리를 하나로 합치고 싶어합니다. 루트가 6인 트리는 rank가 3이고, 루트가 4..

이번에는 강 연결 성분을 찾는 알고리즘 중 역방향 그래프를 활용하는 Kosaraju 알고리즘에 대해서 알아보겠습니다. Kosaraju 알고리즘 Kosaraju 알고리즘은 이전 글에서도 잠깐 설명했지만, 역방향 그래프를 통해서 구현합니다. 해당 과정을 그림과 함께 확인해봅시다. 위와 같은 그래프가 있습니다. 가장 먼저 우리는 위상 정렬을 통해서 해당 그래프를 선형으로 정렬하겠습니다. 위상정렬은 어떻게 하냐에 따라 결과라 다르지만, 우리는 3번 정점부터 탐색하기 시작하여 [4, 7, 1, 0, 6, 5, 3, 2, 9, 8]로 정렬했다고 해봅시다. 그럼 이제, 이 위상 정렬을 역순을 취해줍니다. [8, 9, 2, 3, 5, 6, 0, 1, 7, 4] 그럼 해당 정렬은 위상 정렬의 역순이 되고, 이는 그림 1..

오늘은 강 연결 성분(Strongly Connected Component)에 대해서 알아보겠습니다. 강 연결 성분(Strongly Connected Component) 강 연결 성분은 방향 그래프에서 연결 성분 내의 임의의 두 정점 u와 v에 대해 u에서 v로 가는 경로가 있고 동시에 v에서 u로 돌아오는 경로가 있는 연결 성분을 의미합니다. 강 연결 성분은 scc라고도 불리며, 이중 연결 성분과 다르게 cut point나 bridge를 포함하지 않습니다. 이러한 그래프가 있다고 해봅시다. 만약 우리가 강 연결 성분을 찾는 알고리즘을 수행한다면 아래와 같은 강 연결 성분을 찾을 수 있습니다. 강 연결 성분 알고리즘 scc를 찾기 위한 알고리즘은 대표적으로 2가지가 있습니다. 스택을 사용하는 Tarjan ..

오늘은 최소신장트리에 대해서 알아보겠습니다!! 그 전에 신장 트리에 대해서 알아봐야하는데, 이는 이전 그래프 관련 글에서 다루었으므로 생략하겠습니다. 최소 신장 트리 최소 신장 트리에서는 간선에 가중치가 존재합니다. 실생활에서 쓰이려면 두 정점 사이의 거리라고 해석해도 될 것 같습니다. 저희는 이러한 가중치를 최소화하고 싶습니다. 그래서 간선의 가중치가 최소인 신장 트리를 생각하게 되었고 이를 최소 신장 트리라고 합니다. 최소 신장 트리를 구성하기 위해 쓰이는 알고리즘은 그리디 알고리즘입니다. 그리디 알고리즘은 매순간 현재로써 가장 좋은 선택을 한다는 의미에서 욕심쟁이 알고리즘이라고 합니다. 이러한 그리디 알고리즘에 대한 개념은 최소 신장 트리를 구현한 알고리즘을 이해하면서 차차 알아가실 수 있습니다. ..

오늘은 이중 연결 성분에 대해서 알아보겠습니다. 이중 연결 성분이란? 이중 연결 성분이란 무방향 그래프의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 산순 경로가 존재하는 연결 성분을 의미합니다. 더보기 연결성분이란? 그래프에서 정점들이 서로 연결되어 있는 부분을 의미합니다. 만약 이러한 그래프가 있으면 [a, b, c, d, e], [f, g, h, i], [j]로 연결성분들이 있다고 할 수 있는 것이죠. 그냥 연결되어있는 정점들을 말하는 것이라고 생각하면 됩니다. 이중 연결 성분은 하나의 간선을 삭제하더라도 다른 경로가 존재하므로 연결 성분 내의 정점들의 연결은 유지됩니다. 그렇다면 이중 연결 성분에서 사용되는 용어에 대해 조금 더 자세하 알아봅시다. 단절 정점(Cut Point) 연결 성분의..