[코테 스터디] 3주차 : 그리디

🤔그리디 알고리즘이란

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

✅수행 과정 3단계

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 1단계로 돌가 같은 과정 반복

✅전제 조건

1. 탐욕 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 미치지 않아야 함
2. 최적 부분 구조(Optimal Substructure) : 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성되어야 함

✅유형 및 주의사항

• 동전 교환 문제 : 거스름 돈을 돌려줄 때 , 최소 동전 개수로 거스름돈을 돌려주는 문제
• 최소 신장 트리(MST) : 그래프에서 모든 노드를 포함하면서 간선 가중치의 합이 최소가 되는 트리 찾기 (크루스칼 알고리즘, 프림 알고리즘)
• 최단 경로 문제 : 다익스트라 알고리즘을 이용해 가중치가 있는 그래프에서 최단 경로 찾기

[주의사항]
항상 최적의 해를 보장하지는 않지만, 많은 경우에 대해 빠르고 효율적인 해법을 제공함
문제의 특성에 따라 그리디 알고리즘이 최적의 해를 보장하는지 분석하는 것이 중요!

📌 구현

동전 교환 문제

주어진 금액을 최소 개수의 동전으로 교환하는 문제 

def coin_change(amount, coins):
    coins.sort(reverse=True)  # 큰 단위의 동전부터 사용
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

coins = [1, 5, 10, 50, 100, 500]
amount = 1260
result = coin_change(amount, coins)
print(f"사용된 동전: {result}")

# 사용된 동전: [500, 500, 100, 100, 50, 10]

활동 선택 문제

주어진 활동 중 최대한 많은 활동을 선택하는 문제

def activity_selection(start_times, finish_times):
    n = len(start_times)
    selected_activities = []

    # 첫 번째 활동을 선택
    i = 0
    selected_activities.append(i)

    for j in range(1, n):
        # j 번째 활동이 마지막으로 선택된 활동과 겹치지 않는지 확인
        print(f'start : {start_times[j]} , finish : {finish_times[i]}')
        if start_times[j] >= finish_times[i]:
            selected_activities.append(j)
            i = j

    return selected_activities

# 활동의 시작 시간과 종료 시간
start_times = [1, 3, 0, 5, 8, 5]
finish_times = [2, 4, 6, 7, 9, 9]

# 활동이 종료 시간 기준으로 정렬되었다고 가정
selected_activities = activity_selection(start_times, finish_times)

print("선택된 활동의 인덱스:", selected_activities)

'''
start : 3 , finish : 2
start : 0 , finish : 4
start : 5 , finish : 4
start : 8 , finish : 7
start : 5 , finish : 9
선택된 활동의 인덱스: [0, 1, 3, 4]
'''

크루스칼 알고리즘(최소 신장 트리)

그래프에서 모든 노드를 포함하면서 간선 가중치의 합이 최소가 되는 트리를 찾는 문제

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(n, edges):
    mst = []
    ds = DisjointSet(n)
    edges.sort(key=lambda x: x[2])  # 간선을 가중치 기준으로 정렬

    for u, v, weight in edges:
        if ds.find(u) != ds.find(v):
            ds.union(u, v)
            mst.append((u, v, weight))

    return mst

edges = [
    (0, 1, 1), (0, 2, 3), (1, 2, 3), (1, 3, 6),
    (2, 3, 4), (2, 4, 2), (3, 4, 5)
]
n = 5  # 그래프의 노드 수

mst = kruskal(n, edges)
print("최소 신장 트리의 간선들:", mst)

# 최소 신장 트리의 간선들: [(0, 1, 1), (2, 4, 2), (0, 2, 3), (2, 3, 4)]