[파이썬 자료구조] Binary Heap Binary Heap 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조 예제는 모두 최소힙인 경우임 먼저 이진힙에서 최소값을 삭제하는 예를 ohaengsa.tistory.com 힙정렬 힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다....라고 위키에 써져있음 간단히 살펴보자 1단계. 5가 삽입된 경우임. 트리의 맨 아래에서 왼쪽에다가 붙혀줌 2단계. 위를 쳐다보니 40이 있다. 5가 더 작으니까 40과 교환한다. 3단계. 위를 쳐다보니 이제 20이 있다. 5가 더작으니까 교환한다...

Dijkstra algorithm 다익스트라 알고리즘은 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 위의 예제를 통해 알아보자 각 정점은 인접한 정점에 대한 정보만 가짐. 인접하지 않는 정점까지의 비용은 무한대로 초기화함 먼저 집합N'에 A를 넣으면 A의 정보로 다음과 같은 테이블을 만듬 A B C D E F A 0 10 30 15 무한대 무한대 집합N' A 다음비용이 가장 작은 B를 N'에 넣음 A B C D E F A 0 10 30 15 30 무한대 집합N' A,B B의 정보로 인해서 A->E까지의 경로가 업데이트 됨 다음단계에서는 비용이 가장 작은 D를 집합에 넣음 A B C D E F A 0 10 20 15 30 35 집합N' A, B, D D를 추가하면서 A->C의 경로보다 A->D->C의..

Floyd-Warshall Algorithm i -> j까지의 최소비용경로가 존재할 때, 정점k를 발견했다고 가정 k를 통해서 가는 경로와 통하지 않는 경로를 비교하여 비용이 작은 쪽을 선택하는 알고리즘 k를 통해서 가는것이 더 좋다면 간선완화를 함

이전 포스팅에서 Kruskal 알고리즘에 대해서 알아보았음. [파이썬 자료구조] Kruskal 알고리즘 [파이썬 자료구조] 그래프(Graph) 그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간� ohaengsa.tistory.com Kruskal 알고리즘에서 cycle 여부를 확인하는 과정임. 정점X와 정점Y를 직접 연결하려할 때 정점X에서 Y로 가는 경로가 이미 존재하는지 확인하는 방법 만약 X,Y가 Z를 통해 연결되어있다면 X,Y를 직접 연결하는 edge를 버림 자기 자신을 가르키는 하나의 원소로 이루어짐 5개의 집합있다고 가정함. {0}과 {1}을 합치면 1은 0을 가르킨다. 왼쪽 ..

[파이썬 자료구조] 그래프(Graph) 그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간선에 가중치가 부여된 그래프 병 ohaengsa.tistory.com 최소신장트리(MST)는 edge의 가중치의 합이 최소인 신장트리임 신장트리란? 모든 정점을 연결하는 트리라고 생각하면됨. Kruskal 알고리즘 가중치의 크기순서대로 간선을 추가하며, 싸이클이 만들지 않는 알고리즘임 최소신장트리(MST)를 만드는 알고리즘 예제를 보면 7개의 정점과 12개의 edge가 있음. 각각의 edge에는 가중치가 있음. 0단계. edge를 가중치에 따라 정렬을 함 1단계. 정렬순서대로 (4,6)을 연결하는 ed..