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

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

사전식정렬은 말그대로 사전에서 먼저 나오는 순서대로 정렬하는 것임 입력은 하나의 튜플인데 이게 key임 단계1에서 튜플의 맨마지막값을 비교해서 순서대로 정렬함. 4가 가장 작으니까 맨앞에 둠 단계2에서 중간값을 비교해서 크기순으로 정렬함 단계3에서는 첫번째 값을 비교해서 정렬하면 끝임 여기서 같은 값을 가질때는 입력순서에 따름 예제에서는 맨뒤부터 정렬했지만 맨 앞에서부터 정렬해도됨 어디부터 정렬할지 정하는것이 중요함

쉘 정렬(Shell sort)는 삽입 정렬에 전처리 과정을 추가한 것입니다. 전처리과정이란 작은 값을 가진 원소들을 앞쪽으로 옮겨서 큰 값들을 배열의 뒷쪽에 있게 하는 과정입니다. 전처리과정에서 일정한 간격으로 떨어진 원소들에 대해 삽입정렬을 수행합니다. 일정한 간격을 h-sort라고 합니다. 4-정렬은 인덱스0, 4, 8 한덩어리로 만들고 인덱스1, 5, 9를 한덩어리로 만들어서 수행하는 정렬입니다. 인덱스에 4를 더한것들을 모아서 한덩어리로 만드는겁니다. 그림에서 같은 색깔로 되어있는 부분이 한덩어리입니다. 같은 색깔내에서 삽입정렬을 수행합니다. 그러면 작은 값은 앞으로 큰 값은 뒤에 위치하게 됩니다. 이제 4-정렬에서 2-정렬로 바꿔서 다시 삽입정렬을 수행합니다. 그다음은 1-sort 결과적으로 정..