이번 장에서는 선택 알고리즘에 대해서 알아보고 실증적인 코드를 직접짜보고 연습문제도 공부하는 시간을 갖겠습니다.
슈도코드말고 진짜 코드를 보고싶다면?
01 평균 선형 시간 선택 알고리즘
정렬을 공부하다보면 이런 생각이 자연스럽게 들기 마련이다. 일렬로 메모리에 저장된 데이터 내에서 i 번째 데이터를 찾는 시간이 얼마나 걸릴까? O-표기법으로 최소한의 시간은 무엇일까? 당장 생각해보면 어쨋든 O(n) 밑으로 낮아 질 수 없을것이다. 왜냐하면, 적어도 한번씩은 지나쳐야 어떠한 원소가 큰지 작은지 알 수 있기 때문이다. 앞서 배운 정렬 알고리즘들 중에서 가장 효율이 안좋았던 알고리즘들의 O-표기법은 O(n^2) 였다. 그럼 우리는 직관적으로 O(n) ~ O(n^2)사이에 있다고 자연스럽게 생각하게되고 대부분 O(nlogn)으로 결론이 지어진다. 하지만 놀랍게도 우리는 O(n)으로 i 번째 원소를 찾을 수 있다. 이러한 직관과 벗어나는 빠른 알고리즘을 찾거나 이용하는것이 우리가 알고리즘을 공부하는 즐거움이다.
O(n)으로 i 번째로 크거나 작은 데이터를 찾을 수 있다고? 정렬보다 빠를 수 있다고? 힌트는 우리가 배웠던 퀵 정렬에 있다!
위의 움짤을 보고있으면 기준점을 찾고 그것을 기준으로 왼쪽으로 기준보다 작은것을 몰아넣고 오른쪽으로 그것보다 큰것을 몰아넣고 다시 기준점을 정하고 같은 방법으로 나누는 것을 반복하고 있다. 이것을 우리가 i 번째 데이터를 찾는데 사용한다면 O(n)의 시간을 만족 시킬 수 있다. 슈도코드를 먼저보고 어떻게 이런일이 가능한지 알아보자.
select(A, p, r, i)
{
if(p = r) then return (A[p]);
q = partition(A, p, r);
k = q - p + 1;
if (i < k) then return select(A, p, q - 1, i);
else if (i = k) then return (A[q]);
else return select(A, q+1, r, i - k);
}
// 평균 선형 시간 선택 알고리즘
JavaScript
복사
select 함수를 설명하자면 A배열에 p부터 r까지 원소중 i 번째 원소를 찾는 알고리즘이다. p = r이 같다는것은 정확하게 하나의 데이터를 가리키고 있다는 이야기이므로 (원소가 하나뿐인 경우) 해당 원소를 결과값으로 반납한다. partition 함수는 우리가 배웠던 퀵소트의 partition 함수와 정확하게 같다. 원소가 여러개인 경우는 partition함수를 통해 범위를 계속해서 줄여나간다. q 값으로 기준값이 어디에 저장되었는지 리턴해준다. 위의 움짤에서 보듯이 그 기준값을 기준으로 배열이 나눠졌다. 그리고 q - p + 1 (기준점위치 - 시작점 + 1)을 계산해서 기준점이 배열에서 k번째에 있다는것을 알 수 있다. i(우리가 찾고싶은 원소의 순위)와 k를 비교해서 나눠진 배열에서 왼쪽 부분에서 찾아야할지 혹은 오른쪽에서 찾아야할지 혹은 기준점이 i번째 원소인지를 비교한다. 그에 따라서 다시 select를 실행시켜 비교하는 부분을 계속해서 줄여준다. 따라서 시간복잡도를 생각해보면 최상의 경우 반씩 계속 줄어드므로 O(n)인것을 알 수있지만, 최악의 경우는 O(n^2)인것을 알 수 있다.
clrs에 따르면 이러한 복잡한 수식을 따지면 그러한 결과가 나온다고 한다. 관심이 생기면 chapter 9을 참고하면 좋을거 같다.
최악의 경우는 무엇일까? 최악의 경우는 기준점이 항상 끝으로 오는 경우다 혹은 끝과 아주 가까운 쪽으로 되는것이다. 그러면 배열을 나누는 의미가 없어지기때문이다. 필자가 대학원에 진학중일때 기초 알고리즘 수업에서 해당 문제를 랜덤(기준을 정할때 랜덤 인자를 삽입해서 이미 정렬된 배열의 최악의 시간 복잡도를 예방한다.)으로 해결한 알고리즘과 잘게나눠서 해결한 알고리즘을 공부 하여서 이번엔 잘게나눠서 해결한 알고리즘을 소개하려고한다.
02 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘
앞서 말해듯이 partition하는 과정에서 일정 상수비 이상의 큰그룹을 계속해서 탐색하면 O(n^2)의 시간 복잡도를 갖게된다. 이런한 일이 발생하는 경우는 다행히도 아주 적지만 그럼에도 큰 배열이 이미 정렬되어있는 경우는 어쩔 수 없이 이러한 일이 발생하게 된다. 따라서 일반적인 partition이 아닌 알고리즘을 고안해낸다면 효율적으로 해결 할 수 있다. 예를 들면, 랜덤으로 기준점을 정하거나 잘게 나누는 것이다.
문제는 계속해서 큰그룹에 속해서 그 안에서 계속해서 그룹을 나누는 것이다. 애초에 동등한 크기의 그룹을 가질 수만 있다면 문제가 사라진다.
슈도코드를 통해 어떻게 잘게 나눌수 있는지 알아보자. 다른 알고리즘들도 많으니 해당 알고리즘들을 공부하는것도 상당히 도움이 된다.
linearSelection(A, p, r, i)
{
1. 원소의 총수가 5개 이하이면 i번째 원소를 찾고 알고리즘을 끝낸다.
2. 전체 원소를 5개씩의 원소를 가진 n/5개의 그룹으로 나눈다.
(5개로 딱 나눠지지 않으면 1개가 추가된다.)
3. 각 그룹에서 중앙값을 찾는다. (5개라면 3번째 원소) 이렇게 중앙값들을 m이라고 하자.
4. m들의 중앙값(M)을 재귀적으로 구한다.
홀수면 한개가 찾아지고 짝수면 두개이지만 아무거나 선택해도 알고리즘에 영향은 없다.
5. M을 기준으로 partition함수를 실행시킨다.
6. 해당 분할을 기준으로 i 번째를 찾는다.
}
JavaScript
복사
이렇게 선택된 M은 어찌되었든 무조건 저 회색으로 색칠된 범위의 원소들보다는 무조건적으로 작게되어있다. 우리가 잘게 그룹으로 나눈 후에 그 그룹들의 중앙값의 중앙값을 찾아버리면 저 회색 부분의 원소는 무조건 적으로 위의 사실을 보장한다. 그 외의 원소들은 작은지 큰지 알 수 없다. 중요한것은 우리가 partition 함수의 기준을 일정부분 5:5와 비슷하게 자를 수 있다는것이다. 최악의 경우 우리는 약 7 : 3으로 자르게 된다. 이 경우는 저 회색부분 바로 위에 있는 것들이 전부 M보다 작은 경우이다. 하지만 그럼에도 O(n^2)되는 상수비보다는 훨씬 크다. 따라서 O(n)의 시간복잡도를 보장한다.
수학적인 증명은 이러하다. 관심있으면 clrs를 찾아보자!
정리
우리는 놀랍게도 i 번째 원소를 선택하는 시간이 선형적인 시간 O(n)이 걸린다는 사실을 알아냈고 해당 알고리즘을 구현했다. 그러나 최악의 경우 O(n^2)가 걸리는 것을 알게되었고 따라서 그것을 해결하는 방법으로 partition을 진행할때 일정 상수비 이상으로 분할이되는 알고리즘을 소개했다. 이에 따른 수학적인 증명도 완료했다. 다음 포스트는 검색트리에 관한 포스팅이 될것이니 기대 부탁드린다.
연습 문제
01 정렬을 이용해 배열 A[1 ... n]에서 i 번째 작은 원소를 찾는 방법을 설명하시오.
02 배열 A[1 ... 7]이 <8, 3, 5, 9, 2, 6, 4>로 구성되어 있을 경우 select() 알고리즘을 이용해 5번째 작은 수를 찾는 과정을 따라가보시오. 즉, select(A, 1, 7, 5)가 수행되는 과정을 그리시오.
03 1절의 알고리즘 select가 수행되는 과정에 길이가 0인 배열이 호출되는 경우가 발생할 수 있는가?
04 1절의 알고리즘에서 분할은 기준원소보다 작거나 같은 원소는 왼쪽 그룹에, 기준원소 보다 큰원소는 오른쪽 그룹에 속하도록 분할한다. 이 분할 알고리즘을 조금 바꾸어 기준원소보다 작은것은 왼쪽 그룹에, 크거나 같은 것은 오른쪽 그룹에 속하도록 해본다. 이렇게 하면 1절의 알고리즘 select()는 제대로 작동하는가?
05 04번 문제에서 분할 알고리즘을 기준원소보다 작거나 같은 것으 왼쪽 그룹에, 크거나 같은 것은 오른쪽 그룹에 속하도록 바꾸어본다. 즉, 기준원소와 같은 원소는 왼쪽이나 오른쪽 그룹에 임의로 속할 수 있도록 한다. 이렇게 하면 알고리즘은 제대로 작동하는가?
06 1절의 select 알고리즘에서 partition()의 수행 결과로 항상 1:9로 분할되고, 불행히도 항상 오른쪽의 그룹이 선택된다고 하더라도 알고리즘의 점근적 수행 시간은 O(n)이 됨을 보이시오.
07 06번 문제에서 1:9 대신 1:99로 분할되고 항상 오른쪽의 그룹이 선택된다고 하더라도 점근적 수행 시간은 O(n)이 됨을 보이시오.
08 2절의 linearSelect 알고리즘에서 5개짜리 그룹으로 나누었다. 이것을 5개 대신 7개짜리 그룹으로 나누어도 여전히 선형 시간에 찾는가? 또 9개짜리 그룹으로 나누면 어떻게 되는가?
09 2절의 linearSelect 알고리즘을 이번에는 3개짜리 그룹으로 나누어도 선형시간에 찾을 수 있는가?
10 1절의 select 알고리즘과 2절의 linearSelect 알고리즘은 많은 부분을 공유한다. 두 알고리즘은 어떤 점이 같고, 어떤 점이 다른가?
11 다음은 본문에서 배운 linearSelect() 알고리즘을 변형한 것이다. 이 알고리즘의 최악의 경우 수행 시간을 O-표기로 밝히고 증명하시오.
linearSelection(A, p, r, i)
{
1. 원소의 총수가 8개 이하이면 i번째 원소를 찾고 알고리즘을 끝낸다.
2. 전체 원소를 8개씩의 원소를 가진 n/8개의 그룹으로 나눈다.
(8개로 딱 나눠지지 않으면 1개가 추가된다.)
3. 각 그룹에서 중앙값을 찾는다. (8개라면 4번째 원소) 이렇게 중앙값들을 m이라고 하자.
4. m들의 중앙값(M)을 재귀적으로 구한다.
홀수면 한개가 찾아지고 짝수면 두개이지만 아무거나 선택해도 알고리즘에 영향은 없다.
5. M을 기준으로 partition함수를 실행시킨다.
6. 해당 분할을 기준으로 i 번째를 찾는다.
}
JavaScript
복사
12 11번 문제의 8개원소를 7개로 바꾸고 중앙값이 아닌 3번째 원소로 바꾼다면 그럼에도 선형시간인가?
13 퀵 정렬의 최악의 시간 O(n^2)를 O(nlogn)으로 바꾸는 방법을 생각해보자.
