[알고리즘] 2주차 그리디

알고리즘의 접근 방식과 문제의 성격이 다름
DP: 하위 문제에 대한 최적의 솔루션을 찾은 다음, 이 결과들을 결합한 정보에 입각해 전역 최적 솔루션에 대한 선택을 한다.
Greedy: 각 단계마다 로컬 최적해를 찾는 문제로 접근해 문제를 더 작게 줄여나가는 형태
➡️ 서로 반대 방향으로 접근함

알고리즘 종류

동전 문제

값을 지불시 동전의 수가 가장 적도록
➡️ 가장 큰 동전부터 지불

def min_coin_count(value,coins):
	total=0
    details=list()
	coins.sort(reverse=True)
    for coin in coins:
    	coin_num = value//coin
        total+=coin_num
        value-=coin_num*coin
        details.append([coin,coin_num])
    return total,details

부분 배낭 문제 Fractional Knapsack Prob

무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣음
각 물건은 무게와 가치로 표현
➡️ 물건은 쪼갤 수 있음으로 Fractional 이라 함
(쪼갤 수 없는 배낭 문제는 0/1 Knapsack Problem(다이나믹 프로그래밍))

datas=[(10,10), ...]
def get_max_value(datas,capacity):
	datas = sorted(datas,key=lambdㄱa x:x[1]/x[0],reverse=True)
    	# 어떤 기준으로 정렬할 것인지 선택하는 것이 최적 선택의 시작
    total=0
    details=list()
    
    for data in datas:
    	if capacity - data[0]>=0: # 통째로 넣기
        	capacity-=data[0]
            total+=data[1]
            details.append(data[0],data[1],1])
        else: # 쪼개서 넣기
        	fraction = capacity/data[0]
            tota+=data[1]*fraction
            details.append([data[0],data[1],fraction])
            break # 더 이상 계산 안해도 됨
        return total,details

➡️ 지금 순간에 최적을 찾기. 그 순간에 가장 가치가 높은 것을 고르는 것. 하지만 그 순간의 최적이기에 완벽히 최적일 수는 없다.

Kruskal Algorithm

가중치를 간선에 할당한 그래프인 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답 구하는 것
MST(최소 비용 신장 트리)가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.

간선을 거리가 짧은 순서대로 포함시키기

모든 노드를 최대한 적은 비용으로 연결만

모든 간선 정보를 가중치를 기준으로 오름차순으로 정렬 후 비용이 적은 간선부터 차근차근 그래프에 포함시키면 된다.

동작

간선 선택을 기반으로 함
이전 단계와 상관없이 무조건 최소 간선만을 선택

주의

선택된 간선들 집합에 다음 간선을 추가시 사이클 생성 여부 확인 체크
➡️ union-find 알고리즘 이용 : 추가하고자 하는 간선이 양끝 정점이 같은 집합에 속하는지 검사

사실상 정렬 알고리즘과 union-find 알고리즘의 합으로 볼 수 있다.

코드

graph=[(1,2,13),....] #(정점1, 정점2, 가중치)
graph.sort(key=lambda x:x[2])

mst=[]
n=len(graph)
p=[0] # 상호 배타적 집합 <<??

for i in range(1,n+1):
	p.append(i) # 각 정점 자신이 집합의 대표
def find(u):
    if u!=p[u]:
    	p[u]=find(p[u]) # 경로 압축
    return p[u]
def union(u,v):
    root1=find(u)
    root2=find(v)
    p[root2]=root1 # 임의로 root2가 root1의 부모

tree_edges=0 # 간선 개수
mst_cost=0 # 가중치 합
while True:
    if tree_edges==n-1:break
    u,v,wt = graph.pop(0)
    if find(u)!=find(v): # u와 v가 서로 다른 집합에 속해 있으면
    union(u,v)
    mst.append((u,v))
    mst_cost+=wt
    tree_edges+=1

# 특정 원소가 속한 집합을 찾기
def find(parent, x):
    if parent[x] == x:
        return x
    parent[x] = find(parent, parent[x])
    return parent[x]


# 두 원소가 속한 집합을 합치기 (간선 연결한다고 생각!)
def union(parent, a, b):
    rootA = find(parent, a)
    rootB = find(parent, b)

    if rootA < rootB:
        parent[rootB] = rootA
    else:
        parent[rootA] = rootB


import sys

input = sys.stdin.readline
# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1)

edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 오름차순 정렬하기 위해 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

edges.sort()

for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함(=연결한다.)
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        result += cost

print(result)

# sample input
# 7 9
# 1 2 29
# 1 6 75
# 2 3 35
# 2 6 34
# 3 4 7
# 4 6 23
# 4 7 13
# 5 6 53
# 6 7 25

시간 복잡도

union-find 알고리즘을 이용하면 Kruskal 알고리즘의 시간 복잡도는 간선 정렬 시간에 좌우
퀵정렬과 같은 효율적인 알고리즘으로 정렬시 O(eloge)
[비교][Prim](https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html) 알고리즘 시간 복잡도는 O(n^2)이므로
- 적은 개수의 간선을 갖는 희소 그래프이면 Kruskal이 적합
- 많은 개수의 간선을 갖는 밀집 그래프라면 Prim이 적합하다.