병합정렬
-
[n524] 알고리즘 (2)AI 부트캠프 2022. 1. 28. 10:21
Divide and Conquer(분할 정복) 방법 분할과 정보는 큰 문제를 작은 단위로 나눠서 푸는 알고리즘 방법이다. 재귀 호출과의 차이점은 재귀의 경우 같은 함수 코드를 재호출 하는 것이며, 분할 정복은 비슷한 작업을 재진행 하는 점이다. 즉, 분할 정복은 같은 함수 코드를 재호출 하는 것은 아닐 수 있다. 문제 분할을 스텝 1~5 방향으로 했다면, 문제 해결은 스텝 5~1 방향으로 되어야 한다. 즉 문제를 분할 하는 과정과 해결하는 과정이 있다. 퀵정렬과 병합정렬(Quick Sort and Merge Sort) 둘 다 분할과 정복 (divide and conquer) 개념으로 문제를 해결한다. 보통, 퀵 정렬이 병합 정렬 시간 복잡도는 둘 다 O(nlogn)이다. 퀵 정렬은 좌 우로 나눠서 재귀적..
-
[알고리즘] 병합 정렬 Merge SortAlgorithms & Data Structure 2021. 8. 18. 15:31
병합 정렬이란 분할 정복 알고리즘의 기법을 사용한다. 합병 정렬이라고도 불린다. 재귀 용법을 이용해서 리스트를 잘게 자른다. 그 안에서 다시 또 자른다. 그 뒤에 두 개씩 묶어서 정렬한다. 분리하는 단계, 합병하는 단계로 크게 나뉜다. 병합 정렬 실행 모습 알고리즘 구현하기 def mergesplit(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_point += 1 else: merged.append(left[left_point]) left_point += 1 # case2: left만 남아있는 경..