1/*
2 * νμ μκ³ λ¦¬μ¦ (Greedy Algorithm)
3 * Activity Selection, Huffman Coding, Fractional Knapsack
4 *
5 * 맀 μκ° μ΅μ μ μ νμ ν΅ν΄ μ 체 μ΅μ ν΄λ₯Ό ꡬν©λλ€.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11
12/* =============================================================================
13 * 1. νλ μ ν λ¬Έμ
14 * ============================================================================= */
15
16typedef struct {
17 int start;
18 int end;
19} Activity;
20
21int compare_activities(const void* a, const void* b) {
22 return ((Activity*)a)->end - ((Activity*)b)->end;
23}
24
25int activity_selection(Activity activities[], int n) {
26 qsort(activities, n, sizeof(Activity), compare_activities);
27
28 int count = 1;
29 int last_end = activities[0].end;
30
31 for (int i = 1; i < n; i++) {
32 if (activities[i].start >= last_end) {
33 count++;
34 last_end = activities[i].end;
35 }
36 }
37
38 return count;
39}
40
41/* =============================================================================
42 * 2. λΆν κ°λ₯ λ°°λ λ¬Έμ
43 * ============================================================================= */
44
45typedef struct {
46 double value;
47 double weight;
48 double ratio;
49} Item;
50
51int compare_items(const void* a, const void* b) {
52 double r1 = ((Item*)a)->ratio;
53 double r2 = ((Item*)b)->ratio;
54 return (r2 > r1) - (r2 < r1); /* λ΄λ¦Όμ°¨μ */
55}
56
57double fractional_knapsack(Item items[], int n, double capacity) {
58 qsort(items, n, sizeof(Item), compare_items);
59
60 double total_value = 0;
61 double remaining = capacity;
62
63 for (int i = 0; i < n && remaining > 0; i++) {
64 if (items[i].weight <= remaining) {
65 total_value += items[i].value;
66 remaining -= items[i].weight;
67 } else {
68 total_value += items[i].ratio * remaining;
69 remaining = 0;
70 }
71 }
72
73 return total_value;
74}
75
76/* =============================================================================
77 * 3. ννλ§ μ½λ©
78 * ============================================================================= */
79
80typedef struct HuffmanNode {
81 char ch;
82 int freq;
83 struct HuffmanNode* left;
84 struct HuffmanNode* right;
85} HuffmanNode;
86
87HuffmanNode* create_huffman_node(char ch, int freq) {
88 HuffmanNode* node = malloc(sizeof(HuffmanNode));
89 node->ch = ch;
90 node->freq = freq;
91 node->left = node->right = NULL;
92 return node;
93}
94
95/* κ°λ¨ν μ°μ μμ ν (λ°°μ΄ κΈ°λ°) */
96typedef struct {
97 HuffmanNode** data;
98 int size;
99 int capacity;
100} MinHeap;
101
102MinHeap* create_heap(int capacity) {
103 MinHeap* h = malloc(sizeof(MinHeap));
104 h->data = malloc(capacity * sizeof(HuffmanNode*));
105 h->size = 0;
106 h->capacity = capacity;
107 return h;
108}
109
110void heap_insert(MinHeap* h, HuffmanNode* node) {
111 int i = h->size++;
112 h->data[i] = node;
113 while (i > 0 && h->data[(i - 1) / 2]->freq > h->data[i]->freq) {
114 HuffmanNode* temp = h->data[(i - 1) / 2];
115 h->data[(i - 1) / 2] = h->data[i];
116 h->data[i] = temp;
117 i = (i - 1) / 2;
118 }
119}
120
121HuffmanNode* heap_extract(MinHeap* h) {
122 HuffmanNode* min = h->data[0];
123 h->data[0] = h->data[--h->size];
124 int i = 0;
125 while (2 * i + 1 < h->size) {
126 int smallest = i;
127 if (h->data[2 * i + 1]->freq < h->data[smallest]->freq) smallest = 2 * i + 1;
128 if (2 * i + 2 < h->size && h->data[2 * i + 2]->freq < h->data[smallest]->freq) smallest = 2 * i + 2;
129 if (smallest == i) break;
130 HuffmanNode* temp = h->data[i];
131 h->data[i] = h->data[smallest];
132 h->data[smallest] = temp;
133 i = smallest;
134 }
135 return min;
136}
137
138HuffmanNode* build_huffman_tree(char chars[], int freqs[], int n) {
139 MinHeap* heap = create_heap(n);
140 for (int i = 0; i < n; i++) {
141 heap_insert(heap, create_huffman_node(chars[i], freqs[i]));
142 }
143
144 while (heap->size > 1) {
145 HuffmanNode* left = heap_extract(heap);
146 HuffmanNode* right = heap_extract(heap);
147 HuffmanNode* merged = create_huffman_node('\0', left->freq + right->freq);
148 merged->left = left;
149 merged->right = right;
150 heap_insert(heap, merged);
151 }
152
153 HuffmanNode* root = heap_extract(heap);
154 free(heap->data);
155 free(heap);
156 return root;
157}
158
159void print_huffman_codes(HuffmanNode* root, char code[], int depth) {
160 if (!root) return;
161 if (!root->left && !root->right) {
162 code[depth] = '\0';
163 printf(" '%c': %s\n", root->ch, code);
164 return;
165 }
166 code[depth] = '0';
167 print_huffman_codes(root->left, code, depth + 1);
168 code[depth] = '1';
169 print_huffman_codes(root->right, code, depth + 1);
170}
171
172void free_huffman_tree(HuffmanNode* root) {
173 if (!root) return;
174 free_huffman_tree(root->left);
175 free_huffman_tree(root->right);
176 free(root);
177}
178
179/* =============================================================================
180 * 4. λμ κ±°μ€λ¦λ
181 * ============================================================================= */
182
183int coin_change_greedy(int coins[], int n, int amount) {
184 int count = 0;
185 for (int i = n - 1; i >= 0 && amount > 0; i--) {
186 count += amount / coins[i];
187 amount %= coins[i];
188 }
189 return (amount == 0) ? count : -1;
190}
191
192/* =============================================================================
193 * 5. νμμ€ λ°°μ (μ΅μ νμμ€ μ)
194 * ============================================================================= */
195
196typedef struct {
197 int time;
198 int type; /* 1: μμ, -1: μ’
λ£ */
199} Event;
200
201int compare_events(const void* a, const void* b) {
202 Event* e1 = (Event*)a;
203 Event* e2 = (Event*)b;
204 if (e1->time != e2->time) return e1->time - e2->time;
205 return e1->type - e2->type; /* μ’
λ£ λ¨Όμ */
206}
207
208int min_meeting_rooms(int starts[], int ends[], int n) {
209 Event* events = malloc(2 * n * sizeof(Event));
210 for (int i = 0; i < n; i++) {
211 events[2 * i] = (Event){starts[i], 1};
212 events[2 * i + 1] = (Event){ends[i], -1};
213 }
214 qsort(events, 2 * n, sizeof(Event), compare_events);
215
216 int max_rooms = 0, current = 0;
217 for (int i = 0; i < 2 * n; i++) {
218 current += events[i].type;
219 if (current > max_rooms) max_rooms = current;
220 }
221 free(events);
222 return max_rooms;
223}
224
225/* =============================================================================
226 * 6. μ ν κ²μ
227 * ============================================================================= */
228
229int can_jump(int nums[], int n) {
230 int max_reach = 0;
231 for (int i = 0; i < n; i++) {
232 if (i > max_reach) return 0;
233 if (i + nums[i] > max_reach) max_reach = i + nums[i];
234 }
235 return 1;
236}
237
238int min_jumps(int nums[], int n) {
239 if (n <= 1) return 0;
240 int jumps = 0, current_end = 0, farthest = 0;
241 for (int i = 0; i < n - 1; i++) {
242 if (i + nums[i] > farthest) farthest = i + nums[i];
243 if (i == current_end) {
244 jumps++;
245 current_end = farthest;
246 if (current_end >= n - 1) break;
247 }
248 }
249 return jumps;
250}
251
252/* =============================================================================
253 * ν
μ€νΈ
254 * ============================================================================= */
255
256int main(void) {
257 printf("============================================================\n");
258 printf("νμ μκ³ λ¦¬μ¦ (Greedy) μμ \n");
259 printf("============================================================\n");
260
261 /* 1. νλ μ ν */
262 printf("\n[1] νλ μ ν λ¬Έμ \n");
263 Activity activities[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}};
264 printf(" μ΅λ νλ μ: %d\n", activity_selection(activities, 6));
265
266 /* 2. λΆν λ°°λ */
267 printf("\n[2] λΆν κ°λ₯ λ°°λ\n");
268 Item items[] = {{60, 10, 6}, {100, 20, 5}, {120, 30, 4}};
269 printf(" μ©λ 50μ μ΅λ κ°μΉ: %.2f\n", fractional_knapsack(items, 3, 50));
270
271 /* 3. ννλ§ μ½λ© */
272 printf("\n[3] ννλ§ μ½λ©\n");
273 char chars[] = {'a', 'b', 'c', 'd', 'e'};
274 int freqs[] = {5, 9, 12, 13, 16};
275 HuffmanNode* root = build_huffman_tree(chars, freqs, 5);
276 printf(" μ½λ:\n");
277 char code[100];
278 print_huffman_codes(root, code, 0);
279 free_huffman_tree(root);
280
281 /* 4. λμ κ±°μ€λ¦λ */
282 printf("\n[4] λμ κ±°μ€λ¦λ\n");
283 int coins[] = {1, 5, 10, 50, 100, 500};
284 printf(" λμ [1,5,10,50,100,500], κΈμ‘ 730\n");
285 printf(" μ΅μ λμ μ: %d\n", coin_change_greedy(coins, 6, 730));
286
287 /* 5. νμμ€ λ°°μ */
288 printf("\n[5] μ΅μ νμμ€ μ\n");
289 int starts[] = {0, 5, 15};
290 int ends[] = {30, 10, 20};
291 printf(" νμ: (0-30), (5-10), (15-20)\n");
292 printf(" νμ νμμ€: %dκ°\n", min_meeting_rooms(starts, ends, 3));
293
294 /* 6. μ ν κ²μ */
295 printf("\n[6] μ ν κ²μ\n");
296 int nums1[] = {2, 3, 1, 1, 4};
297 int nums2[] = {3, 2, 1, 0, 4};
298 printf(" [2,3,1,1,4]: λλ¬=%s, μ΅μμ ν=%d\n",
299 can_jump(nums1, 5) ? "κ°λ₯" : "λΆκ°", min_jumps(nums1, 5));
300 printf(" [3,2,1,0,4]: λλ¬=%s\n", can_jump(nums2, 5) ? "κ°λ₯" : "λΆκ°");
301
302 printf("\n============================================================\n");
303
304 return 0;
305}