손코딩 (1)

송윤재·2024년 10월 21일

cs스터디 손코딩

❓Q1. 길이가 N인 배열이 있을 때, 이 배열에서 K 번째로 큰 수를 추출하는 프로그램을 작성해 보세요. (단, 시간복잡도는 O(NlogN) 보다 작아야 합니다.)

💡Solution 빠른 선택 (Quick Select) 알고리즘

빠른 선택 알고리즘(Quick Select)은 Partitioning(파티셔닝)을 이용해 여러 값이 주어졌을 때 k 번째로 작은 값이나 큰 값을 찾는 검색 알고리즘입니다.

Partitioning 이란?

Pivot 이라는 하나의 숫자를 기준으로 배열의 요소를 정렬하는 방식
Pivot 보다 작은 수는 좌측에 위치한다.
Pivot 보다 큰 수는 우측에 위치한다.
이와 같은 규칙으로 배열의 요소를 정리하는 것이다.

복잡도

빠른 선택 알고리즘의 성능은 퀵 정렬 알고리즘과 마찬가지로 Pivot 값을 어떻게 선택하느냐에 따라 좌우됩니다.
이상적인 경우에는 Pivot 값을 기준으로 정확히 매번 배열이 절반으로 나누어져 시간 복잡도는 O(n)이 됩니다. (n + n/2 + n/4 + n/8 ... = 2n = O(n))
연속해서 pivot 값이 가장 작은 값이거나 가장 큰 값이 되어 분할할 때 마다 값들이 한 편으로 크게 치우치게 되어 최악의 경우 O(n^2)의 시간 복잡도를 보일 수 있습니다.
배열의 크기가 커지면 커질수록 최악의 경우가 발생할 경우가 적어지므로 평균적으로 O(n)의 시간 복잡도를 가지게 됩니다.

동작 예시

1. 퀵 셀렉트 시작

배열: [3, 6, 8, 1, 5, 9, 2]
목표는 4번째 작은 값을 찾는 것 (0부터 시작하는 인덱스로는 k = 3).

    // 배열의 중앙값을 반환하는 함수
    public static double findMedian(int[] nums) {
        int length = nums.length;

        if (length % 2 == 1) {
            // 배열 길이가 홀수일 경우, 중앙값은 k번째 작은 수
            return quickSelect(nums, 0, length - 1, length / 2);
        } else {
            // 배열 길이가 짝수일 경우, 중앙값은 두 중앙값의 평균
            return (quickSelect(nums, 0, length - 1, length / 2 - 1) +
                    quickSelect(nums, 0, length - 1, length / 2)) / 2.0;
        }
    }

2. 첫 번째 Pivot 선택 및 분할

랜덤 피벗을 선택합니다. 예를 들어, 6을 Pivot으로 선택했다고 가정합니다.
피벗을 맨 오른쪽으로 이동시킨 후, 배열을 피벗을 기준으로 작은 값과 큰 값으로 분할합니다.

Pivot : 6

분할 전 배열:

[3, 6, 8, 1, 5, 9, 2] -> Pivot인 6을 맨 뒤로 이동 -> [3, 2, 8, 1, 5, 9, 6]

분할 과정:

3, 2, 1, 5는 Pivot보다 작으므로 왼쪽으로 이동합니다.
8, 9는 Pivot보다 크므로 오른쪽에 남습니다.

분할 후 배열:

[3, 2, 1, 5, 6, 9, 8]

Pivot 6의 최종 위치는 인덱스 4입니다.

    // 파티션 함수: 피벗을 기준으로 배열을 분할
    private static int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivotValue = nums[pivotIndex];
        swap(nums, pivotIndex, right);  // 피벗을 오른쪽으로 이동
        int storeIndex = left;
        
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex);  // 피벗을 제자리에 놓음
        return storeIndex;
    }

3. Pivot과 k값 비교

Pivot의 위치는 4입니다.
우리가 찾고 있는 값의 인덱스는 k = 3이므로, 우리가 찾는 값은 Pivot보다 왼쪽에 있습니다.

4. 왼쪽 부분 배열에서 퀵 셀렉트 재귀 호출

Pivot의 왼쪽 부분 배열 [3, 2, 1, 5]에서 다시 퀵 셀렉트를 수행합니다.
배열: [3, 2, 1, 5], 목표 인덱스 k = 3 (여기서는 왼쪽 배열에서 k = 3 - 0 = 3)

    // 퀵 셀렉트를 사용하여 배열에서 k번째 작은 요소를 찾는 함수
    private static int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }
        
        Random rand = new Random();
        int pivotIndex = left + rand.nextInt(right - left + 1);  // 랜덤 피벗 선택
        pivotIndex = partition(nums, left, right, pivotIndex);
        
        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

5. 두 번째 Pivot 선택 및 분할

새로운 Pivot을 무작위로 선택합니다. 예를 들어 2를 선택했다고 가정합니다.
Pivot을 맨 오른쪽으로 이동하고 분할합니다.

Pivot : 2

분할 전 배열:

[3, 2, 1, 5] -> Pivot을 맨 뒤로 이동 -> [3, 5, 1, 2]

분할 과정:

1은 Pivot보다 작으므로 왼쪽으로 이동.
3, 5는 Pivot보다 크므로 오른쪽에 남습니다.

분할 후 배열:

[1, 2, 3, 5]

Pivot 2의 최종 위치는 인덱스 1입니다.

6. Pivot과 k값 비교

Pivot의 위치는 1입니다.
우리가 찾고 있는 값의 인덱스는 k = 3이므로, 여전히 Pivot의 오른쪽에 원하는 값이 있습니다.

7. 오른쪽 부분 배열에서 퀵 셀렉트 재귀 호출

Pivot의 오른쪽 부분 배열 [3, 5]에서 다시 퀵 셀렉트를 수행합니다.
배열: [3, 5], 목표 인덱스 k = 3 - 2 = 1

8. 세 번째 Pivot 선택 및 분할

새로운 Pivot을 선택합니다. 예를 들어 3을 선택했다고 가정합니다.
Pivot 3은 이미 왼쪽 끝에 있기 때문에 분할할 필요가 없습니다.

Pivot : 3

분할 후 배열:

[3, 5]

Pivot 3의 최종 위치는 인덱스 0입니다.

9. Pivot과 k값 비교

Pivot의 위치는 0입니다.
우리가 찾고 있는 값은 인덱스 1에 있습니다.

10. 최종 값 도출

Pivot의 오른쪽에 있는 값 5가 우리가 찾고 있는 4번째 작은 값 입니다.

퀵 셀렉트의 핵심

배열 전체를 정렬하지 않고, Pivot을 선택해 목표 인덱스(k)가 어디에 있는지에 따라 분할하여 검색합니다.

배열을 Pivot 기준으로 작고 큰 값으로 나누고, 필요한 부분만 재귀적으로 탐색합니다.

최종적으로 k번째 작은 값을 찾습니다.

이 과정은 배열을 정렬하지 않고도 k번째 값을 효율적으로 구하는 방법입니다.

❓Q2. 배열을 정렬하지 않고, 배열의 중앙값을 구하는 코드를 작성해보세요.

💡Solution 1. Heap을 이용한 중앙값 찾기

최대 힙은 배열의 왼쪽 절반 (작은 값들을 저장) 을 관리합니다.

최소 힙은 배열의 오른쪽 절반 (큰 값들을 저장) 을 관리합니다.

각 값을 삽입할 때, 최대 힙과 최소 힙의 크기를 조정하여 균형을 맞춥니다.

중앙값은 힙의 크기에 따라 다음과 같이 결정됩니다:

최대 힙과 최소 힙의 크기가 같다면, 두 힙의 루트 값(최대 힙의 최대값과 최소 힙의 최소값)의 평균이 중앙값입니다.

최대 힙의 크기가 더 크다면 최대 힙의 루트 값이 중앙값입니다.

동작 설명

1. 최대 힙과 최소 힙을 사용하여 배열의 작은 절반과 큰 절반을 관리합니다.

maxHeap (최대 힙)은 작은 절반을 관리하고, minHeap (최소 힙)은 큰 절반을 관리합니다.
최대 힙은 큰 값을 기준으로 작은 값이 위로 올라가며, 최소 힙은 작은 값을 기준으로 큰 값이 위로 올라갑니다.

    // 최대 힙(작은 절반의 값)
    private PriorityQueue<Integer> maxHeap;
    // 최소 힙(큰 절반의 값)
    private PriorityQueue<Integer> minHeap;

    public MedianFinder() {
        // 최대 힙은 큰 값을 기준으로 작은 값이 위로 오게 해야 하므로 reverse order
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

2. 새로운 값이 추가될 때

값이 최대 힙에 추가된 후, 최대 힙의 값이 최소 힙의 값보다 크면 값을 교환하여 항상 작은 값이 최대 힙에, 큰 값이 최소 힙에 위치하도록 유지합니다.
힙들의 크기를 균형 있게 유지해야 하므로, 최대 힙의 크기가 최소 힙보다 1만큼 크거나 같도록 합니다.

    // 새로운 값을 추가하는 함수
    public void addNum(int num) {
        // 1. 최대 힙에 우선 추가
        maxHeap.offer(num);

        // 2. 최대 힙의 루트 값이 최소 힙의 루트 값보다 크면 값을 교환 (정렬 유지)
        if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()) {
            minHeap.offer(maxHeap.poll());
        }

        // 3. 최대 힙과 최소 힙의 크기 균형을 맞춤 (최대 힙이 1개 더 많거나 같게 유지)
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

3. 중앙값 찾기

만약 두 힙의 크기가 같다면, 두 힙의 루트 값(최대 힙의 최대값과 최소 힙의 최소값)의 평균이 중앙값이 됩니다.
만약 최대 힙의 크기가 더 크다면, 최대 힙의 루트 값이 중앙값이 됩니다.

    // 중앙값을 반환하는 함수
    public double findMedian() {
        if (maxHeap.size() == minHeap.size()) {
            return (maxHeap.peek() + minHeap.peek()) / 2.0; // 힙 크기가 같을 때 두 루트 값의 평균
        } else {
            return maxHeap.peek(); // 최대 힙이 더 클 때는 최대 힙의 루트 값이 중앙값
        }
    }

동작 예시

배열 [3, 6, 8, 1, 5, 9, 2]에서 새로운 값이 추가될 때마다 중앙값을 구해보겠습니다.

3을 추가하면: 최대 힙 [3] → 중앙값: `3
6을 추가하면: 최대 힙 [3], 최소 힙 [6] → 중앙값: (3 + 6) / 2 = 4.5
8을 추가하면: 최대 힙 [3], 최소 힙 [6, 8] → 중앙값: 6
1을 추가하면: 최대 힙 [1, 3], 최소 힙 [6, 8] → 중앙값: (3 + 6) / 2 = 4.5
5을 추가하면: 최대 힙 [3, 1], 최소 힙 [5, 8, 6] → 중앙값: 5
9을 추가하면: 최대 힙 [3, 1], 최소 힙 [5, 6, 8, 9] → 중앙값: (5 + 6) / 2 = 5.5
2을 추가하면: 최대 힙 [2, 1, 3], 최소 힙 [5, 6, 8, 9] → 중앙값: 5

결론

이 방법은 최대 힙과 최소 힙을 사용해 배열을 정렬하지 않고 중앙값을 빠르게 찾을 수 있습니다. 특히 데이터가 실시간으로 추가되는 경우에 매우 효율적으로 중앙값을 유지할 수 있으며, 삽입이나 중앙값 계산에 O(log n)의 시간 복잡도를 가집니다.

💡Solution 2. Median of Medians 알고리즘

퀵 셀렉트(Quickselect)의 성능을 보완하여 최악의 경우에도 선형 시간 O(n) 에 가까운 성능을 보장하는 알고리즘. 임의의 Pivot을 선택하는 대신, Median of Medians는 균형 잡힌 Pivot을 선택하여 분할(partition)을 보다 효율적으로 만듭니다. 이 과정을 통해 배열의 중앙값을 더 빠르게 찾을 수 있습니다.

단계별 알고리즘

1. 5개의 그룹으로 배열 분할

주어진 배열을 5개의 그룹으로 나누고 각 그룹에서 중앙값을 찾습니다.

2. 각 그룹의 중앙값 추출

각 그룹을 오름차순으로 정렬하여 중앙값을 구합니다. 즉, 그룹이 [a, b, c, d, e]라면 이 그룹의 중앙값은 c입니다.

    // 배열을 5개씩 그룹으로 나누어 중앙값 배열을 반환
    public static int[] getMedians(int[] arr) {
        int numMedians = (arr.length + 4) / 5;  // 그룹당 최대 5개씩
        int[] medians = new int[numMedians];

        for (int i = 0; i < numMedians; i++) {
            int[] group = Arrays.copyOfRange(arr, i * 5, Math.min((i + 1) * 5, arr.length));
            Arrays.sort(group);
            medians[i] = group[group.length / 2];  // 그룹의 중앙값 선택
        }

        return medians;
    }
    
    // 배열에서 k번째 작은 원소를 Median of Medians 알고리즘으로 찾기
    public static int medianOfMedians(int[] arr, int k) {
        // 작은 배열은 바로 정렬해서 해결
        if (arr.length <= 5) {
            Arrays.sort(arr);
            return arr[k];
        }

        // 5개의 그룹으로 중앙값 배열을 구함
        int[] medians = getMedians(arr);
        
        ...
    }

3. 중앙값들의 중앙값을 찾는다

두 번째 단계에서 구한 모든 중앙값들로 새로운 배열을 만든 후, 그 배열의 중앙값을 찾습니다. 이 중앙값을 Pivot으로 사용합니다.

    // 배열을 5개씩 그룹으로 나누어 중앙값 배열을 반환
    public static int[] getMedians(int[] arr) {
    	...
        
        // 중앙값 배열에서 중앙값을 찾음
        int pivot = medianOfMedians(medians, medians.length / 2);
        
        ...
    }

4. 퀵 셀렉트 방식으로 피벗을 사용하여 분할

Pivot을 기준으로 배열을 두 부분으로 나눈 후, 퀵 셀렉트 방식으로 중앙값을 찾습니다.

    // 피벗을 기준으로 배열을 분할하여 세 그룹 반환 (lows, pivots, highs)
    public static int[][] partition(int[] arr, int pivot) {
        int[] lows = Arrays.stream(arr).filter(x -> x < pivot).toArray();
        int[] highs = Arrays.stream(arr).filter(x -> x > pivot).toArray();
        int[] pivots = Arrays.stream(arr).filter(x -> x == pivot).toArray();

        return new int[][]{lows, pivots, highs};
    }

    // 배열을 5개씩 그룹으로 나누어 중앙값 배열을 반환
    public static int[] getMedians(int[] arr) {
    	...
        
        // 피벗을 기준으로 배열을 세 그룹으로 분할
        int[][] partitioned = partition(arr, pivot);
        int[] lows = partitioned[0];
        int[] pivots = partitioned[1];
        int[] highs = partitioned[2];

        // k번째 원소를 찾는 과정
        if (k < lows.length) {
            return medianOfMedians(lows, k);  // 왼쪽 그룹에서 탐색
        } else if (k < lows.length + pivots.length) {
            return pivots[0];  // 피벗이 k번째 원소일 경우
        } else {
            return medianOfMedians(highs, k - lows.length - pivots.length);  // 오른쪽 그룹에서 탐색
        }
    }

동작 예시

배열 [12, 3, 5, 7, 4, 19, 26, 23, 8, 9, 16, 10, 14, 2, 21]에서 중앙값을 찾는 과정을 보겠습니다.

1. 배열을 5개의 그룹으로 분할

	[12, 3, 5, 7, 4], [19, 26, 23, 8, 9], [16, 10, 14, 2, 21]

2. 각 그룹의 중앙값 선택

첫 번째 그룹 [12, 3, 5, 7, 4]의 중앙값은 5 (정렬된 그룹: [3, 4, 5, 7, 12]).
두 번째 그룹 [19, 26, 23, 8, 9]의 중앙값은 19 (정렬된 그룹: [8, 9, 19, 23, 26]).
세 번째 그룹 [16, 10, 14, 2, 21]의 중앙값은 14 (정렬된 그룹: [2, 10, 14, 16, 21]).

이제 중앙값들의 배열은 [5, 19, 14]입니다.

3. 중앙값들의 중앙값 선택

배열 [5, 19, 14]을 정렬하면 [5, 14, 19]이 됩니다. 중앙값은 14입니다.
따라서 Pivot으로 14를 선택합니다.

4. Pivot을 기준으로 배열 분할

Pivot 14를 기준으로 배열을 두 부분으로 분할

	[12, 3, 5, 7, 4, 8, 9, 10, 2] (Pivot보다 작은 값들)
	[19, 26, 23, 16, 21] (Pivot보다 큰 값들)

Pivot 14는 배열에서 10번째에 위치하고, 배열의 크기인 15의 중앙은 8번째입니다.
따라서 중앙값은 14의 왼쪽 부분에서 다시 찾아야 합니다.

5. 재귀적으로 퀵 셀렉트 반복

Pivot 14의 왼쪽 부분 [12, 3, 5, 7, 4, 8, 9, 10, 2]에서 다시 같은 과정으로 중앙값을 찾습니다.
이 배열의 크기는 9이므로, 5번째 원소가 중앙값입니다.

❌ 번외. Quick Select vs Median of Medians

특징	Quick Select	Median of Medians
시간 복잡도 (평균)	O(n)	O(n)
시간 복잡도 (최악)	O(n^2)	O(n)
피벗 선택 방법	임의의 피벗	균형 잡힌 피벗 (Median of Medians)
구현 복잡도	간단하고 직관적	상대적으로 복잡
일반적인 성능	더 빠를 가능성이 있음	항상 안정적인 성능을 보장
사용 목적	평균적인 빠른 성능	최악의 경우를 방지하고자 할 때

결론

Quick Select는 평균적인 상황에서 매우 빠르며 간단하게 구현할 수 있지만, Pivot 선택이 불균형하면 최악의 경우 성능이 떨어질 수 있습니다.
Median of Medians는 최악의 경우에도 선형 시간 복잡도를 보장하지만, 구현이 복잡하고 실용적인 상황에서 Quick Select만큼 빠르지는 않을 수 있습니다.
실용적인 문제에서는 Quick Select가 더 자주 사용되며, 최악의 경우가 중요할 때는 Median of Medians를 고려합니다.

출처

Quick Select
https://www.daleseo.com/quick-select/
https://devraphy.tistory.com/372
Median of Medians
https://gazelle-and-cs.tistory.com/58
https://umbum.tistory.com/671