비둘기집 원리

비둘기집 원리 설명

n 마리의 비둘기 떼가 n-1 개의 비둘기집으로 날아와 보금자리를 만든다고 가정해 봅시다. n 마리의 비둘기를 모두 만족시키 위해서는 적어도 하나의 둥지에 두 마리의 비둘기가 있어야 합니다.
처음 들었을 때 당연한 소리라고 생각되는데 위의 문장들이 비둘기집 원리의 핵심입니다.

Q :
가방에 빨간색 구슬 10개, 흰색 구슬 10개, 파란색 구슬 10개가 들어 있습니다. 가방의 색상으로 구분한다고 하면 최소색상의 가짓수는 몇 개 일까요? 동일한 색상의 구슬 4개를 얻으려면 가방에서 무작위로 구슬을 선택해야 할까요?

A : 비둘기집 원칙을 적용합니다. 색상 수(비둘기 구멍) n = 3
구슬 수(비둘기) K+1 = 4 필요한 구슬 수 = Kn+1 단순화하여 Kn+1 = 10을 얻습니다. 확인: ceil[Average]는 [Kn+1/n] = 4 [Kn+1/3] = 4 Kn+1 = 10 즉, 빨간색 3개 + 흰색 3개 + 파란색 3개 + 1(빨간색 또는 흰색 또는 파란색) = 10

비둘기집 정렬

비둘기집 정렬은 요소의 수와 가능한 키 값의 수가 거의 동일한 요소(element) 목록을 정렬하는 데 적합한 정렬 알고리즘입니다.
O( n + Range) 시간을 필요로 합니다. n은 입력 배열의 요소 수이고, Range는 배열에서 가능한 값의 수입니다.

l = [8, 3, 2, 7, 4, 6, 8]

def pigeonhole_sort(a):
    my_min = min(a)
    my_max = max(a)
    size = my_max - my_min + 1
 
    holes = [0] * size
 
    for x in a:
        holes[x - my_min] += 1
 
    i = 0
    for cnt in range(size):
        while holes[cnt] > 0:
            holes[cnt] -= 1
            a[i] = cnt + my_min
            i += 1
             
pigeonhole_sort(l)

print("정렬 된 순서는 : ", end = ' ')

for i in l:
    print(i, end = ' ')

주어진 구현에서 알고리즘은 다음과 같이 작동합니다.

1. O(n) 시간 복잡도를 가진 배열에서 최소값과 최대값을 찾습니다.
2. 일정한 시간이 걸리는 범위를 계산합니다.
3. 일정한 시간이 걸리는 범위와 동일한 크기의 벡터 배열을 만듭니다.
4. 입력 배열을 순회하고 각 요소를 각각의 구멍에 넣습니다. 이 단계에선 O(n) 시간이 소요됩니다.
5. 모든 구멍을 순회하고 해당 요소를 출력 배열에 순서대로 배치합니다. 이 단계에서는 O(범위) 시간이 소요됩니다.

따라서, 이 알고리즘의 전체 시간 복잡도는 O(n + 범위)입니다. 최악의 경우에는 범위가 배열의 요소 수보다 훨씬 크면 알고리즘이 비효율적일 수 있습니다. 그러나 상대적으로 작은 범위의 정수 배열을 정렬하는 데에는 유용할 수 있습니다.

비둘기 정렬의 장점 & 단점

장점
1. 비비교 기반 정렬이므로 응용 프로그램에서 더 빠르다.
2. 안정적인 정렬 알고리즘이다.
3. 선형 시간으로 정렬을 수행한다.

단점
1. 정렬할 숫자의 범위를 알기 힘들다.
2. 숫자 n은 0과 양의 정수에만 사용할 수 있습니다.