Part2 주요 알고리즘 이론과 실전문제의 Chapter6 정렬을 공부할 시간이다. 7월-12월간의 교육이 끝나고 이제부터 취업전선에 뛰어들기 전에 코딩테스트 실력을 갈고닦기 위해 다시 [이것이 코딩테스트다]로 공부중이다. 이번주에는 Part2 1회독을 한 후에 다음주부터 실전문제를 풀 예정이다. 그리고 1회독을 한 것을 기반으로 다시 머릿속으로 정리하려고 블로그에 포스팅 한다.
1. 정렬
- 정렬 : 데이터를 특정간 기준에 따라서 순서대로 나열하는 것
- 종류와 시간복잡도
| |
내용 |
시간복잡도 |
선택 정렬
(Selection Sort) |
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복
|
O(N제곱) |
삽입 정렬
(Insetion Sort) |
- 특정한 데이터를 적절한 위치에 '삽입'
- 보통은 비효율적이지만 정렬이 거의 되어있는 상황에서는 퀵정렬 알고리즘보다 더 강력
|
O(N제곱) |
퀵 정렬
(Quick Sort) |
- 가장 많이 사용되는 알고리즘
- 참고로 퀵정렬 만큼 빠른 정렬은 병합정렬이 존재
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 변경
|
평균 : O(NlogN)
최악 : O(N제곱) |
계수 정렬
(Count Sort) |
- 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 데이터 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 수행 시간 O(N+K)를 보장
- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적
- 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 하기 때문에 위와 같은 특징이 있음.
|
O(N+K) |
| 파이썬 라이브러리 |
- 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공
- 병렬 정렬을 기반으로 만들어짐 => 정확하게는 병합정렬과 삽입정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘
- 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있음.
|
O(NlogN) |
- 문제 파악법
- 별도의 요구사항 없이 정렬해야하는 상황 -> 기본 정렬 라이브러리 사용
- 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬 사용
- 정렬 알고리즘의 원리에 대해 물어보는 문제 -> 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고있어야함.
2. 정렬 유형의 알고리즘 문제
- 실전문제 위에서 아래로
- 실전문제 성적이 낮은 순서로 학생 출력하기
- 실전문제 두 배열의 원소 교체
- Q 23 국영수
- Q 24 안테나
- Q 25 실패율
- Q 26 카드 정렬하기
