728x90
- 욕심내어 풀어보기
그리디 알고리즘이란?
- 최적화(Optimization) 문제 : 최솟값(또는 최댓값)을 찾는 문제
- 욕심내어 해결하는 것 : 알고리즘이 수행하는 과정에서 항상 가장 작은것(또는 문제에 따라서 가장 큰 것)을 선택하는 방식으로 문제의 해를 계산하는 것
그리디 알고리즘은 문제의 해를 계산하는 과정에서 항상 '욕심내어' 해를 선택하고 이렇게 선택한 해를 모아서(축적하여) 최종적인 해를 찾는 알고리즘이다.
- 태스크 스케줄링
일반적인 태스크 스케줄링(Task Scheduling) : 각 태스트가 시작과 종료 시각을 가질 때, 태스크를 처리할 프로세서에 수행 시간이 겹치지 않게 태스크들을 할당하는 문제
- 구간 스케줄링
Interval Scheduling
예를 들어 대학교에서 동아리들이 중앙도서관의 미팅룸을 사용하기 위해 도서관에 신청했다. 각 동아리는 미팅의 시작과 종료 시각을 제출하였고 도서관에서는 가장 많은 동아리들이 미팅룸을 사용하도록 시간표를 작성하려고 할 때 스케줄을 최적화 해야한다.
그리디 알고리즘을 사용한다. 구간 스케줄링에서 그리디 알고리즘은 다음과 같이 작동한다.
- 종료 시각으로 정렬
- 가장 일찍 종료하는 동아리를 선택
- 다음 동아리의 시작 시각이 직전에 선택된 동아리의 종료 시각 이전이면 다음 동아리를 포기하고, 이후이면 다음 동아리를 선택한다.
a = [['지역봉사회', 8, 13], ['서예회', 9, 11], ['토론회', 10, 12], ['바둑회', 11, 14], ['문학회', 13, 16], ['독서회', 14, 15], ['사진회', 15, 17]]
a.sort(key=lambda t: t[2])
solution = [a[0]]
i = 0
for j in range(1, len(a)):
if a[j][1] >= a[i][2]:
solution.append(a[j])
i = j
print('선택된 동아리:', solution)실행해보면 선택된 동아리는 서예회, 바둑회, 독서회, 사진회가 선택된다.
- 최소 신장 트리
- 트리는 점들이 서로 연결되어 있는 동시에 사이클을 가지지 않는다.
- 신장트리 : 그래프의 모든 점들을 연결하는 트리
- 트리의 특성
- n개의 점을 가진 그래프의 신장 트리는 n-1개의 간선을 가진다.
- 두 점 사이의 경로는 하나밖에 없다.
최소 신장 트리(Minimum Spanning Tree, MST) : 간선에 가중치가 부여된 그래프에서 최소 가중치의 합을 가진 신장 트리
크루스칼 알고리즘이란?
그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다.
그래프에는 정점(Vertex)과 간선(Edge)가 있는데, 간선에 가중치가 포함되어 있다.
그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용한다.
- 간선을 가중치 기준으로 오름차순 정렬
- 간선을 순차적으로 순회하면서 최소 신장 트리를 만든다. 이때, 서로소 집합 알고리즘에 기반하여 트리에 순환성이 생기지 않는 간선만 추가한다.
- 최소 신장 트리가 될 때까지 2번 과정을 반복
class Edge:
def __init__(self, u, v, weight):
self.u = u
self.v = v
self.weight = weight
class KruskalMST:
def __init__(self, vertices):
self.vertices = vertices
self.edges = []
def add_edge(self, u, v, weight):
self.edges.append(Edge(u, v, weight))
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
root_x = self.find(parent, x)
root_y = self.find(parent, y)
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
def kruskal(self):
# 간선을 가중치 기준으로 정렬
self.edges = sorted(self.edges, key=lambda edge: edge.weight)
parent = []
rank = []
mst = []
# 초기화
for node in range(self.vertices):
parent.append(node)
rank.append(0)
for edge in self.edges:
u, v, weight = edge.u, edge.v, edge.weight
root_u = self.find(parent, u)
root_v = self.find(parent, v)
# 사이클이 생기지 않으면 간선을 추가
if root_u != root_v:
mst.append((u, v, weight))
self.union(parent, rank, root_u, root_v)
return mst
# 예제 사용
graph = KruskalMST(4) # 정점 수
# 간선 추가 (u, v, weight)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 2, 6)
graph.add_edge(0, 3, 5)
graph.add_edge(1, 3, 15)
graph.add_edge(2, 3, 4)
mst = graph.kruskal()
print("최소 신장 트리에 포함된 간선:")
for u, v, weight in mst:
print(f"({u}, {v}) - 가중치: {weight}")
프림 알고리즘이란?
최소 신장 트리 구현에 사용되는 알고리즘으로 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법
- 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리를 만든다.
- 삽입된 정점과 인접한 정점 중 연결된 간선의 가중치가 가장 작은 정점을 최소 신장 트리에 추가. 이때, 서로소 집합 알고리즘에 기반하여 트리에 순환성이 생기지 않는 정점만 추가한다.
- 최소 신장 트리가 될 때까지 2번 과정을 반복
import heapq
class PrimMST:
def __init__(self, vertices):
self.vertices = vertices
self.graph = {i: [] for i in range(vertices)} # 인접 리스트로 그래프 표현
def add_edge(self, u, v, weight):
self.graph[u].append((v, weight))
self.graph[v].append((u, weight))
def prim(self, start=0):
visited = [False] * self.vertices # 방문 여부를 저장
min_heap = [(0, start)] # (간선 가중치, 정점)의 우선순위 큐
mst = [] # 최소 신장 트리에 포함된 간선
total_weight = 0 # MST의 총 가중치
while min_heap:
weight, u = heapq.heappop(min_heap) # 최소 가중치 간선 선택
if visited[u]:
continue # 이미 방문한 정점이면 스킵
visited[u] = True
total_weight += weight
# MST에 현재 간선 추가
if weight != 0: # 시작 정점은 간선을 추가하지 않음
mst.append((u, weight))
# 현재 정점의 인접 정점 확인
for v, w in self.graph[u]:
if not visited[v]:
heapq.heappush(min_heap, (w, v))
return mst, total_weight
# 예제 사용
graph = PrimMST(4) # 정점 수
# 간선 추가 (u, v, weight)
graph.add_edge(0, 1, 10)
graph.add_edge(0, 2, 6)
graph.add_edge(0, 3, 5)
graph.add_edge(1, 3, 15)
graph.add_edge(2, 3, 4)
mst, total_weight = graph.prim()
print("최소 신장 트리에 포함된 간선:")
for v, weight in mst:
print(f"정점: {v}, 가중치: {weight}")
print(f"최소 신장 트리의 총 가중치: {total_weight}")
- 최단 경로
가중치 그래프의 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제
대표적인 알고리즘은 다익스트라(Dijkstra) 알고리즘 이다.
다익스트라 알고리즘이란?
그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복한다.
- 출발, 도착 노드 설정
- '최단 거리 테이블' 초기화
- 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택 후 그 노드를 방문처리
- 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.
- 3, 4 번 과정을 반복
import heapq
def dijkstra(graph, start):
# 최단 거리를 저장할 딕셔너리. 초기값은 무한대.
distances = {node: float('inf') for node in graph}
distances[start] = 0 # 시작 정점의 거리는 0
priority_queue = [(0, start)] # (거리, 정점)의 우선순위 큐
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# 이미 처리된 정점이면 스킵
if current_distance > distances[current_node]:
continue
# 현재 정점과 인접한 정점들 탐색
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 더 짧은 경로를 발견하면 업데이트
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 예제 그래프 (인접 리스트로 표현)
graph = {
'A': {'B': 4, 'C': 2},
'B': {'A': 4, 'C': 5, 'D': 10},
'C': {'A': 2, 'B': 5, 'D': 3},
'D': {'B': 10, 'C': 3},
}
# 시작 정점
start_node = 'A'
# 다익스트라 알고리즘 실행
shortest_distances = dijkstra(graph, start_node)
print(f"시작 정점 '{start_node}'으로부터 최단 거리:")
for node, distance in shortest_distances.items():
print(f"{node}: {distance}")728x90