선택 문제

 

* 아래 문제 출처 : 3장 | 알기 쉬운 알고리즘 | 양성봉 | 생능출판사

** 알고리즘은 위의 책에 있는 알고리즘을 사용했기 때문에 책이 있으시면 더 쉽게 이해할 수 있습니다.

 

주어진 배열이 아래 표와 같고 5번째로 작은 숫자를 찾을 때, 알고리즘을 적용하여 선택 문제를 푸는 과정은 다음과 같습니다.

INDEX	0	1	2	3	4	5	6	7	8
ARRAY	6	1	3	9	4	5	8	2	7

 

+ 직관적으로 사람은 답이 5라는 것을 알 수 있습니다. 답을 기억한 상태에서 알고리즘을 적용하며 결과가 맞게 나왔는 지 확인해 보겠습니다. +

 

먼저 Selection(ARRAY, left, right, k)에서 k를 설정합니다. 여기서 k는 n번째로 작은 숫자를 찾는 문제에서 n과 동일합니다.

 

문제에 적용하면 Selection(ARRAY, 0, 8, 5)로 설정할 수 있습니다. 

 

1단계

먼저 피봇을 설정합니다. 알고리즘 상 피봇은 랜덤으로 설정되게 되어 있는데 보통 중간 위치를 설정하는 것이 덜 번거롭기 때문에 INDEX 4를 피봇으로 선정하겠습니다.

INDEX	0	1	2	3	4	5	6	7	8
ARRAY	6	1	3	9	4	5	8	2	7

 

피봇을 선정하고 나면 피봇의 값을 제일 왼쪽의 INDEX로 옮깁니다.

INDEX	0	1	2	3	4	5	6	7	8
ARRAY	4	1	3	9	6	5	8	2	7

 

그 다음 ARRAY에서 작은 값이 왼편에 올 수 있도록 서로 자리를 교환합니다.

INDEX	0	1	2	3	4	5	6	7	8
ARRAY	4	1	3	9	6	5	8	2	7

9, 2를 서로 교환하고

INDEX	0	1	2	3	4	5	6	7	8
ARRAY	4	1	3	2	6	5	8	9	7

피봇을 작은 수들의 제일 마지막 INDEX인 INDEX 3과 자리를 바꿉니다.

INDEX	0	1	2	3	4	5	6	7	8
ARRAY	2	1	3	4	6	5	8	9	7

그러면 피봇을 기준으로 피봇보다 작은 값들은 왼쪽에 위치하게 됩니다.

그 다음, 알고리즘에 따라 S = ( p -1 ) - left + 1에서 S값을 구합니다.

p는 피봇의 INDEX, left는 가장 왼쪽의 INDEX입니다.

따라서 S = ( p -1 ) - left + 1 는 S = (3-1) - 0 + 1 이고 계산하면 3이 됩니다.

S는 피봇보다 작은 값들의 개수입니다.

이제 5번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.

[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.

k는 5, S는 3이므로 위의 조건문은 거짓입니다. 따라서 다음 조건문으로 넘어갑니다.

[만약 k == S+1이라면, 피봇 값을 반환하라] 라는 내용입니다. 참일 경우, 피봇 값이 k번째로 작은 값이라는 뜻인데 5= 4 이므로 거짓이 됩니다.

위의 조건문 둘 다 거짓인 경우 Selection을 다음과 같이 다시 설정해줍니다.

Selction(ARRAY, p+1, right, k-S-1), 문제에 적용하면 Selction(ARRAY, 4, 8, 1)이 됩니다. INDEX 4부터 8까지, 1번째로 작은 숫자를 찾으라는 뜻입니다.

 

2단계

INDEX	4	5	6	7	8
ARRAY	6	5	8	9	7

마찬가지로 피봇을 설정해줍니다. 저는 INDEX 6을 피봇으로 선정하겠습니다.

INDEX	4	5	6	7	8
ARRAY	6	5	8	9	7

과정은 1단계와 동일합니다. 피봇 값을 제일 왼쪽으로 옮기고 피봇 값보다 작은 수가 왼편에 오도록 자리를 바꿔줍니다. 

INDEX	4	5	6	7	8
ARRAY	8	5	6	9	7

그 다음 피봇 값보다 작은 수가 왼편에 오도록 자리를 바꿔줍니다. 피봇 값을 피봇보다 작은 수들의 제일 오른쪽 편에 있는 INDEX 7과 바꿔주면 됩니다.

INDEX	4	5	6	7	8
ARRAY	7	5	6	8	9

이제 다시 S값을 구합니다.

S = ( p -1 ) - left + 1에서 p는 7, k는 1입니다.

S = ( p -1 ) - left + 1 는 S = (7-1) - 4 + 1 이고 계산하면 3이 됩니다.

이제 1번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.

[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.

k는 1, S는 3이므로 위의 조건문은 참입니다. 따라서 Selection을 다음과 같이 설정합니다.

Selection(ARRAY, 4, 6, 1)이 되고 INDEX 4부터 6까지, 1번째로 작은 숫자를 찾으라는 뜻입니다.

 

3단계

INDEX	4	5	6
ARRAY	7	5	6

마찬가지로 가운데 있는 INDEX 5를 피봇으로 선정하고, 5보다 작은 ARRAY값이 없기 때문에 값을 왼편으로 이동시키는 과정은 표현하지 않겠습니다. 알고리즘 상 실행은 됩니다.

INDEX	4	5	6
ARRAY	5	5	6

이제 다시 S값을 구합니다.

S = ( p -1 ) - left + 1에서 p는 4, k는 1입니다.

S = ( p -1 ) - left + 1 는 S = (4-1) - 4 + 1 이고 계산하면 0이 됩니다.

이제 1번째로 작은 값을 찾기 위해 조건문으로 넘어갑니다.

[만약 k가 S보다 작거나 같다면 Selection(ARRAY, left, p-1, k)로 설정하라] 라는 내용의 조건문입니다.

k는 1이고 S는 0이므로 거짓입니다. 따라서 다음 조건문으로 넘어갑니다.

[만약 k == S+1이라면, 피봇 값을 반환하라] 라는 내용입니다. 1 = 0 + 1 이므로 참입니다. 즉, 피봇값이 찾던 값이라는 뜻입니다.

따라서 답은 5가 됩니다.