개발자 모드

오늘은 분할 정복 알고리즘의 대표적인 문제 중 하나인 최근접 점의 쌍 찾기에 대해서 알아보겠습니다. 최근접 점의 쌍 찾기 위와 같은 점들이 있다고 합시다. 여기서 가장 가까운 점의 쌍은 어떤 점일까요?? 물론 이 그림에서는 직관적으로 보일 수 있지만, 이러한 점이 많거나 직관적으로 확인하기 어려울 때 말이죠. 우리는 이러한 문제를 알고리즘으로 해결하기 위해서 분할 정복을 사용합니다. 간단한 방법 사실 간단한 방법으로는 모든 점의 쌍에 대한 거리를 구한 후에, 가장 작은 거리를 구하면 됩니다. 하지만 그렇게 되면 시간 복잡도가 O(n^2)이 되어서, 그렇게 좋은 알고리즘 같아 보이진 않습니다. 그래서 우리는 분할 정복을 이용해 시간 복잡도를 낮춰보겠습니다. 분할 정복을 이용한 알고리즘 가장 먼저는 n개의 ..

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

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

오늘은 기본적인 알고리즘인 DFS와 BFS에 대해서 알아보겠습니다. BFS란? BFS란 Breadth-First Search의 약자로 번역하면 너비 우선 탐색입니다. 이는 트리 구조에서 많이 사용되곤 합니다. 어떤 대상 노드로부터 가장 가깝게 연결된 노드들부터 탐색하며 순차적으로 트리의 전체를 순회하는 구조를 일컫습니다. (트리의 용어가 어색한 분들은, 아래의 그림을 보고 우선은 단순하게 이런 식으로 생긴 놈이구나 라고 생각하시면 좋을 것 같습니다.) 아래의 자료를 보면 금방 이해하실 수 있습니다. 루트 노드인 1로부터 가장 가깝게 연결된 3개를 순서대로 순회합니다. 그 후, 2와 연결된 노드를 방문하고, 최종적으로는 트리의 모든 노드를 방문하는 방법입니다. 그럼 BFS의 소스 코드를 살펴보겠습니다. 제..