그리디 알고리즘이란?
그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘임
동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념
미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
그렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘
장점
다른 최적해 계산 알고리즘에 비해 적은 비용 빠른 속도
단점
당장 그 순간의 최적 값을 찾기 때문에 항상 최적 해를 찾는 것은 불가능
Dynamic Programming(동적 계획법)이란?
전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식
동적 계획법에 대해서 설명해주세요
주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법을 말함. 동적 계획법에서는 어떤 부분 문제가 다른 문제들을 해결하는 데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고, 그 결과를 재활용하는 메모이제이션 기법으로 속도를 향상시킬 수 있음
동적 계획법이 갖는 2가지 조건은 무엇인가요?
중복되는 부분 문제와 최적 부분 구조가 동적 계획법이 갖는 2가지 조건임
중복되는 부분문제는 나눠진 부분 문제가 중복되는 경우로, 메모이제이션 기법을 통해 해결하고, 최적 부분 구조느를 가진 다는 것은 전체 문제의 최적해가 부분 문제의 최적해들로 구성된다는 뜻임
그리디 알고리즘과 동적 계획법을 비교해주세요
그리디 알고리즘은 각 단계에서 최적의 상황을 선택하여 문제를 해결하는 방법이고, DP는 주어진 문제를 풀기 위해, 문제를 여러 개의 하위 문제로 나누어 푸는 방법을 말함
DP는 최적 경로를 구할 수 있으니 시간이 오래걸리고, 그리디는 시간이 적게 들지만 최적이 아닌 경우가 있거나 풀리지 않는 경우가 있음
그리디 알고리즘과 동적 계획법은 각각 어떤 경우에 사용하나요?
그리디 알고리즘은 앞의 선택이 이후의 선택에 영향을 주지 않을 때 사용을 하고, 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성되어 있어야 함.
DP는 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견될 경우에 사용함. 작은 문제에서 구한 정답은 이후에 큰 문제에서도 사용될 수 있음.
MST란?
들어가기전에..
Spanning Tree?
그래프 내의 모든 정점을 포함하는 트리를 말함
신장 트리 = 스패닝 트리
최소 연결 부분 그래프를 말함 => 간선의 수가 가장 적음을 말함
n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리형태가 되고 이게 바로 Spanning Tree가 됨
즉 그래프에서 일부 간선을 선택해서 만든 트리를 말함
특징
하나의 그래프에는 많은 신장 트리가 존재할 수 있음
DFS,BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있음
신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안됨
Minimum Spanning Tree
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
=> 최소 신장 트리
특징
간선의 가중치의 합이 최소여야 함
n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 함
사이클이 포함되어서는 안됨
사용사례
도로건설, 전기 회로, 통신, 배관
구현 방법
1. Kryskal MST 알고리즘
그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됨
즉, 최소 신장 트리를 구하기 위한 알고리즘임
그리디 알고리즘의 일종
1. 그래프 간선의 가중치를 오름차순 정렬
2. 차례대로 선택하다가 사이클을 형성하면 선택하지 않음
3. 선택된 간선의 갯수가 정점의 갯수-1만큼 되면 종료함
코딩 시 사이클 판단 시
Union & Find 자료구조 사용
-> Disjoint Set(서로소 집합)을 표현하는 자료구조
2. Prim MST 알고리즘
그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용됨
마찬가지로 최소 신장 트리를 구하기 위한 알고리즘임
그리디 알고리즘의 일종
1. 시작 단계는 시작 노드만이 MST 집합에 속함
2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점을 MST 트리 집합에 넣음
3. 선택된 간선의 갯수가 정점의 갯수-1만큼 될때까지 반복
코딩
집합 내 정점들을 순회하면서 우선순위 큐에 삽입한 뒤 pop하여 구현
최소 신장 트리에 대해 설명해주세요
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말한다. 즉, 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.
최소 신장 트리의 알고리즘에 대해 설명해주세요
Kruskal과 Prim 알고리즘이 있음. 둘 다 그리디 알고리즘을 베이스로 하고 있음
크루스칼 알고리즘은 간선을 정렬한 후 사이클을 확인하며 연결하는 알고리즘이고, Prim은 시작 정점부터 출발하여 MST 집합을 단계별로 확장해나가는 알고리즘임.
Kruskal 알고리즘에서 사용하는 Union-Find 자료구조에 대해 설명해주세요.
합집합을 찾는 구조이고, 간선에 라벨을 붙여서 라벨이 같다면 같은 그래프에 속하는 것으로 판단하고, 아니라면 다른 그래프에 속하는 것으로 판단하는 알고리즘임.
Kruskal과 Prim 중 어떤 것이 더 빠를까요?
Kruskal은 간선을 정렬한 후 사이클을 확인하며 연결하므로 시간 복잡도는 주로 간선 수에 의해 결정됨. 간선 정렬하는 데에 O(ElogE)가 듦. (각 간선의 사이클 확인은 Union-Find 자료구조를 사용해 상수 시간이 걸림)
Prim은 각 노드마다 가장 작은 가중치의 간선을 선택하므로, 힙을 사용하여 노드와 연결된 간선을 관리함. 초기에 모든 노드를 힙에 넣는 데 O(Vlog V) 시간이 들고, 간선을 추가하고 최소 가중치를 찾는 과정에서 O(Elog V)가 소요됨
그래프 내의 간선이 많은 경우는 Prim이 , 적은 경우에는 Kruskal이 빠름
출처 : https://mangkyu.tistory.com/90
https://chanhuiseok.github.io/posts/algo-33/
https://velog.io/@dbghwns11/CS-정리-4
