파이썬(Python)으로 선형 시간 복잡도 내에 리스트의 n번째로 작은 요소 선택하기

개요

리스트에서 선형 시간 복잡도(O(n))로 n번째로 작은 요소를 선택해야 하는 상황이라면, 크게 두 가지 메서드가 필요합니다. 하나는 주어진 범위에서 가장 작은 요소를 찾는 메서드이고, 다른 하나는 리스트를 두 부분으로 나누는 파티션(partition) 메서드입니다.

리스트를 나누는 기준은 사용자가 입력한 'i' 값입니다. 이 값을 기준으로 리스트가 분할되고, 재귀 호출을 통해 원하는 순번의 작은 요소가 최종적으로 결정됩니다. 이러한 접근 방식은 퀵 정렬(Quick Sort)의 파티션 기법을 응용한 것으로, 흔히 퀵셀렉트(Quickselect) 알고리즘이라고 불립니다.

예제 코드

def select_smallest(my_list, beg, end, i):
    if end - beg <= 1:
        return my_list[beg]
    pivot_val = start_partition(my_list, beg, end)

    k = pivot_val - beg + 1

    if i < k:
        return select_smallest(my_list, beg, pivot_val, i)
    elif i > k:
        return select_smallest(my_list, pivot_val + 1, end, i - k)

    return my_list[pivot_val]

def start_partition(my_list, beg, end):
    pivot_val = my_list[beg]
    i = beg + 1
    j = end - 1

    while True:
        while (i <= j and my_list[i] <= pivot_val):
            i = i + 1
        while (i <= j and my_list[j] >= pivot_val):
            j = j - 1

        if i <= j:
            my_list[i], my_list[j] = my_list[j], my_list[i]
        else:
            my_list[beg], my_list[j] = my_list[j], my_list[beg]
            return j

my_list = input('Enter the list of numbers.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('Enter the value for i.. '))

ith_smallest = select_smallest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_smallest))

실행 결과

Enter the list of numbers.. 43 12 67 89 99 0
Enter the value for i.. 3
The result is 43.

코드 설명

• select_smallest: 리스트, 시작 인덱스(beg), 끝 인덱스(end), 그리고 'i' 값을 매개변수로 받는 메서드입니다.

• start_partition: 피벗(pivot) 값을 기준으로 리스트를 두 부분으로 나누는 역할을 하며, 'select_smallest' 메서드 내부에서 호출됩니다.

• 'select_smallest' 함수는 자기 자신을 다시 호출하는데, 이것이 바로 재귀(recursion)가 동작하는 방식입니다.

• 숫자 목록은 사용자로부터 입력받으며, 입력된 문자열은 공백을 기준으로 분리(split)됩니다.

• 리스트를 반복(iterate)하면서 각 요소를 정수형으로 변환합니다.

• 사용자로부터 'i' 값을 추가로 입력받습니다.

• 이 'i' 값을 기준으로 리스트가 두 부분으로 나뉘고, 조건에 맞는 한쪽 영역에 대해서만 'select_smallest' 메서드가 다시 호출됩니다.

• 최종 결과가 콘솔에 출력됩니다.

성능 참고 사항

이 방식은 평균적인 경우 선형 시간 O(n)에 실행되지만, 피벗 선택이 운에 좌우되기 때문에 최악의 경우 O(n²)까지 느려질 수 있습니다. 항상 좋은 피벗을 보장하고 싶다면 '중앙값의 중앙값(median of medians)' 기법을 함께 적용하면 되는데, 이렇게 하면 최악의 경우에도 O(n)의 성능을 유지할 수 있습니다.