공부/알고리즘7 [알고리즘] 크루스칼 알고리즘 + Python 구현 크루스칼 알고리즘은 Minimum Spanning Tree(최소비용 신장 트리)를 만드는 알고리즘입니다. 그 방법을 5개의 노드를 가지고 6개의 엣지를 가진 그래프를 가지고 단계별로 설명해보도록 하겠습니다. 일단 모든 엣지들의 정보를 비용의 정보를 토대로 오름차순으로 정렬해줍니다. (사실 내림차순 이어도 괜찮습니다.) 이렇게 정렬된 엣지들을 작은 순으로 하나씩 가져와서 사용할 것이기 때문입니다. 그리고 편하신 자료형으로 각 노드들의 부모 노드를 표시하게 만들고 일단은 자기 자신이 부모 노드가 되도록 초기화를 합니다. 이는 그래프에서 사이클이 발생했을 경우 그 엣지를 사용하지 않기 위함입니다. 처음으로 가장 비용이 적은 엣지 중 하나인 A - C 에지를 가져오겠습니다. A - C에서 A와 C 노드의 부모 .. 2021. 7. 20. [알고리즘] 다익스트라 알고리즘 + Python 구현 참조 : https://youtu.be/HFapeLxvdNg Dijkstra(다익스트라) 알고리즘은 그래프에서 노드 간 최단 경로를 찾는 알고리즘입니다. 그 방법을 간단한 5개의 노드를 가진 간단한 그래프를 통하여 단계별로 진행해보겠습니다. 첫 번째로 일단 경로가 시작되는 노드를 잡습니다. 이 그래프에서는 A 노드가 되고 목적지 노드는 E로 가정합니다. 현재 노드에서 모든 노드까지의 비용을 계산합니다. 다만 현재의 노드와 바로 연결되지 않는 노드는 비용을 ∞로 둡니다. A 아래의 4개의 노드는 [B] A / 3이라면 현재까지의 B 노드로 가는 최저 비용의 경로는 3의 비용을 가지고 있으며 바로 직전의 노드는 A 였음을 뜻합니다. 계산이 종료되었다면 지금까지 밝혀진 경로 4개의 노드 중 가장 낮은 비용을 .. 2021. 7. 17. [알고리즘 공부] 5. Quick Sort (퀵 정렬) Quick Sort(퀵 정렬)은 특정 원소를 Pivot으로 잡습니다. 그 후 Pivot을 기준으로 작은 원소는 왼쪽으로 큰 원소는 오른쪽으로 보낸 뒤 Pivot을 이동 시킵니다. 다만 제가 이리저리 검색하면서 공부해본 결과 퀵 정렬의 기본은 딱 여기까지이고 이후 Pivot 설정문제나 이후 정렬 방식 등에 따라 많은 버전이 존재합니다. 이 말은 곧 Pivot을 어떻게 잡아주느냐에 따라서 알고리즘의 효율이 결정된다는 말이기도 합니다. 일반적으로 퀵 정렬은 시간 복잡도 O(n log n)을 가지고 있으나 최악의 경우 O(n^2)을 가지기도 합니다. 이 글에서는 가장 간단한 퀵 정렬 방식 중 하나인 로무토 파티션 버전을 기준으로 설명 및 코드를 짜겠습니다. 위의 방식을 재귀적으로 반복하면 정렬이 되겠죠? 하지만.. 2021. 5. 26. [알고리즘 공부] 4. Merge Sort(합병 정렬) 정렬 알고리즘을 공부하면서 앞의 정렬 알고리즘들은 가볍게 훑고 지나가도 되지만 이제부터는 집중해서 직접 구현해보고 이해하는 것이 좋습니다. Merge Sort(합병 정렬)은 이 쪽 분야계의 천재 중의 천재로 불리는 존 폰 노이만이 개발했습니다. 합병 정렬은 특히 분할 정복 알고리즘으로 짜여진 알고리즘입니다. 분할 정복 알고리즘 문제를 풀기 쉽도록 분할 한 다음 나누어서 풀고 다시 합쳐서 해결하는 방법 이는 위의 그림만 보고는 헷갈릴 수도 있는데 아래의 링크를 보시면 쉽게 이해 될 것입니다. https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html [알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog St.. 2021. 5. 25. 이전 1 2 다음
