Table of Contents
할 일
- Describe linear median finding algorithm. Show that its time complexity is Θ(n).
- In hashing function, why the coefficient a should not be 0?
- Read chapter 8.4. Solve example 8.1 in the chapter. (X)
- Use the birthday dataset, do the followings:
- Put them into your unsorted array using set.
- Order them with the birth day. You should consider the following algorithms.
- Basic quick sort
Pivot X = A[0] or A[n-1] - Intelligent quick sort
Pivot X = median of A - Paranoid quick sort
Pivot X = E(Good choice) - Tuple sort
- The month comes first, and the date second
- The date comes first, and the month second
- Basic quick sort
- Compare the sorting algorithms
- 선형 중앙값 찾기 알고리즘을 설명합니다. 시간 복잡도가 Θ(n)임을 나타냅니다.
- 해싱 함수에서 계수 a가 0이 아니어야 하는 이유는 무엇입니까?
- 8.4장을 읽는다. 이 장의 예제 8.1을 풉니다. (X)
- 생일 데이터 집합을 사용하여 다음을 수행합니다:
- unsorted array using set 사용하여 정렬되지 않은 배열에 넣습니다.
- 생일을 기준으로 정렬합니다. 다음 알고리즘을 고려해야 합니다.
- Basic quick sort
피벗 X = A[0] 또는 A[n-1] - Intelligent quick sort
피벗 X = A의 중앙값 - Paranoid quick sort
피벗 X = E(좋은 선택) - Tuple sort
- 월이 첫 번째, 날짜가 두 번째
- 날짜가 먼저 오고 월이 두 번째
- Basic quick sort
- 정렬 알고리즘 비교
선형 중앙값 찾기
할 일: 선형 중앙값 찾기 알고리즘을 설명합니다. 시간 복잡도가 Θ(n)임을 나타냅니다.
일반적으로 중앙값의 정의에 따라 중앙값을 찾는다고 하면, 정렬을 해야 하기 때문에 아무리 빨라도 O(n log n)이다. 그런데 여기 n log n에 만족하지 못한 누군가가 더 빠른 중앙값 찾기 알고리즘을 만들어뒀다. 내가 만든 건 아니고, 무공 비급서처럼 전해지는 알고리즘을 공부해서 이해한 대로 설명할 뿐이다.
이 알고리즘을 이해하려면 퀵 정렬에 대해 먼저 알면 좋다. 퀵 정렬은 배열에서 pivot을 선택하고, pivot의 값을 기준으로 배열을 반으로 나누어(≠ 이등분) 반씩 부분적으로 정렬해나가는 알고리즘이다. 이 원리를 오로지 중앙값을 찾는 데에만 집중한 알고리즘이 선형 중앙값 찾기 알고리즘이다.
퀵 정렬은 정렬이기 때문에 모든 요소가 몇 번째로 와야 하는지 찾는 것과 같다. 그렇기 때문에 배열을 pivot의 좌우로 나눴을 때, 양쪽 부분 배열 모두에 대해 재귀적으로 정렬을 수행한다. 그러나 중앙값을 찾을 때는 그럴 필요가 없다. 중앙값은 항상 가운데에 있는 값이기 때문에 두 부분 배열 중 가운데에 와야 할 값이 포함된 쪽만 다시 확인하고 나머지는 냅둬도 된다. 알고리즘의 수행 과정은 다음과 같다.
- pivot을 고른다.
- pivot을 기준으로 왼쪽에는 pivot보다 작은 값, 오른쪽에는 pivot보다 큰 값을 모아 배열을 반으로 나눈다.
- 두 부분 배열의 길이와 전체 배열에서 중앙값이 위치해야 하는 인덱스를 고려해, 중앙값이 존재할 부분 배열에 대해서만 위 과정을 반복한다.
- 중앙값을 찾으면 종료한다.
위 과정대로 하면 pivot을 잘 골랐다고 할 때, 크기가 n인 배열에 대해 매 반복마다 대략 n/2으로 길이가 줄어들기 때문에 O(log n), 부분 배열의 요소를 전부 확인하기 때문에 O(n), 합쳐서 O(n log n) 시간으로 중앙값을 찾을 수 있고, 만약 pivot이 항상 남은 배열 중 최댓값 혹은 최솟값이라서 모든 요소를 확인할 수밖에 없었다고 한다면 O(n²)이다.
여기서 좀 더 개선이 가능하다. 배열의 요소를 최소 5개 이상의 개수로 묶어 중앙값의 중앙값을 찾아 그것을 pivot으로 고르면 선형 시간 내에 중앙값을 찾을 수 있다고 한다.
지금은 중앙값에 대해서만 얘기했지만, 위 방법을 응용하면 특정 인덱스의 값을 찾는 것도 가능하다.
덤 - pivot 잘 고르기
퀵 정렬과 선형 중앙값 알고리즘 모두 pivot을 잘못 고르면 시간복잡도가 최악으로 치닫는다. 잘못 고른 pivot이 문제라면 pivot을 잘 고르면 된다!
pivot을 잘 고른다는 게 무슨 말일까? pivot을 잘 고르면 어떻게 될까? 잘못 고른 pivot은 배열을 균등하게 나누지 못하고 한쪽에 너무 많은 요소가 치우치게 만든다. 반대로 말하면 잘 고른 pivot은 배열을 균등하게 나눌 수 있고, 한쪽에 너무 많은 요소가 치우치지 않게 만든다고 볼 수 있다.
여기서부터는 수업 내용을 기억하는 대로 쓰는 거라 틀린 부분이 있을 수 있다.(사유: 필기할 정신이 없을 정도로 설명이 빨랐음)
pivot을 잘 고르기 전에 먼저 전제되어야 할 것이 있다. pivot을 랜덤하게 선택할 건데, 배열의 모든 요소가 pivot으로 선택될 확률이 동일해야 한다. 그리고 잘 고른 pivot이란, 배열을 파티션했을 때 작은 쪽 부분배열의 크기가 적어도 전체 배열의 1/4보다는 크거나 같게 되고, 큰 쪽 부분배열의 크기가 3/4보다는 작거나 같게 되는 것을 말한다.
위의 전제들을 바탕으로 생각해 보자. 알고리즘의 답안에 해당하는 정렬된 배열을 기준으로, 적어도 작은 쪽이 1/4 이상은 남게 배열을 분할해야 하기 때문에 좋은 pivot은 배열의 앞에서부터 1/4 ~ 3/4 사이에 있는 pivot이다. 전체 배열의 비율로 치면 1/2이다. 배열의 모든 요소가 pivot으로 선택될 확률이 동일하기 때문에, 좋은 pivot이 선택될 확률은 전체 배열의 비율과 똑같이 1/2이다.
좋은 pivot이 선택될 확률이 1/2이라는 것은, 나쁜 pivot이 선택될 확률도 1/2이라는 말이다. 그러므로 1/2이라는 확률만 믿고 처음 랜덤하게 고른 pivot을 그대로 쓰긴 좀 그렇고, 적어도 한 번은 파티션을 해봐야 한다. 랜덤한 pivot을 골라 파티션을 한번 해보고 배열이 잘 분할되었으면 그대로 진행, 그렇지 않다면 pivot을 다시 뽑는다.
자세한 과정은 기억나지 않지만 확률적으로 pivot을 2번만 뽑아보면 무조건 좋은 pivot을 찾을 수 있다고 한다. 최악의 경우 O(n²)이 되는 것보다는 O(n)을 2번 써서 O(n log n)을 확실하게 챙기는 게 낫다고 한다.
해싱할 때 0을 곱하면 안 되는 이유
문제: 해싱 함수에서 계수 a가 0이 아니어야 하는 이유는 무엇입니까?
해시 함수 h는 다음과 같이 쓴다.
h_ab(k) = ((ak + b) mod p) mod m
여기서 a가 0이 되면 원래의 값인 k가 사라지기 때문에 a는 0이 아니어야 한다.
다양한 정렬
할 일:
- 생일 데이터 집합을 사용하여 다음을 수행합니다:
- unsorted array using set 사용하여 정렬되지 않은 배열에 넣습니다.
- 생일을 기준으로 정렬합니다. 다음 알고리즘을 고려해야 합니다.
- Basic quick sort
피벗 X = A[0] 또는 A[n-1] - Intelligent quick sort
피벗 X = A의 중앙값 - Paranoid quick sort
피벗 X = E(좋은 선택) - Tuple sort
- 월이 첫 번째, 날짜가 두 번째
- 날짜가 먼저 오고 월이 두 번째
- Basic quick sort
- 정렬 알고리즘 비교
Basic quick sort
기본적인 퀵정렬. 일정한 위치에 있는 피벗을 기준으로 값을 분류한다. 피벗은 주로 배열의 첫 번째 요소이거나, 마지막 요소이다.
이미 정렬된 배열일 경우가 최악의 경우이고, O(n^2)이다.
정렬되지 않은 배열에 대해 O(n log n)으로 정렬이 가능하다.
시간복잡도 O(n log n)
Intelligent quick sort
O(n)을 소비해 배열의 중앙값을 피벗으로 선택함으로써 균형 잡힌 파티션을 보장한다. 파티션이란, 피벗을 기준으로 분류된 배열을 의미한다. 중앙값을 찾는 알고리즘에 대한 설명은 # 선형 중앙값 찾기 문단에서 볼 수 있다.
균형 잡힌 파티션이 보장되는 건 좋지만 코드가 많이 지저분해진다고 한다.
시간복잡도 O(n) + O(n log n)
Paranoid quick sort
배열에서 피벗을 무작위로 선택하되, 좋은 것으로 고른다. 좋은 피벗은 파티션을 분할한 후 두 파티션의 크기가 모두 원래 배열의 1/4 이상, 3/4 이하가 되도록 하는 피벗이다. # 덤 - pivot 잘 고르기 문단에서의 계산에 의해, 피벗을 2번만 골라보면 반드시 좋은 피벗을 고를 수 있다. 이후는 보통 퀵정렬과 같다.
시간복잡도 O(n) + O(n log n)
Tuple sort
정렬해야 할 값을 일정한 기준에 따라 몇 개의 요소로 이루어진 튜플로 만들어 정렬한다. 퀵정렬의 변종이 아니다.
예를 들어 생일을 정렬한다면, (월, 일)의 튜플로 만들어 월별 정렬과 일별 정렬을 모두 수행하는 방식이다. 영향력이 작은 값을 기준으로 먼저 정렬해야 제대로 된 결과가 나온다. 정수를 정렬한다면 임의의 숫자로 나눈 몫과 나머지를 (몫, 나머지) 튜플로 만들어 정렬할 수 있다. 마찬가지로 영향력이 적은 나머지를 기준으로 먼저 정렬해야 제대로 정렬된다.
굳이 따진다면 멀쩡한 배열을 몇 배로 늘려서 정렬하는 꼴이니 시간복잡도는 별로라고 한다.
하지만 카운팅 정렬과 결합해서 정렬한다면 썩 괜찮은 방법이 될 수 있지 않을까? (몫, 나머지) 튜플을 예로 생각해보자. 정렬해야 할 요소들의 범위를 알고 있다면 몫의 범위도 미리 알 수 있다. 그리고 나머지는 나누는 수에 따라 달라지기 때문에 당연히 범위를 알고 있다. 카운팅 정렬은 범위를 미리 알고 있다면 선형 시간 내에 정렬할 수 있으니, 나머지로 한 번 정렬하고 몫으로 다시 정렬해봐야 2n이고, 즉 O(n)이다. 물론 값의 범위를 미리 알아야 한다는 전제가 있고, 카운팅 정렬의 단점도 감수해야 하니 한계가 있는 방법이다.
참고 자료
- 선형 시간에 중간값 구하기 (Quick-Select & Median-of-Medians), https://gazelle-and-cs.tistory.com/58
- 선형 시간 안에 중간값 선택하기, https://umbum.dev/671
- 퀵 정렬(Quick Sort)과 최악의 경우(O(N^2))를 방지하기 위한 방법들, https://blog.naver.com/ljy9378/221508655059