개발자 모드

오늘은 최소 신장 트리를 만드는 알고리즘 중 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) 연결 성분의..

오늘은 정렬방법 중, 위상정렬에 대해서 알아보겠습니다. 위상정렬 위상 정렬(Topological Sort)는 사이클이 없는 방향 그래프에서 정점을 선형 순서로 나열하는 것입니다. 여기서 선형 순서란 일렬로 줄 세우는 것이라고 봐도 되겠습니다. 위상정렬 예제 그럼 위상정렬에 대해서 알아보기 전에!! 왜 위상정렬을 사용하는지, 어떤 경우에 사용하는지에 대해서 알아봅시다. 위와 같은 교과목 체계도가 있다고 해봅시다. 화살표는 선수과목을 의미합니다. 가령, 자료구조는 알고리즘의 선수과목인 것처럼 말이죠. 그런데 여기서 제가 어떤 순서로 들어야할지, 특정 과목부터 시작한다고 하면 무엇을 들을 수 있는지를 위상정렬을 통해서 알아볼 수 있습니다. 만약 위 교과목 체계도에서 위상정렬을 사용한다면, 많은 결과 중 아래와..

이번 글에서는 그래프를 탐색하는 방법 중 하나인 BFS에 대해서 다뤄보겠습니다. BFS란? BFS는 Breath-First Search의 줄임말로, 하나의 정점에서 시작하여 해당 정점과 이웃한 모든 정점을 방문한 뒤, 방문한 정점들의 이웃 정점을 방문하는 방식을 의미합니다. BFS의 탐색 순서를 아래의 그림을 통해 쉽게 확인하실 수 있습니다. BFS의 구현 BFS를 자바로 구현해보겠습니다. import java.util.*; public class Edge{ // 각 노드를 정의 int adjvertex; public Edge(int v){ adjvertex = v; } } public class BFS{ int N; List[] graph; private boolean[] visited; public ..

오늘은 이전 글에서 다룬 그래프에 대한 연장선으로 그래프에서 모든 정점을 탐색하는 방법 중 DFS를 다뤄보겠습니다. DFS란? DFS는 Depth-First Search의 줄임말로, 깊이를 우선으로 하여 탐색하는 방식을 의미합니다. 하나의 정점으로 시작하여, 그 정점과 이웃한 정점 중 하나를 방문합니다. 방금 방문한 정점에서 다시 이웃한 정점을 확인하고, 이웃한 정점들 중 하나를 방문합니다. 이와 같이 진행하는 방식을 DFS라고 합니다. 아래의 그림으로 확인해봅시다. 위와 같은 그래프가 있다고 가정해봅시다.(사실은 트리라고도 볼 수 있습니다.) 위 트리에서 가장 상위의 정점을 시작으로 DFS를 진행한다면 정점 내에 쓰여진 숫자 순서대로 방문합니다. DFS의 구현 자바로 구현한 DFS를 확인해보겠습니다. ..

백트래킹이란? 백트래킹이란 해를 찾는 도중에 주어진 조건에 부합하지 않는 상태일 때, 즉시 이전 상태로 되돌아가 다른 경우의 수를 탐색하는 방법을 말합니다. 보통 이 알고리즘은 DFS나 BFS에서 사용됩니다. 모든 노드를 방문하는 알고리즘 중 하나인 DFS와 BFS에서 조건을 만족하지 않는 노드를 방문했을 때, 해당 노드로부터 연결된 모든 자식 노드들을 방문하지 않고 건너뛰는 방식입니다. 이를 가지치기(Pruning)이라고도 합니다. 저는 이 백트래킹을 조합의 경우의 수를 구하는 과정에서 처음 접했습니다. 따라서 m과 n이 주어졌을 때, 가능한 모든 경우의 수를 출력하는 코드를 소개하면서 백트래킹에 대해 코드와 함께 다뤄보겠습니다. 아래의 코드는 1부터 m까지의 정수가 있다고 했을 때, mCn의 모든 경..