[알고리즘] Week 4: 고급 그리디 알고리즘 - 심화와 예제

Day 1: 그리디 알고리즘 심화

• 강의 내용:
  • 그리디 알고리즘 복습
    • 그리디 알고리즘의 기본 원리
    • 그리디 알고리즘의 장단점 및 사용 사례
  • 고급 그리디 알고리즘
    • 그리디 알고리즘 심화 개념
    • 그리디 알고리즘을 사용해야 하는 경우와 사용하지 않아야 하는 경우
  • 그리디 알고리즘의 시간 복잡도 분석
    • 그리디 알고리즘의 시간 복잡도 계산 방법
• 실습:
  • 간단한 그리디 알고리즘 문제 복습

# 간단한 그리디 알고리즘 예제: 동전 교환 문제
def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

# 예제 실행
coins = [1, 2, 5, 10, 20, 50, 100]
amount = 287
print("동전 교환 결과:", coin_change_greedy(coins, amount))  # [100, 100, 50, 20, 10, 5, 2]

 

Day 2: 주식 거래 최대 이익 문제

• 강의 내용:
  • 주식 거래 최대 이익 문제 소개
    • 문제 정의 및 목표
    • 문제 해결을 위한 그리디 접근 방법
  • 최대 이익을 구하는 그리디 알고리즘
    • 가격이 가장 낮은 시점에 구매하고, 가격이 가장 높은 시점에 판매
  • 시간 복잡도 분석
    • 시간 복잡도: O(n)
• 실습:
  • 파이썬을 사용한 주식 거래 최대 이익 문제 구현 및 예제

# 주식 거래 최대 이익 문제 구현
def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

# 예제 실행
prices = [7, 1, 5, 3, 6, 4]
print("최대 이익:", max_profit(prices))  # 5

 

Day 3: 작업 스케줄링 문제

• 강의 내용:
  • 작업 스케줄링 문제 소개
    • 문제 정의 및 목표
    • 문제 해결을 위한 그리디 접근 방법
  • 최대 작업 수를 구하는 그리디 알고리즘
    • 작업 종료 시간이 가장 빠른 작업을 선택
  • 시간 복잡도 분석
    • 시간 복잡도: O(n log n)
• 실습:
  • 파이썬을 사용한 작업 스케줄링 문제 구현 및 예제

# 작업 스케줄링 문제 구현
def job_scheduling(jobs):
    jobs.sort(key=lambda x: x[1])
    selected_jobs = [jobs[0]]
    for i in range(1, len(jobs)):
        if jobs[i][0] >= selected_jobs[-1][1]:
            selected_jobs.append(jobs[i])
    return selected_jobs

# 예제 실행
jobs = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print("선택된 작업:", job_scheduling(jobs))  # [(1, 3), (3, 5), (5, 7), (8, 9)]

 

Day 4: 허프만 코딩 (Huffman Coding)

• 강의 내용:
  • 허프만 코딩의 개념
    • 허프만 코딩이란 무엇인가?
    • 허프만 코딩의 원리 및 사용 사례
  • 허프만 코딩의 그리디 접근 방법
    • 빈도 기반의 이진 트리 생성
  • 시간 복잡도 분석
    • 시간 복잡도: O(n log n)
• 실습:
  • 파이썬을 사용한 허프만 코딩 구현 및 예제

import heapq

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

def huffman_coding(chars, freqs):
    heap = [HuffmanNode(chars[i], freqs[i]) for i in range(len(chars))]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged = HuffmanNode(None, node1.freq + node2.freq)
        merged.left = node1
        merged.right = node2
        heapq.heappush(heap, merged)
    
    return heap[0]

def print_huffman_tree(node, code=""):
    if node is None:
        return
    if node.char is not None:
        print(f"{node.char}: {code}")
    print_huffman_tree(node.left, code + "0")
    print_huffman_tree(node.right, code + "1")

# 예제 실행
chars = ['a', 'b', 'c', 'd', 'e', 'f']
freqs = [5, 9, 12, 13, 16, 45]
huffman_tree = huffman_coding(chars, freqs)
print("허프만 코딩 결과:")
print_huffman_tree(huffman_tree)

 

Day 5: 고급 그리디 알고리즘 종합 연습

• 강의 내용:
  • 종합 연습 문제 풀이
    • 주식 거래 최대 이익 문제, 작업 스케줄링 문제, 허프만 코딩 문제 종합 연습
  • 고급 그리디 알고리즘의 응용
    • 실생활 문제에서의 응용 사례
• 실습:
  • 종합 연습 문제 해결 및 결과 분석

### 종합 연습 문제 예시
1. 주어진 주식 가격 배열에서 최대 이익을 구하세요.
2. 주어진 작업 리스트에서 최대 작업 수를 선택하세요.
3. 주어진 문자와 빈도 배열을 사용하여 허프만 코딩 트리를 생성하고 코드를 출력하세요.

 

Day 6: 프로젝트 준비

• 강의 내용:
  • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 주제 및 요구사항 확정
    • 프로젝트 설계 및 계획 수립
  • 프로젝트 구현 준비
    • 데이터 구조 및 알고리즘 설계
    • 프로젝트 팀 구성 및 역할 분담
• 실습:
  • 프로젝트 주제 및 요구사항 분석
  • 프로젝트 설계 및 계획 수립

### 프로젝트 주제 예시
1. 대규모 데이터 처리 도구 개발
2. 실시간 경로 최적화 시스템

### 프로젝트 요구사항 예시
1. 대규모 데이터 처리 도구:
   - 대규모 데이터셋 입력 및 저장
   - 고급 그리디 알고리즘을 통한 데이터 처리
   - 처리된 데이터 출력 및 성능 분석

### 프로젝트 설계 및 계획 예시
1. 데이터 입력 모듈 구현
2. 고급 그리디 알고리즘 구현 (주식 거래 최대 이익, 작업 스케줄링, 허프만 코딩 등)
3. 데이터 출력 및 성능 분석 모듈 구현

 

이 강의는 파이썬의 고급 그리디 알고리즘, 특히 주식 거래 최대 이익 문제, 작업 스케줄링 문제, 허프만 코딩의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!