19_greedy.py

Download
python 443 lines 12.7 KB 
  1"""
  2νƒμš• μ•Œκ³ λ¦¬μ¦˜ (Greedy Algorithm)
  3Greedy Algorithms
  4
  5맀 μˆœκ°„ 졜적의 선택을 ν•˜μ—¬ 전체 μ΅œμ ν•΄λ₯Ό κ΅¬ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.
  6"""
  7
  8from typing import List, Tuple
  9import heapq
 10
 11
 12# =============================================================================
 13# 1. ν™œλ™ 선택 문제 (Activity Selection)
 14# =============================================================================
 15
 16def activity_selection(activities: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
 17    """
 18    κ²ΉμΉ˜μ§€ μ•ŠλŠ” μ΅œλŒ€ ν™œλ™ 수 선택
 19    activities: [(μ‹œμž‘, μ’…λ£Œ), ...]
 20    νƒμš• μ „λž΅: μ’…λ£Œ μ‹œκ°„μ΄ λΉ λ₯Έ μˆœμ„œλ‘œ 선택
 21    μ‹œκ°„λ³΅μž‘λ„: O(n log n)
 22    """
 23    # μ’…λ£Œ μ‹œκ°„μœΌλ‘œ μ •λ ¬
 24    sorted_activities = sorted(activities, key=lambda x: x[1])
 25
 26    selected = []
 27    last_end = 0
 28
 29    for start, end in sorted_activities:
 30        if start >= last_end:
 31            selected.append((start, end))
 32            last_end = end
 33
 34    return selected
 35
 36
 37# =============================================================================
 38# 2. λΆ„ν•  κ°€λŠ₯ λ°°λ‚­ 문제 (Fractional Knapsack)
 39# =============================================================================
 40
 41def fractional_knapsack(capacity: int, items: List[Tuple[int, int]]) -> float:
 42    """
 43    λΆ„ν•  κ°€λŠ₯ν•œ λ°°λ‚­ 문제
 44    items: [(κ°€μΉ˜, 무게), ...]
 45    νƒμš• μ „λž΅: λ‹¨μœ„ λ¬΄κ²Œλ‹Ή κ°€μΉ˜κ°€ 높은 μˆœμ„œλ‘œ 선택
 46    μ‹œκ°„λ³΅μž‘λ„: O(n log n)
 47    """
 48    # λ‹¨μœ„ λ¬΄κ²Œλ‹Ή κ°€μΉ˜λ‘œ μ •λ ¬ (λ‚΄λ¦Όμ°¨μˆœ)
 49    sorted_items = sorted(items, key=lambda x: x[0] / x[1], reverse=True)
 50
 51    total_value = 0
 52    remaining = capacity
 53
 54    for value, weight in sorted_items:
 55        if remaining >= weight:
 56            total_value += value
 57            remaining -= weight
 58        else:
 59            # λΆ„ν• ν•΄μ„œ λ‹΄κΈ°
 60            total_value += value * (remaining / weight)
 61            break
 62
 63    return total_value
 64
 65
 66# =============================================================================
 67# 3. νšŒμ˜μ‹€ λ°°μ • (Meeting Rooms)
 68# =============================================================================
 69
 70def min_meeting_rooms(intervals: List[Tuple[int, int]]) -> int:
 71    """
 72    ν•„μš”ν•œ μ΅œμ†Œ νšŒμ˜μ‹€ 수
 73    μ‹œκ°„λ³΅μž‘λ„: O(n log n)
 74    """
 75    if not intervals:
 76        return 0
 77
 78    # μ‹œμž‘/μ’…λ£Œ 이벀트둜 뢄리
 79    events = []
 80    for start, end in intervals:
 81        events.append((start, 1))   # μ‹œμž‘: +1
 82        events.append((end, -1))    # μ’…λ£Œ: -1
 83
 84    events.sort()
 85
 86    max_rooms = current_rooms = 0
 87    for _, delta in events:
 88        current_rooms += delta
 89        max_rooms = max(max_rooms, current_rooms)
 90
 91    return max_rooms
 92
 93
 94# =============================================================================
 95# 4. μž‘μ—… μŠ€μΌ€μ€„λ§ (Job Scheduling)
 96# =============================================================================
 97
 98def job_scheduling(jobs: List[Tuple[int, int, int]]) -> Tuple[int, List[int]]:
 99    """
100    마감 κΈ°ν•œ λ‚΄ μ΅œλŒ€ 이읡 μŠ€μΌ€μ€„λ§
101    jobs: [(μž‘μ—…ID, 마감일, 이읡), ...]
102    νƒμš• μ „λž΅: 이읡이 높은 μˆœμ„œλ‘œ, κ°€λŠ₯ν•œ λŠ¦μ€ μŠ¬λ‘―μ— λ°°μ •
103    """
104    # 이읡 λ‚΄λ¦Όμ°¨μˆœ μ •λ ¬
105    sorted_jobs = sorted(jobs, key=lambda x: x[2], reverse=True)
106
107    max_deadline = max(job[1] for job in jobs)
108    slots = [None] * (max_deadline + 1)  # 각 μ‹œκ°„ 슬둯
109    total_profit = 0
110    scheduled = []
111
112    for job_id, deadline, profit in sorted_jobs:
113        # λ§ˆκ°μΌλΆ€ν„° μ—­μˆœμœΌλ‘œ 빈 슬둯 μ°ΎκΈ°
114        for slot in range(deadline, 0, -1):
115            if slots[slot] is None:
116                slots[slot] = job_id
117                total_profit += profit
118                scheduled.append(job_id)
119                break
120
121    return total_profit, scheduled
122
123
124# =============================================================================
125# 5. ν—ˆν”„λ§Œ μ½”λ”© (Huffman Coding)
126# =============================================================================
127
128class HuffmanNode:
129    def __init__(self, char: str = None, freq: int = 0):
130        self.char = char
131        self.freq = freq
132        self.left = None
133        self.right = None
134
135    def __lt__(self, other):
136        return self.freq < other.freq
137
138
139def huffman_encoding(text: str) -> Tuple[dict, str]:
140    """
141    ν—ˆν”„λ§Œ 인코딩
142    λ°˜ν™˜: (λ¬Έμžβ†’μ½”λ“œ λ”•μ…”λ„ˆλ¦¬, μΈμ½”λ”©λœ λ¬Έμžμ—΄)
143    μ‹œκ°„λ³΅μž‘λ„: O(n log n)
144    """
145    if not text:
146        return {}, ""
147
148    # λΉˆλ„ 계산
149    freq = {}
150    for char in text:
151        freq[char] = freq.get(char, 0) + 1
152
153    # μš°μ„ μˆœμœ„ 큐둜 트리 ꡬ성
154    heap = [HuffmanNode(char, f) for char, f in freq.items()]
155    heapq.heapify(heap)
156
157    while len(heap) > 1:
158        left = heapq.heappop(heap)
159        right = heapq.heappop(heap)
160
161        merged = HuffmanNode(freq=left.freq + right.freq)
162        merged.left = left
163        merged.right = right
164
165        heapq.heappush(heap, merged)
166
167    # μ½”λ“œ 생성
168    codes = {}
169
170    def generate_codes(node: HuffmanNode, code: str):
171        if node is None:
172            return
173
174        if node.char is not None:
175            codes[node.char] = code if code else "0"
176            return
177
178        generate_codes(node.left, code + "0")
179        generate_codes(node.right, code + "1")
180
181    if heap:
182        generate_codes(heap[0], "")
183
184    # 인코딩
185    encoded = ''.join(codes[char] for char in text)
186
187    return codes, encoded
188
189
190def huffman_decoding(encoded: str, codes: dict) -> str:
191    """ν—ˆν”„λ§Œ λ””μ½”λ”©"""
192    reverse_codes = {v: k for k, v in codes.items()}
193    decoded = []
194    current = ""
195
196    for bit in encoded:
197        current += bit
198        if current in reverse_codes:
199            decoded.append(reverse_codes[current])
200            current = ""
201
202    return ''.join(decoded)
203
204
205# =============================================================================
206# 6. 동전 κ±°μŠ€λ¦„λˆ (Coin Change - Greedy)
207# =============================================================================
208
209def coin_change_greedy(coins: List[int], amount: int) -> List[int]:
210    """
211    동전 κ±°μŠ€λ¦„λˆ (νƒμš•, νŠΉμ • 동전 μ§‘ν•©μ—μ„œλ§Œ 졜적)
212    coins: λ‚΄λ¦Όμ°¨μˆœ μ •λ ¬λœ 동전
213    주의: 일반적인 동전 μ‘°ν•©μ—μ„œλŠ” DP ν•„μš”
214    """
215    coins = sorted(coins, reverse=True)
216    result = []
217
218    for coin in coins:
219        while amount >= coin:
220            result.append(coin)
221            amount -= coin
222
223    return result if amount == 0 else []
224
225
226# =============================================================================
227# 7. ꡬ간 μŠ€μΌ€μ€„λ§ (Interval Scheduling)
228# =============================================================================
229
230def interval_partitioning(intervals: List[Tuple[int, int]]) -> List[List[Tuple[int, int]]]:
231    """
232    ꡬ간듀을 μ΅œμ†Œ κ·Έλ£Ή 수둜 λΆ„ν•  (각 κ·Έλ£Ή λ‚΄ κ²ΉμΉ¨ μ—†μŒ)
233    μ‹œκ°„λ³΅μž‘λ„: O(n log n)
234    """
235    if not intervals:
236        return []
237
238    # μ‹œμž‘ μ‹œκ°„μœΌλ‘œ μ •λ ¬
239    sorted_intervals = sorted(enumerate(intervals), key=lambda x: x[1][0])
240
241    # 각 그룹의 μ’…λ£Œ μ‹œκ°„μ„ νž™μœΌλ‘œ 관리
242    groups = []  # [(μ’…λ£Œμ‹œκ°„, 그룹인덱슀)]
243    assignment = [[] for _ in range(len(intervals))]
244
245    for idx, (start, end) in sorted_intervals:
246        if groups and groups[0][0] <= start:
247            # κΈ°μ‘΄ 그룹에 λ°°μ •
248            _, group_idx = heapq.heappop(groups)
249            assignment[group_idx].append(intervals[idx])
250            heapq.heappush(groups, (end, group_idx))
251        else:
252            # μƒˆ κ·Έλ£Ή 생성
253            new_group = len(groups)
254            assignment.append([intervals[idx]])
255            heapq.heappush(groups, (end, new_group))
256
257    return [g for g in assignment if g]
258
259
260# =============================================================================
261# 8. 점프 κ²Œμž„ (Jump Game)
262# =============================================================================
263
264def can_jump(nums: List[int]) -> bool:
265    """
266    λ§ˆμ§€λ§‰ 인덱슀 도달 κ°€λŠ₯ μ—¬λΆ€
267    nums[i] = iμ—μ„œ μ΅œλŒ€ 점프 거리
268    μ‹œκ°„λ³΅μž‘λ„: O(n)
269    """
270    max_reach = 0
271
272    for i, jump in enumerate(nums):
273        if i > max_reach:
274            return False
275        max_reach = max(max_reach, i + jump)
276
277    return True
278
279
280def min_jumps(nums: List[int]) -> int:
281    """
282    λ§ˆμ§€λ§‰ μΈλ±μŠ€κΉŒμ§€ μ΅œμ†Œ 점프 횟수
283    μ‹œκ°„λ³΅μž‘λ„: O(n)
284    """
285    if len(nums) <= 1:
286        return 0
287
288    jumps = 0
289    current_end = 0
290    farthest = 0
291
292    for i in range(len(nums) - 1):
293        farthest = max(farthest, i + nums[i])
294
295        if i == current_end:
296            jumps += 1
297            current_end = farthest
298
299            if current_end >= len(nums) - 1:
300                break
301
302    return jumps
303
304
305# =============================================================================
306# 9. μ£Όμœ μ†Œ (Gas Station)
307# =============================================================================
308
309def can_complete_circuit(gas: List[int], cost: List[int]) -> int:
310    """
311    μ›ν˜• 경둜 μ™„μ£Ό κ°€λŠ₯ν•œ μ‹œμž‘μ  μ°ΎκΈ°
312    gas[i] = iμ—μ„œ μ–»λŠ” 기름
313    cost[i] = iβ†’i+1 이동 λΉ„μš©
314    μ‹œκ°„λ³΅μž‘λ„: O(n)
315    """
316    total_tank = 0
317    current_tank = 0
318    start = 0
319
320    for i in range(len(gas)):
321        gain = gas[i] - cost[i]
322        total_tank += gain
323        current_tank += gain
324
325        if current_tank < 0:
326            start = i + 1
327            current_tank = 0
328
329    return start if total_tank >= 0 else -1
330
331
332# =============================================================================
333# 10. μ΅œμ†Œ ν™”μ‚΄λ‘œ 풍선 ν„°νŠΈλ¦¬κΈ°
334# =============================================================================
335
336def min_arrows(points: List[List[int]]) -> int:
337    """
338    μˆ˜ν‰μ„  풍선을 ν„°νŠΈλ¦¬λŠ” μ΅œμ†Œ ν™”μ‚΄ 수
339    points[i] = [μ‹œμž‘, 끝] λ²”μœ„
340    μ‹œκ°„λ³΅μž‘λ„: O(n log n)
341    """
342    if not points:
343        return 0
344
345    # 끝점으둜 μ •λ ¬
346    points.sort(key=lambda x: x[1])
347
348    arrows = 1
349    arrow_pos = points[0][1]
350
351    for start, end in points[1:]:
352        if start > arrow_pos:
353            arrows += 1
354            arrow_pos = end
355
356    return arrows
357
358
359# =============================================================================
360# ν…ŒμŠ€νŠΈ
361# =============================================================================
362
363def main():
364    print("=" * 60)
365    print("νƒμš• μ•Œκ³ λ¦¬μ¦˜ (Greedy) 예제")
366    print("=" * 60)
367
368    # 1. ν™œλ™ 선택
369    print("\n[1] ν™œλ™ 선택 문제")
370    activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
371    selected = activity_selection(activities)
372    print(f"    ν™œλ™: {activities}")
373    print(f"    선택: {selected} ({len(selected)}개)")
374
375    # 2. λΆ„ν•  κ°€λŠ₯ λ°°λ‚­
376    print("\n[2] λΆ„ν•  κ°€λŠ₯ λ°°λ‚­")
377    items = [(60, 10), (100, 20), (120, 30)]  # (κ°€μΉ˜, 무게)
378    capacity = 50
379    value = fractional_knapsack(capacity, items)
380    print(f"    μ•„μ΄ν…œ (κ°€μΉ˜, 무게): {items}")
381    print(f"    μš©λŸ‰: {capacity}, μ΅œλŒ€ κ°€μΉ˜: {value}")
382
383    # 3. νšŒμ˜μ‹€ λ°°μ •
384    print("\n[3] μ΅œμ†Œ νšŒμ˜μ‹€ 수")
385    meetings = [(0, 30), (5, 10), (15, 20)]
386    rooms = min_meeting_rooms(meetings)
387    print(f"    회의: {meetings}")
388    print(f"    ν•„μš” νšŒμ˜μ‹€: {rooms}개")
389
390    # 4. μž‘μ—… μŠ€μΌ€μ€„λ§
391    print("\n[4] μž‘μ—… μŠ€μΌ€μ€„λ§")
392    jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)]  # (ID, 마감일, 이읡)
393    profit, scheduled = job_scheduling(jobs)
394    print(f"    μž‘μ—… (ID, 마감, 이읡): {jobs}")
395    print(f"    μŠ€μΌ€μ€„: {scheduled}, 총 이읡: {profit}")
396
397    # 5. ν—ˆν”„λ§Œ μ½”λ”©
398    print("\n[5] ν—ˆν”„λ§Œ μ½”λ”©")
399    text = "abracadabra"
400    codes, encoded = huffman_encoding(text)
401    decoded = huffman_decoding(encoded, codes)
402    print(f"    원본: '{text}'")
403    print(f"    μ½”λ“œ: {codes}")
404    print(f"    인코딩: {encoded} ({len(encoded)} bits)")
405    print(f"    원본 크기: {len(text) * 8} bits")
406    print(f"    λ””μ½”λ”©: '{decoded}'")
407
408    # 6. 동전 κ±°μŠ€λ¦„λˆ
409    print("\n[6] 동전 κ±°μŠ€λ¦„λˆ")
410    coins = [500, 100, 50, 10]
411    amount = 1260
412    result = coin_change_greedy(coins, amount)
413    print(f"    동전: {coins}, κΈˆμ•‘: {amount}")
414    print(f"    결과: {result} ({len(result)}개)")
415
416    # 7. 점프 κ²Œμž„
417    print("\n[7] 점프 κ²Œμž„")
418    nums1 = [2, 3, 1, 1, 4]
419    nums2 = [3, 2, 1, 0, 4]
420    print(f"    {nums1}: 도달 κ°€λŠ₯ = {can_jump(nums1)}, μ΅œμ†Œ 점프 = {min_jumps(nums1)}")
421    print(f"    {nums2}: 도달 κ°€λŠ₯ = {can_jump(nums2)}")
422
423    # 8. μ£Όμœ μ†Œ
424    print("\n[8] μ£Όμœ μ†Œ 문제")
425    gas = [1, 2, 3, 4, 5]
426    cost = [3, 4, 5, 1, 2]
427    start = can_complete_circuit(gas, cost)
428    print(f"    gas: {gas}, cost: {cost}")
429    print(f"    μ‹œμž‘μ : {start}")
430
431    # 9. 풍선 ν„°νŠΈλ¦¬κΈ°
432    print("\n[9] μ΅œμ†Œ ν™”μ‚΄λ‘œ 풍선 ν„°νŠΈλ¦¬κΈ°")
433    points = [[10, 16], [2, 8], [1, 6], [7, 12]]
434    arrows = min_arrows(points)
435    print(f"    풍선: {points}")
436    print(f"    ν•„μš” ν™”μ‚΄: {arrows}개")
437
438    print("\n" + "=" * 60)
439
440
441if __name__ == "__main__":
442    main()