순서통계량(Order Statistic)
17 Oct 2017 | Algorithm
이번 글에서는 순서통계량(order statistic)을 구현하는 알고리즘을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
순서통계량이란 $n$개 표본의 측정값들을 그 크기 순으로 작은 쪽부터 배열한 것을 가리킵니다. 최소값, 최대값, 중앙값(median), 4분위수(quantile) 등이 대표적인 순서통계량입니다. $i$번째 순서통계량은 $n$개 요소 가운데 $i$번째로 작은 값을 가리킵니다. 따라서 최소값은 $i$가 1, 최대값은 $i$가 $n$이 됩니다. $n$이 홀수인 경우에 중앙값의 $i$는 $(n+1)/2$, 짝수인 경우 $n/2$입니다.
순서통계량을 가장 확실하게 구하는 방법은 모든 요소를 정렬하는 것입니다. 카운팅 정렬(counting sort) 같은 일부 특이한 알고리즘을 제외하면, 대부분의 정렬 알고리즘은 두 값을 반복적으로 비교해 정렬 작업을 수행하는 comparison sort입니다. comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. (자세한 내용은 이곳 참고) 다시 말해 힙 정렬이나 합병 정렬 같은 $O(n\log{n})$의 알고리즘으로 전체 요소를 정렬해 놓으면 순서통계량 또한 구할 수 있다는 이야기입니다.
하지만 최소값, 최대값, 중앙값만을 알고자 할 때 요소 전체를 정렬할 필요까지는 없습니다. 바꿔 말해 순서통계량을 구하는 알고리즘이 목표로 하는 계산복잡성은 $O(n)$이라는 것입니다.
최대값(최소값)
최대값을 구하는 가장 간단한 알고리즘은 이렇습니다. 우선 max라는 변수를 만들고, 이 변수에 첫번째 표본의 값을 집어 넣습니다. 그리고 나머지 $n-1$개 표본과 max 변수값을 반복적으로 비교해 큰 값을 다시 max에 저장합니다. 따라서 $n-1$회 비교하게 되면 $n$개 표본 가운데 최대값을 뽑아낼 수 있습니다. 따라서 이 알고리즘의 계산복잡성은 $O(n)$이 됩니다. 최소값은 여기에서 작은 값을 취하는 것 말고는 동일한 과정을 거칩니다.
파이썬으로 구현한 코드는 다음과 같습니다.
def maximum(list):
max = list[0]
for i in list:
if max < i:
max = i
return max
최대값과 최소값 동시에 구하기
최대값을 구하는 데 $n-1$회, 최소값을 구하는 데에도 $n-1$회 비교 연산을 수행해야 합니다. 따라서 최대값과 최소값을 동시에 구하려면 $2n-2$회 비교를 해야 합니다. 이보다 더 낮출 수는 없을까요? 방법이 있습니다. 예컨대 다음과 같은 리스트를 정렬한다고 칩시다.
[1, 4, 10, 6, 3, 2]
우선 출력변수 result를 초기화합니다. result 첫번째 요소엔 최소값, 두번째 요소엔 최대값을 저장할 예정입니다.
result=(False, False)
정렬 대상 숫자를 순서대로 두 개씩 묶어 소그룹으로 만든 다음 두 개 숫자를 비교합니다. 큰 값을 왼쪽에, 작은 값을 오른쪽에 둡니다.
compare [1, 4] ==> [1, 4]
compare [10, 6] ==> [6, 10]
compare [3, 2] ==> [2, 3]
첫번째 소그룹의 왼쪽 값을 result 첫번째 요소, 오른쪽 값을 두번째 요소에 저장합니다.
result=(1, 4)
두번째 소그룹의 왼쪽 값(6), result의 기존 왼쪽 값(1)을 비교합니다. 작은 값을 result의 왼쪽에 저장합니다. 두번째 소그룹의 오른쪽 값(10), result의 기존 오른쪽 값(4)을 비교합니다. 큰 값을 result의 오른쪽에 저장합니다.
$\min(1,6)$, $max(4,10)$
result=(1,10)
마지막으로 세번째 소그룹의 왼쪽 값(2), result의 기존 왼쪽 값(1)을 비교합니다. 작은 값을 result의 왼쪽에 저장합니다. 세번째 소그룹의 오른쪽 값(3), result의 기존 오른쪽 값(4)을 비교합니다. 큰 값을 result의 오른쪽에 저장합니다.
$\min(1,2)$, $max(10,3)$
result=(1,10)
위 방법의 계산복잡성은 다음과 같은 세 가지 단계로 나누어 생각해볼 수 있습니다.
- 두 개 숫자씩 소그룹으로 나누고 두 숫자 비교
- 최소값 찾기 : 소그룹의 왼쪽값과 result의 왼쪽값 비교
- 최대값 찾기 : 소그룹의 오른쪽값과 result의 오른쪽값 비교
데이터가 $n$개 있을 때 1번 과정에서 비교 연산의 횟수는 $n/2$회입니다. 2번 과정과 3번 과정도 각각 $n/2$회가 됩니다. 따라서 전체적으로는 $1.5n$회 비교 연산을 수행하면 됩니다. 기존 $2n-2$회에서 그 연산의 횟수를 줄인 셈입니다. (물론 Big-O notation 상으로는 둘 모두 $O(n)$으로 같습니다)
i번째 작은 값 구하기
$n$개의 숫자 가운데 $i$번째 작은 값은 퀵 정렬(quick sort)을 활용해 효과적으로 구할 수 있습니다. 퀵 정렬은 분기의 기준이 되는 피봇(pivot)값 $k$를 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽 리스트로 분기합니다. 이후 분기된 두 리스트 각각에 퀵 정렬을 재귀적으로 수행해 정렬을 완료하는 구조입니다.
그러면 분석 대상 리스트가 $n$개 숫자로 구성돼 있고 피봇보다 큰 값들이 $a$개, 작은 값들이 $b$개라고 칩시다. 우리는 정렬이 아니라 $i$번째 작은 값을 찾는 데에만 관심이 있으므로, $a$가 $i$보다 크다면 $b$개에 대해선 계산할 필요가 전혀 없습니다. 다시 말해 피봇값 $k$보다 작은 값들의 개수($a$)가 $i$개 이상이라면 우리가 찾는 $i$번째 작은 값은 이들 중 하나일 것입니다. 따라서 $k$보다 큰 $b$개의 숫자에 대해선 계산하지 않아도 됩니다.
이를 파이썬으로 구현한 코드는 다음과 같습니다.
# i번째(query) 작은 숫자 찾기
def select(ARRAY, query):
# query가 ARRAY의 수보다 크면 에러 출력
if query > len(ARRAY):
print('query error')
else:
ARRAY_LENGTH = len(ARRAY)
if ARRAY_LENGTH <= 1:
return ARRAY[0]
else:
# 피봇을 기준으로 기존 리스트 분리
LESSOR, PIVOT, GREATER = partition(ARRAY)
# query가 LESSOR 다음 index와 일치하면
# i번째 작은 숫자는 바로 피봇값
if query == len(LESSOR):
return PIVOT
# query가 LESSOR 개수보다 작으면
# GREATER는 버리고 LESSOR 안에서만 탐색
elif query < len(LESSOR):
return select(LESSOR, query)
# query가 LESSOR 개수보다 크면
# LESSOR는 버리고 GREATER 안에서만 탐색
else:
return select(GREATER, query)
# quick_sort algorithm 일부 변경
def partition(ARRAY):
ARRAY_LENGTH = len(ARRAY)
if ARRAY_LENGTH <= 1:
return ARRAY
else:
# 피봇은 입력데이터의 마지막 요소
PIVOT = ARRAY[-1]
GREATER = [ element for element in ARRAY[:-1] if element > PIVOT ]
LESSER = [ element for element in ARRAY[:-1] if element <= PIVOT ]
return LESSER, PIVOT, GREATER
정렬 대상 리스트가 $n$개 숫자이고 피봇보다 큰 값들이 $a$개, 작은 값들이 $b$개라면 퀵 정렬의 계산복잡성은 다음과 같이 쓸 수 있습니다.
\[T\left( n \right) =T\left( a \right) +T\left( b \right) +O\left( n \right)\]
위 식 우변 마지막 항이 $O(n)$이 되는 이유는 피봇값 $k$와 리스트의 나머지 $n-1$개 요소 간 비교 연산을 수행해야 하기 때문입니다. 그런데 우리는 정렬이 목표가 아니므로 $k$보다 큰 $b$개의 숫자에 대해선 계산하지 않아도 됩니다. 따라서 $i$번째 작은 값을 구하는 알고리즘의 계산복잡성은 다음과 같이 쓸 수 있습니다.
\[T\left( n \right) =T\left( a \right) +O\left( n \right)\]
이 알고리즘의 계산복잡성은 피봇을 어떻게 선택하느냐에 따라 달라집니다. 피봇값을 잘못 선택해 매 분기 때마다 아래 그림처럼 이뤄질 경우 각 층에서 피봇값과 리스트의 나머지 요소($k$번 분기시 $n-k$번) 간 비교연산을 수행하고, 이를 높이($n$)만큼 반복 수행해야 하므로 $O(n^2)$의 계산복잡성을 가지게 됩니다.
반대로 피봇을 잘 선택해 매번 분기 때마다 절반씩 나눌 수 있게 되면 $i$번째 작은 값을 구하는 알고리즘의 계산복잡성은 $O(n)$이 됩니다. 아래 점화식 형태의 계산복잡성 식이 $O(n)$이 되는 이유에 대해서는 이곳을 참고하시면 좋을 것 같습니다.
\[T\left( n \right) =T\left( n/2 \right) +O\left( n \right) \\ \Rightarrow O\left( n \right)\]
pivot을 적절히 선택하기
따라서 $i$번째 작은 값을 찾는 문제를 선형 시간 내에 풀려면 피봇을 적절히 선택해 주어야 합니다. 이와 관련해 아래 그림 같은 아이디어도 있습니다. 방법은 이렇습니다. 전체 데이터를 몇 개 그룹으로 나눕니다. 해당 그룹에서 중앙값을 찾습니다. 여기서 다시 중앙값을 택합니다. 이를 피봇 삼아 분기를 수행하는 것입니다.
이번 글에서는 순서통계량(order statistic)을 구현하는 알고리즘을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아를 참고해 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concepts
순서통계량이란 $n$개 표본의 측정값들을 그 크기 순으로 작은 쪽부터 배열한 것을 가리킵니다. 최소값, 최대값, 중앙값(median), 4분위수(quantile) 등이 대표적인 순서통계량입니다. $i$번째 순서통계량은 $n$개 요소 가운데 $i$번째로 작은 값을 가리킵니다. 따라서 최소값은 $i$가 1, 최대값은 $i$가 $n$이 됩니다. $n$이 홀수인 경우에 중앙값의 $i$는 $(n+1)/2$, 짝수인 경우 $n/2$입니다.
순서통계량을 가장 확실하게 구하는 방법은 모든 요소를 정렬하는 것입니다. 카운팅 정렬(counting sort) 같은 일부 특이한 알고리즘을 제외하면, 대부분의 정렬 알고리즘은 두 값을 반복적으로 비교해 정렬 작업을 수행하는 comparison sort입니다. comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. (자세한 내용은 이곳 참고) 다시 말해 힙 정렬이나 합병 정렬 같은 $O(n\log{n})$의 알고리즘으로 전체 요소를 정렬해 놓으면 순서통계량 또한 구할 수 있다는 이야기입니다.
하지만 최소값, 최대값, 중앙값만을 알고자 할 때 요소 전체를 정렬할 필요까지는 없습니다. 바꿔 말해 순서통계량을 구하는 알고리즘이 목표로 하는 계산복잡성은 $O(n)$이라는 것입니다.
최대값(최소값)
최대값을 구하는 가장 간단한 알고리즘은 이렇습니다. 우선 max라는 변수를 만들고, 이 변수에 첫번째 표본의 값을 집어 넣습니다. 그리고 나머지 $n-1$개 표본과 max 변수값을 반복적으로 비교해 큰 값을 다시 max에 저장합니다. 따라서 $n-1$회 비교하게 되면 $n$개 표본 가운데 최대값을 뽑아낼 수 있습니다. 따라서 이 알고리즘의 계산복잡성은 $O(n)$이 됩니다. 최소값은 여기에서 작은 값을 취하는 것 말고는 동일한 과정을 거칩니다.
파이썬으로 구현한 코드는 다음과 같습니다.
def maximum(list):
max = list[0]
for i in list:
if max < i:
max = i
return max
최대값과 최소값 동시에 구하기
최대값을 구하는 데 $n-1$회, 최소값을 구하는 데에도 $n-1$회 비교 연산을 수행해야 합니다. 따라서 최대값과 최소값을 동시에 구하려면 $2n-2$회 비교를 해야 합니다. 이보다 더 낮출 수는 없을까요? 방법이 있습니다. 예컨대 다음과 같은 리스트를 정렬한다고 칩시다.
[1, 4, 10, 6, 3, 2]
우선 출력변수 result를 초기화합니다. result 첫번째 요소엔 최소값, 두번째 요소엔 최대값을 저장할 예정입니다.
result=(False, False)
정렬 대상 숫자를 순서대로 두 개씩 묶어 소그룹으로 만든 다음 두 개 숫자를 비교합니다. 큰 값을 왼쪽에, 작은 값을 오른쪽에 둡니다.
compare [1, 4] ==> [1, 4]
compare [10, 6] ==> [6, 10]
compare [3, 2] ==> [2, 3]
첫번째 소그룹의 왼쪽 값을 result 첫번째 요소, 오른쪽 값을 두번째 요소에 저장합니다.
result=(1, 4)
두번째 소그룹의 왼쪽 값(6), result의 기존 왼쪽 값(1)을 비교합니다. 작은 값을 result의 왼쪽에 저장합니다. 두번째 소그룹의 오른쪽 값(10), result의 기존 오른쪽 값(4)을 비교합니다. 큰 값을 result의 오른쪽에 저장합니다.
$\min(1,6)$, $max(4,10)$
result=(1,10)
마지막으로 세번째 소그룹의 왼쪽 값(2), result의 기존 왼쪽 값(1)을 비교합니다. 작은 값을 result의 왼쪽에 저장합니다. 세번째 소그룹의 오른쪽 값(3), result의 기존 오른쪽 값(4)을 비교합니다. 큰 값을 result의 오른쪽에 저장합니다.
$\min(1,2)$, $max(10,3)$
result=(1,10)
위 방법의 계산복잡성은 다음과 같은 세 가지 단계로 나누어 생각해볼 수 있습니다.
- 두 개 숫자씩 소그룹으로 나누고 두 숫자 비교
- 최소값 찾기 : 소그룹의 왼쪽값과 result의 왼쪽값 비교
- 최대값 찾기 : 소그룹의 오른쪽값과 result의 오른쪽값 비교
데이터가 $n$개 있을 때 1번 과정에서 비교 연산의 횟수는 $n/2$회입니다. 2번 과정과 3번 과정도 각각 $n/2$회가 됩니다. 따라서 전체적으로는 $1.5n$회 비교 연산을 수행하면 됩니다. 기존 $2n-2$회에서 그 연산의 횟수를 줄인 셈입니다. (물론 Big-O notation 상으로는 둘 모두 $O(n)$으로 같습니다)
i번째 작은 값 구하기
$n$개의 숫자 가운데 $i$번째 작은 값은 퀵 정렬(quick sort)을 활용해 효과적으로 구할 수 있습니다. 퀵 정렬은 분기의 기준이 되는 피봇(pivot)값 $k$를 기준으로 작은 값들은 왼쪽, 큰 값들은 오른쪽 리스트로 분기합니다. 이후 분기된 두 리스트 각각에 퀵 정렬을 재귀적으로 수행해 정렬을 완료하는 구조입니다.
그러면 분석 대상 리스트가 $n$개 숫자로 구성돼 있고 피봇보다 큰 값들이 $a$개, 작은 값들이 $b$개라고 칩시다. 우리는 정렬이 아니라 $i$번째 작은 값을 찾는 데에만 관심이 있으므로, $a$가 $i$보다 크다면 $b$개에 대해선 계산할 필요가 전혀 없습니다. 다시 말해 피봇값 $k$보다 작은 값들의 개수($a$)가 $i$개 이상이라면 우리가 찾는 $i$번째 작은 값은 이들 중 하나일 것입니다. 따라서 $k$보다 큰 $b$개의 숫자에 대해선 계산하지 않아도 됩니다.
이를 파이썬으로 구현한 코드는 다음과 같습니다.
# i번째(query) 작은 숫자 찾기
def select(ARRAY, query):
# query가 ARRAY의 수보다 크면 에러 출력
if query > len(ARRAY):
print('query error')
else:
ARRAY_LENGTH = len(ARRAY)
if ARRAY_LENGTH <= 1:
return ARRAY[0]
else:
# 피봇을 기준으로 기존 리스트 분리
LESSOR, PIVOT, GREATER = partition(ARRAY)
# query가 LESSOR 다음 index와 일치하면
# i번째 작은 숫자는 바로 피봇값
if query == len(LESSOR):
return PIVOT
# query가 LESSOR 개수보다 작으면
# GREATER는 버리고 LESSOR 안에서만 탐색
elif query < len(LESSOR):
return select(LESSOR, query)
# query가 LESSOR 개수보다 크면
# LESSOR는 버리고 GREATER 안에서만 탐색
else:
return select(GREATER, query)
# quick_sort algorithm 일부 변경
def partition(ARRAY):
ARRAY_LENGTH = len(ARRAY)
if ARRAY_LENGTH <= 1:
return ARRAY
else:
# 피봇은 입력데이터의 마지막 요소
PIVOT = ARRAY[-1]
GREATER = [ element for element in ARRAY[:-1] if element > PIVOT ]
LESSER = [ element for element in ARRAY[:-1] if element <= PIVOT ]
return LESSER, PIVOT, GREATER
정렬 대상 리스트가 $n$개 숫자이고 피봇보다 큰 값들이 $a$개, 작은 값들이 $b$개라면 퀵 정렬의 계산복잡성은 다음과 같이 쓸 수 있습니다.
\[T\left( n \right) =T\left( a \right) +T\left( b \right) +O\left( n \right)\]위 식 우변 마지막 항이 $O(n)$이 되는 이유는 피봇값 $k$와 리스트의 나머지 $n-1$개 요소 간 비교 연산을 수행해야 하기 때문입니다. 그런데 우리는 정렬이 목표가 아니므로 $k$보다 큰 $b$개의 숫자에 대해선 계산하지 않아도 됩니다. 따라서 $i$번째 작은 값을 구하는 알고리즘의 계산복잡성은 다음과 같이 쓸 수 있습니다.
\[T\left( n \right) =T\left( a \right) +O\left( n \right)\]이 알고리즘의 계산복잡성은 피봇을 어떻게 선택하느냐에 따라 달라집니다. 피봇값을 잘못 선택해 매 분기 때마다 아래 그림처럼 이뤄질 경우 각 층에서 피봇값과 리스트의 나머지 요소($k$번 분기시 $n-k$번) 간 비교연산을 수행하고, 이를 높이($n$)만큼 반복 수행해야 하므로 $O(n^2)$의 계산복잡성을 가지게 됩니다.
반대로 피봇을 잘 선택해 매번 분기 때마다 절반씩 나눌 수 있게 되면 $i$번째 작은 값을 구하는 알고리즘의 계산복잡성은 $O(n)$이 됩니다. 아래 점화식 형태의 계산복잡성 식이 $O(n)$이 되는 이유에 대해서는 이곳을 참고하시면 좋을 것 같습니다.
\[T\left( n \right) =T\left( n/2 \right) +O\left( n \right) \\ \Rightarrow O\left( n \right)\]pivot을 적절히 선택하기
따라서 $i$번째 작은 값을 찾는 문제를 선형 시간 내에 풀려면 피봇을 적절히 선택해 주어야 합니다. 이와 관련해 아래 그림 같은 아이디어도 있습니다. 방법은 이렇습니다. 전체 데이터를 몇 개 그룹으로 나눕니다. 해당 그룹에서 중앙값을 찾습니다. 여기서 다시 중앙값을 택합니다. 이를 피봇 삼아 분기를 수행하는 것입니다.
Comments