선택문제 (Selection Problem)

선택 문제 (Selection Probelm) 이란?

N개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제

선택 문제를 해결하기 방법

1. 최소 숫자를 k번 찾는다.

2. 숫자를 정렬한 후, k번째 숫자를 찾는다.

이를 위해 QuickSort의 피봇의 위치를 지정하는 방식을 사용한다.

1. 피봇을 찾는다.

2. 피봇의 위치를 찾고 분할한 경우, Small group (피봇 기준 왼쪽), Large group (피봇 기준 오른쪽)으로 나뉜다.

이때, 분할하고 알아야 할 것은 각 그룹의 크기다.
각 그룹의 크기를 알면, k번째 작은 숫자가 어느 그룹에 있는지 알 수있고, 그 다음에는 그 그룹에서 몇 번째로 작은 숫자를 찾아야 하는지 알 수 있다.
즉, 7번째 작은 수를 찾으려고하는데 피봇의 위치가 5번째 위치라면 피봇위치를 기준으로 2번째 작은 수를 찾으면 7번째 작은 수를 찾을 수 있다.

예시

의사코드

C++ 코드

#include <stdio.h>
#define MAX 100

int input[MAX]; // 입력 값의 배열
int count; // 입력 값의 개수

void swap(int* a, int* b) { // 스왑 함수
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Selection(int pivot, int left, int right, int k) { // 선택 함수
	int low = left;
	int high = right;
	
	while (1) {
		// left를 이동 : pivot보다 작은 숫자들을 skip
		for (int i = 0; i < right + 1; i++) {
			printf("%d ", input[i]);
		}
		printf("\n\n");

		do {
			low++;
		} while (low <= right && input[low] < input[pivot]);
		// right 값과 low값을 비교하여 low 값이 right 값보다 작거나 같고 pivot 값이 low에 위치한 값보다 작으면 실행

		while (left <= high && input[high] > input[pivot]) {
			high--;
		} // high 값이 left 보단 크거나 같고 high에 위치한 값 pivot이 크다면 실행

		// low와 high의 자리를 바꿔준다.
		if (low < high) {
			swap(&input[low], &input[high]);
		}

		else {
			if (high == k) { // 내가 찾고자 하는 위치 k가 high와 동일
				printf("%d번째로 큰 값은 %d입니다.\n", high + 1, input[pivot]);
				return;
			}
			else {
				// 일단 pivot과 high의 위치를 바꾸고
				swap(&input[pivot],&input[high]);

				// 내가 찾고자하는 k가 의 high의 왼쪽인지, 오른쪽인지 검사한다
				if (k < high) { // 왼쪽 부분 배열만 확인하면 된다.
					Selection(pivot, pivot, high - 1, k);
				}
				else { // 오른쪽 부분 배열만 확인하면 된다.
					Selection(high + 1, high + 1, right, k);
				}
				return;
			}
		}
	}
}

int main(void) {
	printf("입력 값의 개수를 입력하세요 : ");
	scanf("%d", &count);
	
	printf("\n");

	printf("값을 입력해주세요 : ");

	for (int i = 0; i < count; i++) {
		scanf("%d", &input[i]);
	}

	printf("몇번째로 큰 값을 찾을까요?? : ");
	int k; // 우리가 찾고자 하는 값 (ex : k번째로 큰수)
	scanf("%d",&k);

	Selection(0, 0, count - 1, k - 1);

	return 0;
}