그리디 알고리즘
그리디 알고리즘의 개념
- 각 단계에서 최적이라고 생각되는 것을 선택하는 알고리즘
- 결정을 해야 할 때마다 미래에 대한 생각없이 그 순간에 가장 최선의 선택을 함
- 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달
- 근사적인 방법
- 항상 최적의 값을 보장하는 것이 아님
그리디 알고리즘 방법
- 문제의 최적해 구조를 결저
- 현재 상테에서으 문제의 구조에 맞는 최적의 해답 선택 절차를 정의 (선택 절차)
- 선택 절차에 따라 선택을 수행
- 선택된 해가 문제의 조건을 만족하는지 검사 (적절성 검사)
- 조건을 만족하지 않으면 해당 해를 제외
- 모든 선택이 완료되면 해답을 검사 (해답 검사)
- 조건을 만족하지 않으면 해답으로 인정 안하고 선택 절차로 돌아가 반복
그리디 알고리즘 조건
- 탐욕스러운 선택 조건
- 탐욕적인 선택이 항상 최적해를 보장해야 함
- 이전의 선택이 이후의 선택에 영향을 주지 않아야 함
- 최적 부분 구조 조건
- 전체 문제가 여러 부분 문제로 분할되며 이 단계마다 최적해가 도출되어야 함
- 전체 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 함
그리디 알고리즘의 종류
1. Prime
- N개의 노드에 대한 최소 신장 트리 (MST)를 찾는다
- 최적해를 보장하는 드문 예
- 정점 중심
- 시작 정점에서 인접한 정점 중 최소 비용으로 선택 가능한 정점을 선택하고 선택된 정점들 중 다시 최소 비용을 찾아 모든 정점이 선택될 때까지 반복
public class Prime {
static boolean visit[];
static final int MAX_VALUE = 100; //무한대를 편의상 100으로 설정했음
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int weightSum = 0; // 가중치 합
int count = 0; // Prim은 정점을 기준으로 하기 때문에 선택된 정점 갯수
int V, E; // 정점과 간선
int D[]; // 최소 거리 담는 배열
System.out.print("정점의 개수 : ");
V = sc.nextInt(); // 정점의 개수
System.out.print("간선의 개수 : ");
E = sc.nextInt(); // 간선의 개수
// 방문 배열
visit = new boolean[V];
// 입력받은 간선 개수만큼 가중치를 입력받기 위한 배열 생성
int graph[][] = new int[V][V];
// 간선과 가중치 입력받음
// 인접행렬 구성
for (int i = 0; i < E; i++) {
System.out.print("정점1 정점2 가중치 : ");
int v1 = sc.nextInt() - 1;
int v2 = sc.nextInt() - 1;
int w = sc.nextInt();
graph[v1][v2] = w;
graph[v2][v1] = w;
}
D = new int[V]; // 선택된 정점들로부터 가능한 최소거리 저장 배열
Arrays.fill(D,MAX_VALUE); // 아직 거리를 모르므로 최대값으로 설정
D[0] = 0; // 첫 번째 정점은 거리가 0
while(true) {
int min = MAX_VALUE; // 비교할 최소값을 처음에 무한대(이 코드에선 100)로 설정
int index = 0; //인덱스 저장 변수
for(int i =0; i < V; i++) {
if( !visit[i] && (D[i] < min) ) {
min=D[i]; //최소값 바꿔줌
index = i;
}
}
visit[index]=true; // 선택된 정점은 방문했다고 바꿈
weightSum += min; // 가중치 더해짐
System.out.println((index+1)+"정점 방문(거리 : "+D[index]+", 총합 : "+weightSum+")");
count++; // 선택된 정점 개수 증가
if(count == V) {
break; //선택된 정점의 갯수가 정점갯수와 같아지면 종료
}
// 선택된 정점을 포함하여 다른 정점의 간선정보를 갱신
for(int i = 0; i < V ; i++) {
//i정점을 방문하지 않았고, index 정점에서 i정점까지 의 거리가 저장된 최소값보다 작고
//i정점과 index 정점이 연결되어 있으면
if(!visit[i] && (graph[index][i] < D[i]) && graph[index][i] > 0 ) {
D[i] = graph[index][i]; // index 노드와 i 노드의 가중치를 최소값으로 설정
}
}
}
System.out.println("간선의 총합 : " + weightSum);
}
}
// 출처 : https://kimansu.medium.com/6-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B3%B5%EB%B6%80-prim-algorithm-with-java-ddf235600aeb
2. Kruskal
- N개의 노드에 대한 최소 신장 트리 (MST)를 찾는다
- 그래프의 간선들을 가중치의 오름차순으로 정렬
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
- 해당 간선을 현재의 MST의 집합에 추가
- 간선 선택을 기반
public class Kruskal {
static int V, E;
static int[][] graph;
// 각 노드의 부모
static int[] parent;
// 최종적으로 연결된 최소 신장 트리 연결 비용
static int final_cost;
public static void main(String[] args) {
// 그래프의 연결상태(노드1, 노드2, 비용)를 초기화
Scanner sc = new Scanner(System.in);
V = sc.nextInt();
E = sc.nextInt();
graph = new int[E][3];
for (int i = 0; i < E; i++) {
graph[i][0] = sc.nextInt();
graph[i][1] = sc.nextInt();
graph[i][2] = sc.nextInt();
}
parent = new int[V];
final_cost = 0;
// 간선 비용 순으로 오름차순 정렬
Arrays.sort(graph, (o1, o2) -> Integer.compare(o1[2], o2[2]));
// makeSet
for (int i = 0; i < V; i++) {
parent[i] = i;
}
// 낮은 비용부터 크루스칼 알고리즘 진행
for (int i = 0; i < E; i++) {
// 사이클이 존재하지 않는 경우에만 간선을 선택한다(여기서는 최종 비용만 고려)
if (find(graph[i][0] - 1) != find(graph[i][1] - 1)) {
System.out.println("<선택된 간선>");
System.out.println(Arrays.toString(graph[i]));
union(graph[i][0] - 1, graph[i][1] - 1);
final_cost += graph[i][2];
System.out.println("<각 노드가 가리키고 있는 부모>");
System.out.println(Arrays.toString(parent) + "\n");
continue;
}
}
System.out.println("최종 비용 : " + final_cost);
sc.close();
}
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (a > b) {
parent[a] = b;
} else {
parent[b] = a;
}
}
private static int find(int x) {
if (parent[x] == x)
return x;
else
return find(parent[x]);
}
}
// 출처 : https://sskl660.tistory.com/72
3. Dijkstra
- 주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다
- 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구함
- 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택
- 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신
// 도착 지점과, 도착지점으로 가는 비용을 의미하는 클래스를 정의
class Node {
int idx;
int cost;
// 생성자
Node(int idx, int cost) {
this.idx = idx;
this.cost = cost;
}
}
public class Dijkstra {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 노드와 간선의 개수
int V = sc.nextInt();
int E = sc.nextInt();
// 출발지점
int start = sc.nextInt();
// 1. 인접리스트를 이용한 그래프 초기화
ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
// 노드의 번호가 1부터 시작하므로, 0번 인덱스 부분을 임의로 만들어 놓기만 한다
for (int i = 0; i < V + 1; i++) {
graph.add(new ArrayList<>());
}
// 그래프에 값을 넣는다.
for (int i = 0; i < E; i++) {
// a로 부터 b로 가는 값은 cost
int a = sc.nextInt();
int b = sc.nextInt();
int cost = sc.nextInt();
graph.get(a).add(new Node(b, cost));
}
// 2. 방문 여부를 확인할 boolean 배열, start 노드부터 end 노드 까지의 최소 거리를 저장할 배열을 만든다
boolean[] visited = new boolean[V + 1];
int[] dist = new int[V + 1];
// 3. 최소 거리 정보를 담을 배열을 초기화
for (int i = 0; i < V + 1; i++) {
// 출발 지점 외 나머지 지점까지의 최소 비용은 최대로 지정
dist[i] = Integer.MAX_VALUE;
}
// 출발 지점의 비용은 0으로 시작
dist[start] = 0;
// 4. 다익스트라 알고리즘을 진행
// 모든 노드을 방문하면 종료하기 때문에, 노드의 개수 만큼만 반복
for (int i = 0; i < V; i++) {
// 4 - 1. 현재 거리 비용 중 최소인 지점을 선택
// 해당 노드가 가지고 있는 현재 비용
int nodeValue = Integer.MAX_VALUE;
// 해당 노드의 인덱스(번호)
int nodeIdx = 0;
// 인덱스 0은 생각하지 않기 때문에 0부터 반복을 진행
for (int j = 1; j < V + 1; j++) {
// 해당 노드를 방문하지 않았고, 현재 모든 거리비용 중 최솟값을 찾는다
if (!visited[j] && dist[j] < nodeValue) {
nodeValue = dist[j];
nodeIdx = j;
}
}
// 최종 선택된 노드를 방문처리
visited[nodeIdx] = true;
// 4 - 2. 해당 지점을 기준으로 인접 노드의 최소 거리 값을 갱신
for (int j = 0; j < graph.get(nodeIdx).size(); j++) {
// 인접 노드를 선택한다.
Node adjNode = graph.get(nodeIdx).get(j);
// 인접 노드가 현재 가지는 최소 비용과
// 현재 선택된 노드의 값 + 현재 노드에서 인접 노드로 가는 값을 비교하여 더 작은 값으로 갱신
if (dist[adjNode.idx] > dist[nodeIdx] + adjNode.cost) {
dist[adjNode.idx] = dist[nodeIdx] + adjNode.cost;
}
}
}
// 5. 최종 비용을 출력
for (int i = 1; i < V + 1; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.println("INF");
} else {
System.out.println(dist[i]);
}
}
sc.close();
}
}
// 출처 : https://sskl660.tistory.com/59