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

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

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

[파이썬 자료구조] 깊이 우선 탐색 (DFS, depth first traversal) 그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 v ohaengsa.tistory.com 너비 우선 탐색(Breadth-first search, BFS)은 맹목적탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. cross edge는 재방문을 막기위한 표시임 1단계. 임의의 점하나를 선택함(예제에서는 A를 선택..

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

버킷 정렬 또는 버킷 소트(bucket sort)는 수많은 버킷에 배열 요소들을 분산시킴으로써 동작하는 정렬알고리즘이다. 각 버킷은 그 뒤로 개별 정렬되는데, 이는 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 반복 적용시켜 수행한다. key의 범위를 알려진 경우에만 사용가능한 정렬방식임 키의 값을 새로운 배열의 인덱스로 사용함 파이썬으로 구현해봄 1 2 3 4 5 6 7 8 9 10 11 12 13 def bucket_sort(keys, low, high): length = high - low + 1 # length of buckets bucket = [[] for _ in range(length)] keys_sorted = [] for elem in keys: bucket[elem-low].a..

정렬 중에서 퀵정렬에 대해서 알아보겠습니다. 2가지의 방식이 있습니다. 방법1. 1단계. 입력된 임의의 원소를 피벗으로 선택합니다. 피벗은 기준이 되는 원소입니다. 2단계. 피벗을 기준으로 작은 원소들, 피벗과 같은 원소들, 피벗보다 큰 원소들로 나눕니다. 3단계. 재귀적으로 정렬하고 크기순으로 놓으면 끝 파이썬으로 간단히 구현해보면 1 2 3 4 5 6 7 8 def quick_sort(S): if len(S) = b: return pivot_idx = random.randint(a, b) S[pivot_idx], S[a] = S[a], S[pivot_idx] pivot = S[a] left = a+1 right = b while left

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

예를 들면, i인덱스의 값이 i-1값보다 작으면 i-1값과 자리를 바꾸고 i-2와 다시 비교하는 과정을 반복합니다. 이과정을 반복하다보면 전체적으로 정렬된 리스트를 얻게됩니다. 파이썬 코드로 간단히 구현해보았습니다. 1 2 3 4 5 6 7 def insertion_sort(L): for i in range(1, len(L)): for j in range(i, 0, -1): if L[j-1] > L[j]: L[j-1], L[j] = L[j], L[j-1] else: break cs 4번째 줄에서 비교를 하고 5번째 줄에서 교환을 합니다. 만약 j값이 j-1값보다 크다면 break문을 통해 다음 비교를 실행합니다. 다음은 삽입 정렬의 시간복잡도에 대해서 알아보겠습니다. 인덱스 1일때 인덱스 0과 한번 비교..