흰연
2022. 1. 28. 09:31
2022. 1. 28. 09:31
목차
- 기준에 따라 데이터를 정렬
- [실전 문제] 위에서 아래로
- [실전 문제] 성적이 낮은 순서로 학생 출력하기
- [실전 문제] 두 배열의 원소 교체
기준에 따라 데이터를 정렬
- 정렬(Sorting)
- 데이터를 특정한 기준에 따라서 순서대로 나열
- 이진 탐색(Binary Search)에서 사용
- 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
- 리스트를 뒤집는 연산 시간 복잡도 : O(N)
- 선택 정렬(Selection Sort)
- 매번 가장 작은 것을 선택하는 알고리즘
- 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 전체 데이터 정렬이 이루어진다.
- 시간 복잡도 : O(N^2)
- N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
- N X (N+1) / 2 = (N^2 + N) / 2 = O(N^2)
- 데이터가 늘어날 경우의 정렬 수행 시간(파이썬 기준)
- 삽입 정렬(Insertion Sort)
- 특정한 데이터를 적절한 위치에 삽입
- 그 앞의 데이터들은 이미 정렬되어 있다고 가정한다.
- 첫 번째 데이터는 그 자체로 정렬되어 있다고 생각하기 때문에 두 번째 데이터부터 시작한다.
- 시간 복잡도 O(N^2)
- 현재 리스트의 데이터가 거의 정렬되어 있는 상태일 경우 매우 빠르게 동작한다.
- 퀵 정렬(Quick Sort)
- 가장 많이 사용되는 알고리즘
- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후에 리스트를 반으로 나누는 방식으로 동작한다.
- 피벗(Pivot)이 사용되고, 다양한 분할 방법이 있다.
- 호어 분할(Hoare Partition) : 가장 대표적인 분할 방식. 리스트에서 첫 번째 데이터를 피벗으로 정한다.
- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 큰 데이터와 작은 데이터의 위치를 서로 교환해준다.
- 왼쪽과 오른쪽에서 찾는 값이 엇갈린 경우 작은 데이터와 피벗의 위치를 서로 변경해준다.
- 분할 = 파티션(Divide = Partition) : 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치하고, 피벗의 오른쪽에는 피벗보다 큰 데이터가 위치하도록 하는 작업
- 파티션이 완료된 상태에서 왼쪽 배열을 정렬 오른쪽 배열을 정렬
- (퀵 정렬 종료 조건) 현재 리스트의 데이터 개수가 1개인 경우, 이미 정렬이 되어 있다고 간주하여 분할이 불가능하다.
- 시간 복잡도 평균 : O(NlogN), 최악의 경우 : O(N^2)
- 무작위 데이터는 빠르게 동작할 확률이 높지만, 왼쪽 데이터를 피벗으로 삼을 때 이미 데이터가 정렬되어 있는 경우라면 매우 느리게 동작한다.
- 데이터 유형을 파악하기 어렵다면 퀵 정렬을 사용하는 것이 유리하다.
- 계수 정렬(Count Sort)
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘
- 데이터 개수 N, 최대 값 K
- 최악의 경우에도 수행 시간 O(N + K) 보장
- (제한 조건) 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 -> 리스트(배열)을 선언해야 되기 때문
- 0이상 100이하인 성적 데이터 정렬에 효과적이다.
- 모든 범위를 담을 수 있는 배열을 생성하고, 모든 데이터를 0으로 초기화한다.
- 데이터를 하나씩 확인하며 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시켜준다.
JAVA 정렬 라이브러리
- Arrays.sort()
- 듀얼 피봇 퀵 정렬 사용
- 시간 복잡도
- 평균 O(Nlog(N)
- 최악의 경우 O(N^2)
- Collection.sort()
- Timesort 사용
- 시간 복잡도
- 평균 O(Nlog(N))
- 최악의 경우 O(Nlog(N))
- 최선의 경우 O(N)
- 삽입 정렬을 사용하는데 O(N^2)이 나오는 이유
실전 문제 (1)
- 문제 해설
- 수의 개수가 500개 이하로 매우 적기 때문에, 모든 수는 1~100,000개이다. 어떠한 정렬 알고리즘이어도 상관 없기 때문에 가독성을 위해 기본 정렬 라이브러리를 사용한다.
실전 문제 (2)
- 문제 요약
- N 명의 학생
- 학생의 정보 - 이름, 성적
- 성적이 낮은 순서대로 학생 이름을 출력하는 프로그램
- 문제 해설
- 학생의 정보가 최대 100,000개이므로, 최악의 경우 O(NlogN)을 보장하는 알고리즘 혹은 O(N)을 보장하는 계수 정렬 사용
실전 문제 (3)
- 문제 요약
- 두 개의 배열 A, B은 N개의 원소로 구성
- 배열의 원소는 모두 자연수
- 최대 K번 바꿔치기 연산 수행 : 배열 A의 원소와 배열 B의 원소 하나를 골라서 서로 바꾸는 것
- 배열 A의 모든 원소 합의 최대값을 출력하는 프로그램
- 문제 해설
- 매번 배열 A에서 가장 작은 원소를 고르고, 배열 B에서 가장 큰 원소와 교체한다.
- 배열 A의 원소를 오름차순 정렬 후, 배열 B 원소를 내림차순 정렬한다.
- 그리고 두 배열의 원소를 가장 첫 번째 인덱스부터 비교해나간다.
- 단, 배열 A에서 가장 작은 원소 < 배열 B에서 가장 큰 원소 일 경우에만 수행