목차
1. 퀵 정렬
2. 퀵 정렬 실전 문제
3. 병합 정렬
4. 병합 정렬 실전 문제
출처
Do it! 알고리즘 코딩테스트 with Python
1. 퀵 정렬
기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬
평균 시간복잡도 : O(nlogn)
최악 시간복잡도 : O(n²)
설명 : 기준값을 피벗으로 두고 남은 범위에서 한쪽은 큰값, 한쪽은 작은값으로 swap하며 반복진행 후 마지막 남은 값을 기준에 맞게 피벗과 swap하는 과정을 반복
2. 퀵 정렬 실전 문제
https://www.acmicpc.net/problem/11004
1
3. 병합 정렬
분할정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하여 합침
시간복잡도 : O(nlogn)
설명 : 그룹으로 나눠 각 그룹마다 정렬진행 후 가까운 그룹끼리 다시 그룹을 만들어 정렬하는 과정을 반복 (예를들어 오름차순 정렬하는 경우 정렬된 두 그룹끼리 병합하는 과정은 두 그룹중 작은값을 저장하는 과정을 반복하는 방식으로 병합)
4. 병합 정렬 실전 문제
4.1
https://www.acmicpc.net/problem/1517
2
4.2
https://www.acmicpc.net/problem/2751
3
'파이썬 코딩테스트' 카테고리의 다른 글
알고리즘 스터디 7일차 (0) | 2023.08.20 |
---|---|
알고리즘 스터디 6일차 (0) | 2023.08.20 |
알고리즘 스터디 4일차 (0) | 2023.08.19 |
알고리즘 스터디 3일차 (0) | 2023.08.17 |
알고리즘 스터디 2일차 (0) | 2023.08.15 |