🤔그리디 알고리즘이란
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘
✅수행 과정 3단계
- 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해 선택
- 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사
- 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못한다면 1단계로 돌가 같은 과정 반복
✅전제 조건
- 탐욕 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 미치지 않아야 함
- 최적 부분 구조(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)]
'🏷️CS > Algorithm' 카테고리의 다른 글
[코테 스터디] 4주차 : 동적계획법 (0) | 2024.07.01 |
---|---|
[코테 스터디] 2주차 : 시간복잡도 (0) | 2024.06.17 |
[코테 스터디] 2주차 : DFS/BFS (1) | 2024.06.17 |
[코테 스터디] 1주차 : 자료구조 / 이진탐색 (1) | 2024.06.10 |
[백준] 1966 (프린터 큐) (2) | 2023.07.26 |