Ch6. 정렬
1. 기준에 따라 데이터를 정렬
1-1. 정렬 알고리즘 개요
- '정렬'
: 데이터를 특정한 기준(오름차순 또는 내림차순)에 따라서 순서대로 나열하는 것이다.
: 정렬 알고리즘으로 데이터를 정렬하고 나면 이진 탐색이 가능해진다.
1-2. 선택 정렬
- 매번 '가장 작은 것'을 '선택'한다는 의미에서 선택 정렬이다.
- 다른 알고리즘들보다 비효율적이지만 가장 작은 데이터를 찾는 경우가 많으므로 소스 코드에 익숙해질 필요가 있다.
- 소스 코드
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] #swap
print(arr)#include <stdio.h>
using namespace std;
int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
return;
}
void select_sort(int* array) {
for (int i = 0; i < n; i++) {
int min_idx = i;
for (int j = i + 1; j < n; j++) {
if (array[min_idx] > array[j]) min_idx = j;
}
swap(&array[min_idx], &array[i]);
}
}
int main() { // 선택 정렬
select_sort(arr);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
} - 시간 복잡도
: 선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해 비교 연산
을 수행해야한다. // N + (N - 1) + (N - 2) + .... + 2
따라서 시간 복잡도 O(N^2)가 걸린다.
1-3. 삽입 정렬
- 특정한 데이터를 적절한 위치에 '삽입'한다는 의미이다. 적절한 위치에 삽입되기 전에 그 앞까지의 데이터는 이미 정렬되
어 있다고 가정한다.
- 소스 코드
arr = [7,5,9,0,3,1,6,2,4,8]
for i in range(1,len(arr)):
for j in range(i, 0, -1):
if arr[j] < arr[j-1]:
arr[j], arr[j-1] = arr[j-1], arr[j];
else:
break;
print(arr)#include <stdio.h>
using namespace std;
int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
return;
}
void insert_sort(int* array) {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (array[j - 1] > array[j]) swap(&array[j], &array[j - 1]);
else break;
}
}
}
int main() { // 삽입 정렬
insert_sort(arr);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}- 시간 복잡도
: 선택 정렬과 마찬가지로 이중 for문이 사용되었기 때문에 O(N^2)의 시간 복잡도를 가진다. 그렇지만, 현재 리스트의
데이터가 거의 정렬되어 있는 상태라면 best의 경우 O(N)의 시간 복잡도를 가진다.
거의 정렬되어 있는 상태의 데이터가 들어온다면 다른 정렬 알고리즘들보다 삽입 정렬을 이용하는 것이 정답 확률을
높일 수 있다.
1-4. 퀵 정렬
- 지금까지 배운 알고리즘들 중에 가장 많이 사용되는 알고리즘들이다. 비슷한 속도를 가지는 병합 정렬 알고리즘이 있지
만 이 책에서는 나오지 않는다.
- 기준(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
- pivot을 설정하고 리스트를 분할하는 방법에 따라 여러 가지 방식으로 구분하는데 여기서는 가장 대표적인 분할 방식인
호어 방식(hoare partition)을 기준으로 퀵 정렬을 설명한다.
'호어 방식(hoare partition)'
1) 리스트의 첫번째 데이터를 pivot으로 설정하고 왼쪽에서부터 pivot보다 큰 수를, 오른쪽에서부터 pivot보다 작은
수를 작은 데이터를 찾아 찾은 두 데이터의 위치를 서로 교환해준다.
2) 교환하여 pivot의 왼쪽에는 pivot보다 작은 데이터가 위치하고, pivot의 오른쪽에 있는 피벗보다 큰 데이터가 위치
하게 되면(=partition or divide가 다 되면) 왼쪽 리스트와 오른쪽 리스트에서 각각 위 과정을 또 진행한다.
3) 분할(divide) or 파티션(partition)된 현재 리스트의 원소가 1개일 때 퀵 정렬은 끝난다.
- 소스 코드
arr = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(arr, start, end):
if start >= end: # 원소가 하나일 때
return
pivot = start
left = pivot + 1
right = end
while left <= right:
# pivot보다 큰 것을 찾을 때까지 idx 증가
while left <= end and arr[left] <= arr[pivot]:
left += 1
# pivot보다 작은 것을 찾을 때까지 idx 감소
while right > start and arr[right] >= arr[pivot]:
right -= 1
if left > right: # 5 8 7 6 4
# 엇갈렸다면 작은 arr[right]와 arr[pivot]를 교체
arr[right], arr[pivot] = arr[pivot], arr[right]
else:
# 엇갈리지 않았을 때 작은 데이터와 큰 데이터 교체
arr[left], arr[right] = arr[right], arr[left]
quick_sort(arr, start, right - 1)
quick_sort(arr, right + 1, end)
quick_sort(arr, 0, len(arr)-1)
print(arr)파이썬의 장점을 살린 퀵 정렬
arr = [5,7,9,0,3,1,6,2,4,8]
def quick_sort(arr):
if len(arr) <= 1: return arr
pivot = arr[0]
tail = arr[1:] # pivot을 제외한 list
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
sorted_arr = quick_sort(arr)
print(sorted_arr)#include <stdio.h>
using namespace std;
int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
return;
}
void quick_sort(int* array, int start, int end) {
if(start >= end) return;
int pivot = start;
int left = start + 1;
int right = end;
while(left <= right){
// pivot보다 큰 데이터를 찾을 때까지 반복
while(left <= end && array[left] <= array[pivot]) left++;
// pivot보다 작은 데이터를 찾을 때까지 반복
while(right > start && array[pivot] <= array[right]) right--;
if(left > right) swap(&array[pivot], &array[right]);
else swap(&array[left], &array[right]);
}
quick_sort(arr, start, right - 1);
quick_sort(arr, right + 1, end);
}
int main() { // 퀵 정렬
quick_sort(arr, 0, n-1);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}- 시간 복잡도
: 퀵 정렬은 평균적으로 O(NlogN)의 시간 복잡도를 가진다. (증명이 필요한데 코딩테스트와 관련 없으므로 넘어간다)
평균 시간 복잡도는O(NlogN)이지만, 최악의 경우(이미 데이터가 정렬되어 있는 경우) O(N^2)이다.
실제로 정렬 라이브러리에는 피벗값을 설정하는 추가적인 로직이 있기에 최악의 경우에도 O(NlogN)를 보장한다.
1-5. 계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
'데이터의 크기 범위가 제한되어 양의 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
ex) 0 이상 100 이하인 성적 데이터
- 계수 정렬보다 조금 느리지만 처리할 수 있는 정수의 크기는 더 큰 기수 정렬(radix sort)가 있다.
계수 정렬과 기수 정렬은 현존하는 알고리즘 중에 제일 빠르다.
- 소스 코드
arr = [7,5,9,0,3,1,6,2,9,1,4,8,0,5,2]
count = [0] * (max(arr)+1)
for i in range(len(arr)):
count[arr[i]] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 설정#include <stdio.h>
#define MAX_VALUE 9
using namespace std;
int n = 15;
int arr[15] = { 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2 };
int arrCnt[MAX_VALUE + 1];
int main() { // 계수 정렬
for (int i = 0; i < n; i++) {
arrCnt[arr[i]] += 1;
}
for (int i = 0; i <= MAX_VALUE; i++) {
for (int j = 0; j < arrCnt[i]; j++) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}- 시간 복잡도
: 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때,
계수 정렬의 시간 복잡도는 O(N+K)이다.
(앞에서부터 데이터를 확인하면서 적절한 인덱스의 값을 증가시킬 뿐만 아니라, 추후 인덱스에 해당하는 값들을
확인할 때 데이터 중 최댓값의 크기만큼 반복을 수행해야 하기 때문)
- 공간 복잡도
: 리스트의 크기가 적절하고, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 왜냐하면 데이터가 0과 999,999
단 두 개가 존재한다고 가정했을 때 리스트이 크기가 100만 개가 되도록 설정해야하기 때문이다.
: 일반적인 코딩 테스트의 시스템 환경에서는 메모리 공간상의 제약과 입출력 시간 문제로 입력되는 데이터의 개수를
1000만개 이상으로 설정하기 어렵기 때문에 1000만 개 미만으로 출제될 것이다.
1-6. 파이썬의 정렬 라이브러리
- 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. 퀵 정렬과 방식이 비슷한 병합 정렬로 만들어졌는데,
병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.
- sorted() 함수는 list나 dictionary 자료형 등을 입력받아 정렬된 결과를 리스트 자료형으로 반환한다.
- 소스 코드
arr = [7,5,9,0,3,1,6,2,4,8]
# sorted() 함수 사용하기
result = sorted(arr)
print(result)
# 리스트 객체의 내장 함수 sort() 사용하기
arr.sort()
print(arr)
# sorted()나 sort()를 이용할 때
# key를 사용하여 정렬 할 수 있다
arr = [('바나나',2), ('사과',5),('당근',3)]
def setting(data):
return data[1]
result = sorted(arr, key=setting)
print(result)#include <stdio.h>
#include <algorithm>
using namespace std;
int n = 10;
int arr[10] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
int main() {
sort(arr, arr + n);
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
return 0;
}- 시간 복잡도
: 정확하게 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하기에 항상 최악의
경우에도 O(NlogN)을 보장한다.
: 따라서 문제를 풀 때 별도의 요구가 없다면 단순히 정렬해야하는 상황에는 기본 정렬 라이브러리를 사용하고,
데이터 범위가 한정되어 있으며 더 빠르게 동작해야할 때는 계수 정렬을 사용하자.
1-7. 코딩 테스트에서 정렬 알고리즘이 사용되는 경우
1) 정렬 라이브러리로 풀 수 있는 문제
: 단순히 정렬 기법을 알고 있는지 물어보는 문제
2) 정렬 알고리즘의 원리에 대해서 물어보는 문제
: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 풀 수 있는 문제
3) 더 빠른 정렬이 필요한 문제
: 퀵 정렬 기반의 정렬 기법으로 문제를 풀 수 없으며 계수 정렬 등 다른 정렬 알고리즘을 이용하거나 문제에서 기존에
알려진 알고리즘의 구조적인 개선을 고쳐야 풀 수 있는 문제
2. 위에서 아래로
- 문제
- 문제 해결
: 수의 개수가 500개 이하로 매우 적고, 모든 수는 1 이상 100,000 이하의 자연수로 어떤 정렬 알고리즘을 사용해도
문제를 해결할 수 있다. 여기서는 가장 편한 파이썬의 기본 라이브러리를 이용하는 것이 효과적이다.
- 소스 코드
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
arr = sorted(arr, reverse=True)
for i in arr:
print(i,end=' ')#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int N = 0;
vector<int> v;
bool compare(int a, int b){
return a > b;
}
int main() {
scanf("%d", &N);
for (int i = 0; i < N; i++){
int x = 0;
scanf("%d", &x);
v.push_back(x);
}
sort(v.begin(), v.end(), compare);
for (int i = 0; i < N; i++) printf("%d ", v[i]);
printf("\n");
return 0;
}
3. 성적이 낮은 순서로 학생 출력하기
- 문제
- 문제 해결
: 학생의 정보가 최대 100,000개까지 입력될 수 있으므로 최악의 경우 O(NlogN)을 보장하는 알고리즘을 이용하거나
O(N)을 보장하는 계수 정렬을 이용하면 된다.
: 그뿐만 아니라 입력되는 데이터는 학생의 이름과 정수지만 출력할 때는 학생의 이름만 출력하면 되기 때문에
학생 정보(점수, 이름)으로 묶은 뒤에 점수를 기준으로 수행해야 한다. 따라서 이런 경우에도 -> 파이썬 기본 정렬 library
- 소스 코드
n = int(input())
list_info = []
for i in range(n):
data = input().split()
list_info.append((data[0], int(data[1])))
def setting(student):
return student[1]
list_info = sorted(list_info, key=setting)
for student in list_info:
print(student[0], end=' ')#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
class Student {
public:
string name;
int score;
Student(string name, int score) {
this->name = name;
this->score = score;
}
bool operator < (Student &other) {
return this->score < other.score;
}
};
int N;
vector<Student> v;
int main() {
cin >> N;
// scanf로 문자열을 받으려면 char[30] str 이런 형식이어야 한다.
for (int i = 0; i < N; i++){
string name;
int score;
cin >> name >> score;
v.push_back(Student(name, score));
}
sort(v.begin(), v.end());
for (int i = 0; i < N; i++) {
cout << v[i].name << " ";
}
cout << endl;
return 0;
}4. 두 배열의 원소 교체
- 문제
- 문제 해결
: 기본 아이디어는 매번 배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다.
(단, 배열 A에서 가장 작은 원소가 배열 B에 있는 가장 큰 원소보다 작을 때에만 교체를 해야한다)
: 배열 A의 원소를 오름차순으로 정렬하고, 배열 B의 원소를 내림차순으로 설정한다. 두 배열의 원소를 가장 첫 번째 인덱스
부터 차례대로 비교하면서 A의 원소가 B의 원소보다 작을 때 교체를 수행한다.
: 두 배열의 원소가 100,000개 까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬 알고리즘을 이용해야 한다.
- 소스 코드
n, k = map(int,input().split())
arrA = list(map(int,input().split()))
arrB = list(map(int,input().split()))
arrA.sort()
arrB.sort(reverse=True)
for i in range(k):
if arrA[i] < arrB[i]:
arrA[i], arrB[i] = arrB[i], arrA[i]
else:
break;
print(sum(arrA))#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
vector<int> a, b;
bool compare(int x, int y) {
return x > y;
}
int main() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
a.push_back(x);
}
for (int i = 0; i < N; i++) {
int x;
cin >> x;
b.push_back(x);
}
sort(a.begin(), a.end()); // 배열 A는 오름차순 정렬 수행
sort(b.begin(), b.end(), compare); // 배열 B는 내림차순 정렬 수행
for (int i = 0; i < K; i++) {
if (a[i] < b[i]) swap(a[i], b[i]);
else break;
}
long long result = 0;
for (int i = 0; i < N; i++) {
result += a[i];
}
cout << result << endl;
return 0;
}'Algorithm&Problem > [Algorithm] 이.코.테.다' 카테고리의 다른 글
| [문제실습] Ch 6. Sort (0) | 2021.02.07 |
|---|---|
| [문제실습] Ch 3. 그리디(greedy) (0) | 2021.01.23 |
| [6일차] 이.코.테.다! Ch5 DFS/BFS (0) | 2020.09.22 |
| [5일차] 이.코.테.다! Ch4 구현 Implementation (0) | 2020.09.20 |
| [4일차] 이.코.테.다! Ch3 그리디 greedy (0) | 2020.09.16 |