7. 그리디 알고리즘
7.1 그리디 알고리즘의 개념
그리디 알고리즘(Greedy Algorithm)
그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복적으로 해 나가면서 최적해를 찾아가는 알고리즘입니다. 이 알고리즘은 각 단계에서 최선의 선택을 하는 것이 전체 문제에 대한 최적해를 보장한다는 전제하에 작동합니다.
그리디 알고리즘의 시간 복잡도는 일반적으로 문제의 구조에 따라 달라집니다. 예를 들어, 선택 정렬은 \(O(n^2)\)의 시간 복잡도를 가지지만, 동전 교환 문제는 \(O(n)\) 또는 \(O(\log n)\)의 시간 복잡도를 가질 수 있습니다.
그리디 알고리즘은 주로 최단 경로, 최소 신장 트리, 작업 스케줄링 문제 등에서 많이 사용됩니다.
그리디 알고리즘의 역사는 1950년대와 1960년대에 도입되었으며, 대표적인 예로 다익스트라(Dijkstra) 알고리즘과 크루스칼(Kruskal) 알고리즘이 있습니다. 이 알고리즘들은 네트워크 최적화와 그래프 이론에서 중요한 역할을 합니다.
왜 그리디 알고리즘이 생겨났는가?
그리디 알고리즘은 특정 문제들이 복잡한 전체 문제를 해결하지 않고도, 각 단계에서의 최선의 선택만으로도 충분히 좋은 결과를 얻을 수 있는 경우가 많기 때문에 개발되었습니다. 즉, 복잡한 문제를 더 단순하게 해결할 수 있는 방법을 제공하는 것이 그리디 알고리즘의 핵심입니다. 이러한 접근법은 많은 실제 문제에 적용할 수 있어 실용적인 가치를 가지고 있습니다.
// 거스름돈 문제 - 그리디 알고리즘 예시
import java.util.Arrays;
public class CoinChange {
/**
* 주어진 금액을 최소 동전 개수로 만들기 위한 그리디 알고리즘
*
* @param coins 사용 가능한 동전의 종류
* @param amount 거스름돈 금액
* @return 각 동전의 사용 개수 배열
*/
public static int[] coinChange(int[] coins, int amount) {
Arrays.sort(coins); // 동전 배열을 오름차순으로 정렬
int[] result = new int[coins.length]; // 각 동전의 개수를 저장할 배열
int index = coins.length - 1; // 가장 큰 동전부터 사용
while (amount > 0) {
if (coins[index] <= amount) {
result[index] = amount / coins[index]; // 현재 동전으로 만들 수 있는 최대 개수
amount -= result[index] * coins[index]; // 남은 금액 계산
}
index--; // 다음 동전으로 이동
}
return result;
}
public static void main(String[] args) {
int[] coins = {1, 5, 10, 25}; // 동전 종류
int amount = 63; // 거스름돈 금액
int[] result = coinChange(coins, amount); // 그리디 알고리즘 실행
System.out.println("Coins used to make change for " + amount + ":");
for (int i = 0; i < result.length; i++) {
if (result[i] != 0) {
System.out.println(coins[i] + "¢ coin: " + result[i] + "개");
}
}
}
}
이 코드에서 우리는 그리디 알고리즘을 사용하여 최소한의 동전 개수로 거스름돈을 만드는 문제를 해결합니다. 큰 동전부터 사용하여 남은 금액을 줄여 나가는 방식입니다. 각 단계에서 가장 큰 동전을 사용하여 남은 금액을 줄이는 것이 최적의 결과를 보장합니다.
7.2 대표적인 그리디 알고리즘 문제
대표적인 그리디 알고리즘 문제
그리디 알고리즘은 여러 문제에 적용될 수 있습니다. 대표적인 문제로는 동전 교환 문제, 활동 선택 문제, 최소 신장 트리(MST) 문제 등이 있습니다.
그리디 알고리즘은 매 단계에서 지역적으로 최적의 선택을 하지만, 이는 전체적으로 최적의 해결책을 보장하지 않을 수 있습니다. 따라서 그리디 알고리즘이 모든 문제에 적용 가능한 것은 아니며, 문제의 특성에 따라 적용 여부를 결정해야 합니다.
아래는 활동 선택 문제의 예시입니다. 활동 선택 문제는 최대한 많은 활동을 선택하는 문제입니다.
// 활동 선택 문제 예시
import java.util.*;
class Activity implements Comparable {
int start, end;
public Activity(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Activity other) {
return this.end - other.end; // 종료 시간을 기준으로 정렬
}
}
public class ActivitySelection {
/**
* 주어진 활동 목록에서 최대한 많은 활동을 선택하는 그리디 알고리즘
*
* @param activities 활동 목록
* @return 선택된 활동 목록
*/
public static List selectActivities(List activities) {
Collections.sort(activities); // 활동을 종료 시간 기준으로 정렬
List result = new ArrayList<>();
result.add(activities.get(0)); // 첫 번째 활동 선택
int lastEndTime = activities.get(0).end; // 마지막 선택된 활동의 종료 시간 초기화
for (int i = 1; i < activities.size(); i++) {
if (activities.get(i).start >= lastEndTime) {
result.add(activities.get(i)); // 현재 활동의 시작 시간이 마지막 선택된 활동의 종료 시간보다 늦으면 선택
lastEndTime = activities.get(i).end; // 마지막 선택된 활동의 종료 시간 업데이트
}
}
return result;
}
public static void main(String[] args) {
List activities = Arrays.asList(
new Activity(1, 3),
new Activity(2, 4),
new Activity(3, 5),
new Activity(0, 6),
new Activity(5, 7),
new Activity(8, 9),
new Activity(5, 9)
);
List selectedActivities = selectActivities(activities); // 그리디 알고리즘 실행
System.out.println("Selected activities:");
for (Activity activity : selectedActivities) {
System.out.println("Activity: (" + activity.start + ", " + activity.end + ")");
}
}
}
이 코드에서 우리는 그리디 알고리즘을 사용하여 최대한 많은 활동을 선택하는 문제를 해결합니다. 활동을 종료 시간 기준으로 정렬한 후, 시작 시간이 마지막으로 선택된 활동의 종료 시간보다 늦은 활동을 선택합니다. 이 과정에서 각 단계에서 최선의 선택을 하여 최종적으로 최대의 활동을 선택할 수 있습니다.
예시 문제 추가
아래는 추가적인 그리디 알고리즘 문제 예시입니다.
1. 배낭 문제 (Fractional Knapsack Problem)
배낭 문제는 제한된 무게 내에서 최대 가치를 얻을 수 있도록 물건을 선택하는 문제입니다. 그리디 알고리즘을 사용하여 가치 대비 무게가 높은 물건부터 배낭에 넣습니다.
// 배낭 문제 (Fractional Knapsack) 예시
import java.util.Arrays;
import java.util.Comparator;
class Item {
int value, weight;
Item(int value, int weight) {
this.value = value;
this.weight = weight;
}
}
public class FractionalKnapsack {
/**
* 주어진 물건들로 배낭을 채워 최대 가치를 얻기 위한 그리디 알고리즘
*
* @param W 배낭의 최대 무게
* @param arr 물건 배열
* @return 최대 가치
*/
public static double getMaxValue(int W, Item[] arr) {
Arrays.sort(arr, new Comparator() {
@Override
public int compare(Item o1, Item o2) {
double r1 = (double) o1.value / o1.weight;
double r2 = (double) o2.value / o2.weight;
return Double.compare(r2, r1); // 가치 대비 무게 비율로 정렬
}
});
double totalValue = 0.0;
for (Item item : arr) {
if (W == 0)
break;
if (item.weight <= W) {
W -= item.weight;
totalValue += item.value;
} else {
// 남은 배낭 용량에 맞춰 부분적으로 물건을 넣음
totalValue += item.value * ((double) W / item.weight);
W = 0;
}
}
return totalValue; // 최대 가치 반환
}
public static void main(String[] args) {
Item[] arr = {new Item(60, 10), new Item(100, 20), new Item(120, 30)}; // 물건 배열
int W = 50; // 배낭의 최대 무게
double maxValue = getMaxValue(W, arr); // 그리디 알고리즘 실행
System.out.println("Maximum value we can obtain = " + maxValue);
}
}
이 코드에서 우리는 배낭 문제를 해결하기 위해 그리디 알고리즘을 사용합니다. 물건을 가치 대비 무게 비율로 정렬한 후, 배낭의 용량이 허용하는 한 최대한의 가치를 얻을 수 있는 물건을 선택합니다.
2. 회의실 배정 문제 (Meeting Room Allocation)
회의실 배정 문제는 여러 회의의 시작 및 종료 시간이 주어졌을 때, 회의실을 최대한 효율적으로 사용하여 가장 많은 회의를 배정하는 문제입니다.
// 회의실 배정 문제 예시
import java.util.*;
class Meeting implements Comparable {
int start, end;
public Meeting(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Meeting other) {
return this.end - other.end; // 종료 시간을 기준으로 정렬
}
}
public class MeetingRoomAllocation {
/**
* 주어진 회의 목록에서 최대한 많은 회의를 배정하기 위한 그리디 알고리즘
*
* @param meetings 회의 목록
* @return 배정된 회의 목록
*/
public static List allocateMeetings(List meetings) {
Collections.sort(meetings); // 회의를 종료 시간 기준으로 정렬
List result = new ArrayList<>();
result.add(meetings.get(0)); // 첫 번째 회의 선택
int lastEndTime = meetings.get(0).end; // 마지막 선택된 회의의 종료 시간 초기화
for (int i = 1; i < meetings.size(); i++) {
if (meetings.get(i).start >= lastEndTime) {
result.add(meetings.get(i)); // 현재 회의의 시작 시간이 마지막 선택된 회의의 종료 시간보다 늦으면 선택
lastEndTime = meetings.get(i).end; // 마지막 선택된 회의의 종료 시간 업데이트
}
}
return result;
}
public static void main(String[] args) {
List meetings = Arrays.asList(
new Meeting(1, 3),
new Meeting(2, 4),
new Meeting(3, 5),
new Meeting(0, 6),
new Meeting(5, 7),
new Meeting(8, 9),
new Meeting(5, 9)
);
List selectedMeetings = allocateMeetings(meetings); // 그리디 알고리즘 실행
System.out.println("Selected meetings:");
for (Meeting meeting : selectedMeetings) {
System.out.println("Meeting: (" + meeting.start + ", " + meeting.end + ")");
}
}
}
이 코드에서 우리는 회의실 배정 문제를 해결하기 위해 그리디 알고리즘을 사용합니다. 회의를 종료 시간 기준으로 정렬한 후, 시작 시간이 마지막으로 선택된 회의의 종료 시간보다 늦은 회의를 선택합니다.
3. 최소 신장 트리 (Minimum Spanning Tree) - 크루스칼 알고리즘
최소 신장 트리 문제는 그래프에서 모든 정점을 연결하는 최소 비용의 트리를 찾는 문제입니다. 크루스칼 알고리즘은 그리디 알고리즘을 사용하여 최소 신장 트리를 찾습니다.
// 크루스칼 알고리즘 예시
import java.util.*;
class Edge implements Comparable {
int src, dest, weight;
public Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight; // 가중치를 기준으로 정렬
}
}
class Graph {
int V, E;
Edge[] edges;
public Graph(int V, int E) {
this.V = V;
this.E = E;
edges = new Edge[E];
}
public void addEdge(int i, int src, int dest, int weight) {
edges[i] = new Edge(src, dest, weight);
}
public int find(int[] parent, int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
public void union(int[] parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
public void kruskalMST() {
Arrays.sort(edges); // 모든 간선을 가중치 기준으로 정렬
int[] parent = new int[V];
Arrays.fill(parent, -1);
ArrayList result = new ArrayList<>();
for (Edge edge : edges) {
int x = find(parent, edge.src);
int y = find(parent, edge.dest);
if (x != y) {
result.add(edge);
union(parent, x, y);
}
}
System.out.println("Edges in the constructed MST:");
for (Edge edge : result) {
System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
}
}
}
public class KruskalAlgorithm {
public static void main(String[] args) {
int V = 4; // 그래프의 정점 수
int E = 5; // 그래프의 간선 수
Graph graph = new Graph(V, E);
graph.addEdge(0, 0, 1, 10);
graph.addEdge(1, 0, 2, 6);
graph.addEdge(2, 0, 3, 5);
graph.addEdge(3, 1, 3, 15);
graph.addEdge(4, 2, 3, 4);
graph.kruskalMST(); // 크루스칼 알고리즘 실행
}
}
이 코드에서 우리는 크루스칼 알고리즘을 사용하여 그래프에서 최소 신장 트리를 찾습니다. 모든 간선을 가중치 기준으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 최소 신장 트리를 구성합니다.
'IT 강좌(IT Lectures) > 알고리즘(Algorithm)' 카테고리의 다른 글
| 10강. 고급 주제 (0) | 2024.07.13 |
|---|---|
| 9강. 문자열 알고리즘 (0) | 2024.07.12 |
| 6강. 동적 계획법과 분할 정복 (0) | 2024.07.09 |
| 5강. 고급 데이터 구조 (0) | 2024.07.08 |
| 4강. 검색알고리즘 (0) | 2024.07.07 |