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

그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 visted vertex는 한번 지나온 정점임 A -> B -> C로 순서일 때, C -> A가 연결되있음. 하지만 A는 이미 지나온 정점임. C -> A Edge를 back edge로 표기함 이제 C는 D로 가거나 E로 갈 수 있음. 파이썬으로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 def DFS(g, u, discovered): for e in g.incident_edges(u): v = e.opposite(u) if v not in discovered: dis..

1단계. 1의자리를 비교해서 정렬함(값이 같을때는 입력순서를 따름) 2단계. 10의자리를 비교해서 정렬 3단계. 100의 자리를 비교해서 정렬 시간복잡도 예제에서는 10진수의 수니까 N은 10임. 따라서 O(dn)의 수행시간을 가짐 자리수를 안다면 수행 성능은 O(32n) -> O(n)임

사전식정렬은 말그대로 사전에서 먼저 나오는 순서대로 정렬하는 것임 입력은 하나의 튜플인데 이게 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

리스트 분리해서 합칠때 정렬하는 방법입니다! 각각 재귀적으로 정렬을 수행하고 두개의 정렬된 배열을 합칩니다. 각각의 리스트의 맨 앞의 값을 비교해서 둘 중 작은 값을 새로운 리스트의 맨 앞에 삽입합니다. 파이썬으로 구현해보면 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def merge_sort(L): n = len(L) if n

쉘 정렬(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과 한번 비교..

선택정렬(Selection sort): 배열에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬 알고리즘 1단계. 전체길이가 m일때 인덱스 0 ~ m-1 중에서 가장 작은 값을 찾아서 인덱스0의 값과 교환 2단계. 인덱스 1~m-1 중에서 가장 작은 값과 인덱스 1의 값을 교환 3단계. 이과정을 계속 반복하면 정렬된 리스트를 얻을 수 있다. 오름차순,내림차순 둘다 가능 선택정렬 파이썬 코드 1 2 3 4 5 6 7 def selection_sort(L): for i in range(0, len(L)): min_index = i for j in range(i, len(L)): if L[min_index] > L[j]: min_index = j L[..