条件

ダイナミックプログラミングとの違い

アルゴリズムタイプ

コイン問題

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

一部リュック問題分割式Kapsack Prob

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

短距離順に幹線を含める

コード#コード#

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

時間の複雑さ