Programming/Algorithm3 Merge Sort (병합 정렬) 참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌 Geeks for geeks - Merge Sort 정렬방법에는 시간복잡도 $O(N^2)$ 을 갖는 Selection Sort (선택 정렬), bubble sort(버블정렬), insertion sort(삽입정렬)등이 있다. 이 방법들은 프로그래밍이 직관적이고 쉽지만 데이터의 개수의 제곱으로 계산량이 증가하기 때문에 많은 데이터를 처리해야 하는 작업에는 적합하지 않다. 이를 극복하기 지난 글에서는 위해 시간복잡도 $O(N*logN)$을 갖는 Quick Sort (퀵 정렬)에 대해서 알아보았다. 이번에는 Quick Sort와 같이 시간 복잡도 $O(N*logN)$을 갖는 분할 정복식 알고리즘(DAC)인 Merge Sort (병합 정렬)에 대해 알아보도록 하.. 2021. 9. 28. Selection Sort (선택 정렬) 참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌 알고리즘에 따른 효율성을 가장 잘 보여줄 수 있는 문제가 정렬에 관한 문제이다. 이번에는 시간복잡도는 $O(N^2)$으로 느리지만 가장 단순하게 풀어 볼 수 있는 selection sort(선택정렬)에 대해서 알아본다. Selection sort는 프로그래밍이 직관적이고 쉽지만 데이터의 개수의 제곱으로 계산량이 증가하기 때문에 많은 데이터를 처리해야 하는 작업에는 적합하지는 않다. 1 10 5 8 7 6 4 3 2 9 의 숫자들이 나열되어 있을 때 이를 오름차순으로 정렬하는 프로그래밍을 작성해보자. 먼저 가장 단순하게 "가장 작은 것을 선택해서 제일 앞으로 보내"는 방법을 생각해보자. 바로 이 방법이 selection sort이다. 한번 손으로 풀어보자... 2021. 9. 27. Quick Sort (퀵 정렬) 참고자료: 유투버 동빈나 님의 실전 알고리즘 강좌 정렬방법에는 시간복잡도 $O(N^2)$ 을 갖는 Selection Sort (선택 정렬), bubble sort(버블정렬), insertion sort(삽입정렬)등이 있다. 이 방법들은 프로그래밍이 직관적이고 쉽지만 데이터의 개수의 제곱으로 계산량이 증가하기 때문에 많은 데이터를 처리해야 하는 작업에는 적합하지 않다. 이번에는 시간복잡도 $O(N*logN)$을 갖는 Quick Sort에 대해서 알아보도록 하겠다. Quick Sort는 대표적인 분할 정복식 알고리즘(Divide and Conquer Algorithm, DAC) 이라고 한다. DAC에 대해 간단히 알아보면, 1. Divide: 문제를 작은 sub-problem들로 나누는것 2. Conquer.. 2021. 9. 15. 이전 1 다음
