공부하자

최대공약수 GCD (Greatest Common Divisor) 두 자연수가 공통으로 가지는 약수들 중 가장 큰 값을 의미한다. 최소공배수 LCM (Least Common Multiple) 두 자연수의 배수들 중에서 가장 작은 값을 의미한다. 참고로 최소공배수는 최대공약수를 활용하여 바로 구할 수 있다. 최소공배수 = 두 자연수의 곱 / 최대공약수 유클리드 호제법 (Euclidean Algorithm) 유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a,b에 대해 a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를..

그리디 알고리즘이란? 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자." 라는 모토를 가지는 알고리즘 설계 기법이다. 정치적으로 보면 당면한 경제 문제를 가장 빠르게 해결해 줄 것이라고 여기는 대통령을 찍거나 당면한 지역 인프라 과제를 가장 빠르게 해결해 줄 것이라고 여기는 시장·군수·도지사 또는 국회의원을 찍는 의사결정 행위로 볼 수 있다. 또한 유명한 마시멜로 실험에 비유할 수 있다. 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 계속해서 먹는것이다. 하지만, 이 그리디 알고리즘을 사용하여 도출된 결과값은 항상 가장 최적의 결과를 보장해주지는 않는다. 위의 예시와 같이 지금 당..

다익스트라 알고리즘이란? 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘이다. 한 정점에서 다른 정점까지의 최단 경로를 구하는데, 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다. 그래프 탐색 알고리즘 중 최소 비용을 구하는 알고리즘은 다익스트라 외에도 벨만-포드 알고리즘 Bellman-Ford Algorithm, 플로이드-워셜 Floyd-Warshall 알고리즘 등이 있다. (벨만-포드 알고리즘은 음수 가중치의 그래프도 탐색 가능하다.) 그중에서도 다익스트라 알고리즘은 프림 알고리즘을 살짝 변형한 형태인데, 두 가지 차이점이 존재한다. 차이점은 다음과 같다. ..

프림 알고리즘이란? 최소 신장 트리 (Minimum Spanning Tree, MST) 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법이다. 프림 알고리즘의 시퀀스 1. 시작할 정점을 MST집합에 넣는다. 2. MST집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점을 MST집합에 넣는다. 3. 2번과정을 MST집합의 원소 개수가 그래프 정점의 갯수가 될 때까지 반복한다. 4. 만들어진 MST집합의 가중치를 다 더해서 MST Cost 산출. 크루스칼 알고리즘 vs 프림 알고리즘 크루스칼 알고리즘 : Kruskal's Algorithm 프림 알고리즘 : Prim's Algorithm 그래프의 최소 가중치 간선들을 정렬된 순서로 추가하여..

크루스칼 알고리즘이란? 최소 신장 트리 구현에 사용되는 알고리즘으로, 가중치가 있는 그래프의 모든 간선들을 대상으로 1. 최소 비용의 간선으로 구성 2. 사이클을 형성하지 않음 의 조건을 지켜가며 각 단계마다 최선의 해를 선택하기에 그리디 알고리즘에 기원을 둔다. 크루스칼 알고리즘의 시퀀스 1. 그래프의 간선들을 가중치 기준으로 오름차순 정렬한다. 2. 정렬된 간선들 중 가중치가 작은 순서대로 사이클을 형성하지 않는 한 선택한다. 3. 선택된 간선으로 MST를 구현한다. 4. MST 집합의 원소의 개수가 V-1개가 될때까지 위 단계를 반복한다. 이때, 주의해야 할 점은 사이클을 형성하지 않게 정렬된 간선들을 선택한다는 것이다. 따라서 사이클을 형성하는지 안하는지에 대한 판가름을 해줄 수 있는 메소드를 같..

너비 우선 탐색이란? (breath First Search, BFS) 시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성되고, 현재 경계에 인접한 정점을 반복적으로 탐색한다. BFS의 중요한 특징은, 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다는 점이다. 이를 구현할 때에는, 보통 경계를 별도의 자료구조로 만들어 명시적으로 사용하지 않고, 대신 정점 ID를 큐(Queue)에 저장하여 시작 정점과 가까운 정점을 멀리 있는 정점보다 먼저 방문할 수 있도록 구현한다. 다음은 너비 우선 탐색을 표현한 애니메이션이다. 두 애니메이션을 보면 그래프를 탐색함에 있어 무조건 같은 Level의 부모 정점들이 먼저 탐색되고, 그 다음 Level에 있는 자식 정점들이 나중..

그래프 탐색이란? 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것. 이때, 어떤 탐색 알고리즘을 쓰는지에 따라 방문하는 방식이 달라진다. 깊이 우선 탐색이란? (DFS, Depth First Search) 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 그리고 더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방식을 백트래킹(Backtracking) 이라고 한다. 다음은 깊이 우선 탐색을 표현한 애니메이션이다. 애니메이션에서 연한 녹색으로 칠해지는것이 정점을 방문하는 절차이고, 진한 녹색으로 칠해지는것이 더 방문할 정점이 있는지 탐색하는 백트래킹 과정이다. 트리구조에서 전..