중앙값 구하기, 재귀 함수[파이썬 독학]

데이터 세트의 중앙값을 계산하는 것은 통계 및 데이터 분석에서 일반적인 작업입니다. 파이썬에서는 중앙값을 계산하는 여러 알고리즘이 있는데, 이 게시물에서는 파이썬에서 중앙값을 계산하는 두 가지 방법을 다뤄보겠습니다.

 

알고리즘 1: 정렬 및 중간 값 찾기

중앙값을 계산하는 가장 간단한 방법은 데이터 리스트를 정렬하고 중간 값을 찾는 것입니다. 데이터 리스트에 홀수 개의 요소가 있는 경우, 중간 요소가 중앙값입니다. 데이터 리스트에 짝수 개의 요소가 있는 경우엔, 중앙값은 두 중간 요소의 평균이 됩니다.

def median(lst):
    lst = sorted(lst)
    n = len(lst)
    if n % 2 == 0:
        return (lst[n//2-1] + lst[n//2]) / 2
    else:
        return lst[n//2]

lst = [5, 3, 1, 2, 4,7,3,1,10,143,144]
median(lst)
#output: 4

lst = [5,3,1,2,4,6,7,9,8,7]
median(lst)
#output: 5.5

이 코드에서는 먼저 sorted() 함수를 사용하여 리스트를 정렬합니다. 그런 다음 리스트의 길이를 찾아 짝수 또는 홀수의 요소가 있는지 확인합니다. 요소의 수가 짝수이면 두 중간 요소의 평균을 반환합니다. 요소의 수가 홀수이면 중간 요소를 반환합니다.

 

알고리즘 2: quickselect

quickselect 알고리즘은 리스트에서 k번째로 작은 요소를 찾기 위해 최적화된 빠른 정렬 알고리즘의 변형입니다. quickselect를 사용하여중위수를 계산하기 위해 먼저 k번째 요소를 찾습니다. 여기서 k는 정렬된 리스트의 중간 인덱스입니다. 리스트에 짝수 개의 요소가 있으면 k번째 및 (k+1)번째 요소를 찾아 평균을 반환합니다.

import random

def quickselect(lst, k):
    if len(lst) == 1:
        return lst[0]
    pivot = random.choice(lst)
    lows = [elem for elem in lst if elem < pivot]
    highs = [elem for elem in lst if elem > pivot]
    pivots = [elem for elem in lst if elem == pivot]
    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quickselect(highs, k - len(lows) - len(pivots))

def median2(lst):
    n = len(lst)
    if n % 2 == 0:
        return (quickselect(lst, n//2-1) + quickselect(lst, n//2)) / 2
    else:
        return quickselect(lst, n//2)
        
lst = [5,3,1,2,4,7,3,1,10,143,144]
median2(lst)
#output: 4

lst = [5,3,1,2,4,6,7,9,8,7]
median2(lst)
#output: 5.5

 

리스트에서 k번째로 작은 요소를 찾는 quickselect() 함수를 정의합니다. 이때 값은 리스트 안에서 random.choice() 함수로 추출합니다. 피벗 요소를 선택하고 리스트를 피벗보다 작은 요소, 피벗보다 큰 요소, 피벗과 동일한 요소의 세 부분으로 분할합니다. 그런 다음 k번째 요소를 찾을 때까지 적절한 파티션에서 quickselect() 함수를 재귀적으로 호출합니다.

중앙값을 찾기 위해 median2() 함수에서는 quickselect() 함수를 두 번 호출합니다. n의 나머지 자리수에 따라서 짝수라면 한 번은 k번째 요소에 대해, 한 번은 (k+1)번째 요소에 대한 quickselect() 함수를 호출하고 평균을 반환해줍니다. n이 홀수개라면 quickselect()함수를 한번만 호출합니다.

 

재귀함수

재귀 함수는 특정 조건이 충족될 때까지 일련의 단계를 반복하기 위해 스스로 호출하는 프로세스 또는 함수를 의미합니다. 다시 말해, 함수가 재귀적으로 호출될 때, 그것은 본질적으로 자신의 정의 안에서 자신을 호출합니다.

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

n을 5로 주게 되면, 맨 처음엔 5 * factorial(4) → 두번째는 5 * 4 * factorial(3) → 세번째는 5 * 4 * 3 * factorial(2) → 네번째는 5 * 4 * 3 * 2 * factorial(1) → 마지막으로는 5 * 4 * 3 * 2 * 1이 됩니다.

재귀 함수는 특정 유형의 문제를 해결하는 데 매우 유용할 수 있지만 주의하여 사용해야 합니다. 만약 신중하게 구현되지 않는다면, 재귀 함수들은 무한 루프와 스택 오버플로를 초래할 수 있으며, 이는 프로그램을 충돌시킬 수도 있습니다.