Greedy
1. Activity Selection (활동 선택 문제)
문제: 주어진 활동 중 서로 겹치지 않는 최대 개수의 활동을 선택합니다.
아이디어: 종료 시간이 빠른 활동을 먼저 선택하는 것이 최적입니다.
class Activity {
int start, finish;
Activity(int start, int finish) {
this.start = start;
this.finish = finish;
}
}
void activitySelection(List<Activity> activities) {
// 종료 시간을 기준으로 활동 정렬
activities.sort((a, b) -> a.finish - b.finish);
// 첫 번째 활동 선택
int lastFinishTime = activities.get(0).finish;
System.out.println("Selected Activity: " + activities.get(0).start + " - " + activities.get(0).finish);
// 각 활동을 확인하면서 종료 시간이 겹치지 않는 활동 선택
for (int i = 1; i < activities.size(); i++) {
if (activities.get(i).start >= lastFinishTime) {
System.out.println("Selected Activity: " + activities.get(i).start + " - " + activities.get(i).finish);
lastFinishTime = activities.get(i).finish;
}
}
}2. Fractional Knapsack (부분 배낭 문제)
문제: 주어진 배낭에 최대한 많은 가치를 담으면서 무게 제한을 넘지 않도록 합니다.
아이디어: 가치 대비 무게 비율이 높은 물건을 우선적으로 담습니다.
class Item {
int weight;
int value;
Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
void fractionalKnapsack(int capacity, List<Item> items) {
// 가치 대비 무게 비율을 기준으로 아이템 정렬
items.sort((a, b) -> Double.compare((double) b.value / b.weight, (double) a.value / a.weight));
double totalValue = 0;
for (Item item : items) {
if (capacity > 0 && item.weight <= capacity) {
// 물건을 배낭에 전부 담을 수 있는 경우
capacity -= item.weight;
totalValue += item.value;
} else {
// 물건을 부분적으로 담아야 하는 경우
totalValue += item.value * ((double) capacity / item.weight);
break;
}
}
System.out.println("Maximum value we can obtain: " + totalValue);
}3. 최소 동전 문제 (Coin Change Problem, 최소 개수)
문제: 주어진 금액을 만들기 위해 최소한의 동전을 사용하는 방법을 찾습니다.
아이디어: 큰 동전부터 사용하여 금액을 채웁니다.
void coinChange(int[] coins, int amount) {
Arrays.sort(coins); // 동전을 오름차순으로 정렬
int count = 0;
for (int i = coins.length - 1; i >= 0; i--) {
if (amount == 0) break;
if (coins[i] <= amount) {
count += amount / coins[i]; // 현재 동전으로 만들 수 있는 금액
amount %= coins[i]; // 남은 금액
}
}
if (amount > 0) {
System.out.println("Cannot make the amount with given coins.");
} else {
System.out.println("Minimum coins required: " + count);
}
}4. 회의실 배정 문제
문제: 여러 회의가 있을 때, 하나의 회의실에서 가장 많은 회의를 진행할 수 있도록 회의를 선택합니다.
아이디어: 종료 시간이 가장 빠른 회의를 먼저 선택합니다.
class Meeting {
int start, end;
Meeting(int start, int end) {
this.start = start;
this.end = end;
}
}
void meetingRoomAllocation(List<Meeting> meetings) {
meetings.sort((a, b) -> a.end - b.end); // 종료 시간을 기준으로 정렬
int lastEndTime = -1;
int count = 0;
for (Meeting meeting : meetings) {
if (meeting.start >= lastEndTime) {
lastEndTime = meeting.end;
count++;
}
}
System.out.println("Maximum number of meetings: " + count);
}5. Job Scheduling Problem (작업 스케줄링 문제)
문제: 각 작업은 특정 시간이 지나면 수행할 수 없으며, 작업이 주어진 기한 내에 완료될 때 보상을 받습니다. 최대 보상을 받는 스케줄을 선택합니다.
아이디어: 보상이 높은 작업을 우선적으로 기한 내에 배치합니다.
class Job {
int deadline, profit;
Job(int deadline, int profit) {
this.deadline = deadline;
this.profit = profit;
}
}
void jobScheduling(List<Job> jobs, int maxDeadline) {
jobs.sort((a, b) -> b.profit - a.profit); // 보상을 기준으로 정렬
boolean[] slots = new boolean[maxDeadline];
int totalProfit = 0;
for (Job job : jobs) {
for (int j = Math.min(maxDeadline - 1, job.deadline - 1); j >= 0; j--) {
if (!slots[j]) {
slots[j] = true;
totalProfit += job.profit;
break;
}
}
}
System.out.println("Maximum profit: " + totalProfit);
}6. 최소 신장 트리 (Kruskal's Algorithm)
문제: 주어진 그래프에서 최소 신장 트리를 구합니다.
아이디어: 간선의 가중치가 낮은 순서대로 추가하면서 사이클이 생기지 않도록 합니다.
class Edge {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
class UnionFind {
int[] parent, rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int u) {
if (parent[u] != u) parent[u] = find(parent[u]);
return parent[u];
}
void union(int u, int v) {
int rootU = find(u);
int rootV = find(v);
if (rootU != rootV) {
if (rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
} else if (rank[rootU] < rank[rootV]) {
parent[rootU] = rootV;
} else {
parent[rootV] = rootU;
rank[rootU]++;
}
}
}
}
void kruskalMST(List<Edge> edges, int vertices) {
edges.sort((a, b) -> a.weight - b.weight);
UnionFind uf = new UnionFind(vertices);
int mstWeight = 0;
List<Edge> mst = new ArrayList<>();
for (Edge edge : edges) {
if (uf.find(edge.src) != uf.find(edge.dest)) {
uf.union(edge.src, edge.dest);
mst.add(edge);
mstWeight += edge.weight;
}
}
System.out.println("Total weight of MST: " + mstWeight);
}Last updated