blog...

최소신장트리 MST 하나의 연결성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치 합이 최소인 신장트리 ※ 신장트리란(Spanning Tree)? → 주어진 그래프가 하나의 연결성분으로 구성되어 있을 때, 그래프의 모든 정점들을 싸이클 없이 연결하는 부분그래프 MST 알고리즘에는 Kruskal, Prim, Sollin이 있음→Greedy Kruskal 알고리즘 가장 작은 가중치 순서대로 선택 (가중치1→2→3 이런식으로) 사이클 만들면 버리기 n-1개 간선 선택되면 종료 주요코드(일부) weights=[(0,1,9),(0,2,10)...(5,6,6)] # u,v,wt 순 #kruskal은 가중치를 기준으로 정렬해야함! weights.sort(key=lambda t:t[2]) # find함수 : u가..

선택 정렬(selection sort) O($n^2$) 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나감 삽입정렬(insertion sort) O($n^2$) 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬 역정렬된 경우 최악 #삽입정렬1 def insertion_sort1(A) : n = len(A) for i in range(1, n): key = A[i] j = i-1 while j>=0 and A[j] > key: A[j+1] = A[j] j-=1 A[j+1] = key #삽입정렬2 - 더 오래걸림 def insertion_sort2(a): for i in range(1, len(a)): # i 현재 원소..