탐욕 알고리즘
현재 상황에서 가장 좋아보이는 답을 선택하는 방법.
상황마다 최적을 선택하면 전체 결과값도 최적이 될것이라는 가정을 전제로 함.
① 각 단계에 도달할 때 마다, 최적의 결과를 도출한다.
② 결과를 저장한다.
③ 이미 저장한 결과는 다시 판단하지 않는다.
탐욕 알고리즘이 적용된 알고리즘들
- 선택정렬 Selection Sort
- 배낭문제 Knapsack Problem
- 단일 출발지 최단 경로 문제 Single-Source Shortest Path Proble,
- 최소 신장 트리 Minimum Spanning Tree
- 프림 최소 신장 트리 알고리즘 Prim's Minimum Spanning Tree Algorithm
- 쿠스칼 최소 신장 트리 알고리즘 Kruskal's Minimum Spanning Tree Algorithm
- 다익스트라 최소 신장 트리 알고리즘 Dijkstra's Minimum Spanning Tree Algorithm
- 허프만 코딩 Huffman Coding
- 포드 풀커슨 알고리즘 Ford-Fulkerson Algorithm
예시 : 동전 고르기
Q : 500원, 100원, 50원, 10원짜리 동전이 있다. 4종류의 동전을 이용하여 1800원을 만들 때, 최소 동전의 갯수는 얼마인가?
A : 값이 가장 큰 동전 순서로 1800원을 만든다.
가장 값이 큰 동전을 최대한 사용했을 때, 총 동전의 갯수는 최소가 된다.
① 가장 큰 500원 동전을 3개 사용한다.
② 두번째로 큰 100원 동전을 3개 사용한다.
③ 최소 동전의 갯수는 6개이다. (500원 3개, 100원 3개)
예시 : 최소 신장 트리 Minimum Spanning Tree
신장트리 Spanning Tree : 가중치가 있는 무방향성 그래프의 모든 정점을 연결하는 간선의 집합
최소 신장 트리 Minimum Spanning Tree : 신장 트리 중 최소 비용을 가진 것
① 시작점에서 최소비용인 간선을 하나 추가한다.
② ①에서 추가된 간선에 의해 순환이 생기는지 체크한다.
프림 알고리즘 Prim's Algorithm
매 단계마다 가중치 최소값인 간선을 추가하여 최소 신장 트리를 구하는 알고리즘
① 현재 정점과 이어진 모든 간선을 중 최소값을 구한다.
② ①에서 구해진 최소값을 결과에 추가한다.
③ 모든 정점을 연결할때까지 ①과②를 반복한다.
구현 JAVA
package test;
import java.util.Arrays;
public class Prim {
public static void main(String[] args) {
//인접행렬로 구현한 그래프
int[][] graph = {{0,2, 3 , 1, 0},
{2, 0, 7, 0, 4},
{3, 7, 0, 0, 5},
{1, 0, 0, 0, 6},
{0, 4, 5, 6, 0}};
//최소 신장 트리 결과값
int[] spanningTree = new int[graph.length-1];
// 프림 알고리즘 수행
Prim f = new Prim();
f.prim(graph, spanningTree);
System.out.println("최소 신장 트리 결과값");
System.out.println("최소 신장 트리 리스트 : " + Arrays.toString(spanningTree));
System.out.println("최소 신장 트리 비용 : "
+ Arrays.stream(spanningTree).sum());
}
void prim(int[][] graph, int[] spanningTree) {
//정점의 방문여부를 저장할 배열
boolean[] isVisited = new boolean[graph.length];
//시작점 지정 : 방문여부 True
isVisited[0] = true;
//최소신장트리 갯수
int spanningTreeCount=0;
//정점를 모두 연결하는 엣지의 갯수 = 노드갯수 - 1
//정점의 갯수 : graph.length
//최소신장트리로 저장된 엣지의 갯수 : spanningTreeCount
//저장된 엣지의 갯수가 노드갯수-1 개일 때까지 탐색 수행
while(spanningTreeCount < graph.length-1) {
int visitedNode = Integer.MIN_VALUE; //최소값 엣지와 연결된 정점
int minWeight = Integer.MAX_VALUE; //엣지 최소 가중치
// 방문여부가 true인 정점을 찾기
for(int i = 0; i < graph.length; i++) {
if(isVisited[i]) {
for(int j = 0; j < graph.length; j++) {
//정점 j가 정점 i와 연결되어 있고 (엣지가 있고, 가중치 > 0)
//정점 j의 방문여부가 false인 (방문한 적이 없는) 것들을 탐색
if(graph[i][j]>0 && !isVisited[j]) {
//탐색한 엣지 중 최소값을 찾기
if(minWeight > graph[i][j]) {
minWeight = graph[i][j];
visitedNode = j;
}
}
}
}
}
//최소신장트리 결과값 저장
spanningTree[spanningTreeCount] = minWeight;
spanningTreeCount++;
isVisited[visitedNode] = true;
}
}
}최소 신장 트리 결과값
최소 신장 트리 리스트 : [1, 2, 3, 4]
최소 신장 트리 비용 : 10
쿠루스칼 알고리즘 Kruskal's Algorithm
① 모든 엣지를 가중치가 작은 값 순으로 정렬한다.
② 가장 작은 엣지부터 최소신장트리(결과값)에 저장한다. 만약 순환이 발생하면 저장하지 않는다.
* 순환 판별 방법
1) 각 노드가 속한 그룹의 부모노드를 저장할 배열을 선언하고 값 자기자신으로 초기화한다.
2) 최소신장트리를 저장하면서 현재 노드가 속한 그룹의 부모노드값을 저장한다.
(부모노드 : 현재 노드가 속한 엣지집합의 반대편 끝 노드)
3) 현재 엣지의 Source 노드와 Target 노드의 부모노드 값이 같다면 엣지를 최소신장트리에 추가하지 않는다.
* 부모노드 값이 같다면, 이미 같은 그룹에 속한 것인데, 두 노드를 연결하면 순환이 발생하게 된다.
③ 모든 정점을 탐색할 때까지 ②를 반복한다.
구현 JAVA
package test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Kruskal {
static int[] parents;//부모노드
static Edge[] spanningTree; //최소신장트리
public static void main(String[] args) {
Kruskal f = new Kruskal();
//그래프 선언
List<Edge> graph = new ArrayList<>();
graph.add(f.new Edge(0, 1, 2));
graph.add(f.new Edge(0, 2, 3));
graph.add(f.new Edge(0, 3, 1));
graph.add(f.new Edge(1, 0, 2));
graph.add(f.new Edge(1, 2, 7));
graph.add(f.new Edge(1, 4, 4));
graph.add(f.new Edge(2, 0, 3));
graph.add(f.new Edge(2, 1, 7));
graph.add(f.new Edge(2, 4, 5));
graph.add(f.new Edge(3, 0, 1));
graph.add(f.new Edge(3, 4, 6));
graph.add(f.new Edge(4, 1, 4));
graph.add(f.new Edge(4, 2, 5));
graph.add(f.new Edge(4, 3, 6));
//쿠루스칼 알고리즘 수행
f.kruskal(graph, 5);
//결과값 출력
for(Edge edge : spanningTree) {
System.out.println(edge.toString());
}
}
void kruskal(List<Edge> graph, int nodeCount) {
//초기화
//저장된 최소신장트리 간선의 갯수
int spanningTreeCount = 0;
spanningTree = new Edge[nodeCount-1];
parents = new int[nodeCount];
for(int i = 0; i<nodeCount; i++) {
parents[i] = i; //부모노드를 저장할 배열
}
// 가중치가 작은 순으로 정렬
Collections.sort(graph);
//엣지 source와 target 노드의 부모노드 값이 다르면 최소신장트리에 값을 추가
for(Edge edge : graph) {
if(findParent(edge.getSource()) != findParent(edge.getTarget())) {
parents[edge.getTarget()] = findParent(edge.getSource());
spanningTree[spanningTreeCount++] = edge;
}
}
}
/**
* 노드의 부모노드를 찾는 함수
* @param source
* @return
*
* ①정점 번호와 부모노드 값이 같으면 최상위 부모노드
* ②정점 번호와 부모노드 값이 다르면 하위노드
* 최상위 부모노드를 찾도록 재귀 호출
*/
private int findParent(int source) {
if(parents[source] == source) {
return parents[source];
}else {
return findParent(parents[source]);
}
}
class Edge implements Comparable<Edge>{
int source;
int target;
int weight;
Edge(int source, int target, int weight){
this.source = source;
this.target = target;
this.weight = weight;
}
public int getSource() {
return source;
}
public void setSource(int source) {
this.source = source;
}
public int getTarget() {
return target;
}
public void setTarget(int target) {
this.target = target;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public int compareTo(Edge edge) {
return this.weight - edge.weight;
}
@Override
public String toString() {
return "Edge [source=" + source + ", target=" + target + ", weight=" + weight + "]";
}
};
}Edge [source=0, target=3, weight=1]
Edge [source=0, target=1, weight=2]
Edge [source=0, target=2, weight=3]
Edge [source=1, target=4, weight=4]
출처
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 힙 정렬 Heap Sort (0) | 2021.09.21 |
|---|---|
| 퀵 정렬 Quick Sort (0) | 2021.09.21 |
| 플로이드-와샬 알고리즘 Floyd-Warshall Algorithm (0) | 2021.09.20 |
| 벨만-포드 알고리즘 Bellman Ford's Algorithm (0) | 2021.09.20 |
| 다익스트라 알고리즘 Dijkstra's algorithm (0) | 2021.09.19 |