글 읽기 - quick Selection 알고리즘을 써보는데 4%에서 넘어가질 못합니다...

kimjh9434 5년 전 0

흠냐... 이번이 3번째 질문이군요.

매일 최소 한 문제씩 푼다고 하는데, 요 근래들어 힘이부치는것 같습니다.

이 문제에 매달린지도 좀 되는것 같내요.

맨 처음의 풀이구상 : 그냥 정렬 후 K번째 수 출력

- 기본적으로는 그냥 정렬 후 K번째 수를 출력하는건데, 일단 분할 정복 단계에 있는 만큼

Quick_Sort 또는 Merge sort를 이용해봐야겠다는 생각이 들었습니다.

또한 여담으로 수의 크기 자체가 많은 만큼, BufferedReader를 써야겠다는 생각으로 풀어보았습니다.

그렇게, BufferedReader로 입력받은 수를 배열로 만들어서, Quick_Sort를 돌리고, K번째 수를 출력한 채점결과는,

99%까지 쭉쭉쭉 올라가다가 99%에서 시간초과가 뜨더군요!

아, 이건 여담으로 문제 자체는 Arrays 패키지의 'Arrays.sort(arr);'를 써버리니까 풀리긴 했습니다...

예전 정렬해보기 단계의 3번째 문제 - 10989 수 정렬하기 3도 BufferedReader, BufferedWriter + Counting Sort알고리즘으로 풀었었는데,

그것도 Arrays.sort(arr)로 풀리더군요... 자바의 기본 패키지의 정렬 알고리즘이 엄청나다는것은 깨닫긴 했습니다.

[어줍잖게 자체 정렬알고리즘을 쓰면 안된다는 교훈]

근데, 그건 그거고, 당연히 제 힘으로 푼 문제가 아니기 때문에, '이걸로 문제 풀렸으니까 장땡' 하고 넘어갈 수가 없더군요.

2. 두번째 풀이 구상 : quick Selection

- 일단 일차 풀이가 틀려서 Merge sort를 이용해볼 생각을 하면서, 게시판의 질문목록을 확인해봤습니다.

그러니, 수가 워낙 커서 Quick_Sort 또는 Merge sort를 써도 통과가 안되었다는 의견들이 많더군요.

보아하니, 언어가 C++같은 경우 nth-element라는 함수가 있어서 k번째 수를 찾는것 같은데, 그건 C++한정이라서 제가 시도하는 자바는 안되는 경우였고,

quick Selection이라는 알고리즘을 쓰면 k번째 수를 찾을수 있다고 해서 살펴보았습니다.

- 내용은 단순하더군요.

본래 quick sort가 pivot을 잡고, 파티션을 통해 pivot보다 작은놈들, 큰놈들 둘로 쪼게는걸 반복하는 식이라면,

quick Selection은 pivot을 잡고, 파티션을 하는것 까진 똑같지만, K값이 pivot의 Index보다 큰지 작은지에 따라

그 외의 영역까지 정렬시킬 필요는 없고, 나머지 영역만 진행하면 되는놈이기 때문이었죠. [그래서 O(nlogn)이나 O(n^2)이 O(n)까지 줄여준댔나 뭐래나]

근데 문제는 개념은 이해했는데, quick Selection을 적용한 제 코드가 계속 4%에서 넘어가질 못합니다... 계속 거기서 시간초과가 떠버리는군요.

제가 스스로 생각한 코드가 안되서, 구글에 quick Selection를 검색해서 나오는 소스코드를 복붙해서 채점에 넣어보기 시작했습니다.

여기 질문 게시판에 저 말고도 quick Selection 을 돌렸던 https://www.acmicpc.net/board/... 분의 코드도 돌려보았지만 똑같았습니다.

이 모든 예제가 모두다 정답은 잘만 나오는데 죄다 4%를 넘지 못해서...

제가 quick sort 및 quick Selection을 잘못 이해하고 있는건 아닌지,

또는 뭔가 치명적인 문제가 있는 코드지만 그 문제를 발견하지 못하는 아닌가 해서 질문 드립니다...

아래는 제가 시도해 보았던 코드들 입니다. [저거 말고도 더 있지만 그냥 비슷비슷한 놈들이라서... 일단 저거만 올립니다.]

CF. 샘플 입력 예제 [1~40까지를 무작위로 배치해 놓은 수]

40 25

19 4 30 40 13 31 7 36 12 23 8 37 5 20 38 2 24 18 39 3 25 15 35 6 21 26 17 34 11 27 9 16 28 10 33 29 14 1 22 32

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N, K;
		int[] A;

		String[] str;

		str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		K = Integer.parseInt(str[1]);

		str = br.readLine().split(" ");
		A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(str[i]);
		}
        // 위 부분은 변하지 않는 부분
        //////////////////////////////////////////
        
        // 수많은 Quick_Sort 후보들
		bw.write(Quick_Select(A, 0, N - 1, K) + "\n");
		//bw.write(quick_selection(N, A, K-1) + "\n");
        //bw.write(Quick_Select3(A, 0, N - 1, K) + "\n");
        //bw.write(quickSelect(A, 0, N-1, K-1) + "\n");

        
        bw.flush();
		bw.close();
    }
    
    // 출처 : 본인
    // Quick_Select 후보 1
	public static int Quick_Select(int[] arr, int left, int right, int select) {

		if (left <= right) {
			int pivotI = Partition(arr, left, right);
			
			if(pivotI == select -1){
				return arr[select -1];
			}else if(select -1 < pivotI){
				return Quick_Select(arr, left, pivotI - 1, select);
			}else{
				return Quick_Select(arr, pivotI + 1, right, select);
			}
		}
		return -1;
	}
    
    public static int Partition(int[] arr, int left, int right) {
		int pivotV = Median(arr[left], arr[right], arr[(left+right)/2]);

		// left가 right보다 작은동안 반복한다.
		while (left < right) {
			// right보다 왼쪽에 존재하지만, pivotV보다 큰 left의 위치 찾는다.
			while (left < right && pivotV > arr[left]) {
				left++;
			}
			// left보다 오른쪽에 존재하지만, pivotV보다 작은 right의 위치을 찾는다.
			while (left < right && pivotV < arr[right]) {
				right--;
			}
			// 엇갈리지않으면 두 값의 위치를 바꾼다.
			if(left < right){
				Swap(arr, left, right);
			}
		}

		return right;
	}
    
    // 중위값 찾는 함수
	public static int Median(int a, int b, int c) {
		int ret;
		if (a > b) {
			if (b > c)
				ret = b;
			else if (a > c)
				ret = c;
			else
				ret = a;
		} else {
			if (a > c)
				ret = a;
			else if (b > c)
				ret = c;
			else
				ret = b;
		}
		return ret;
	}

	// 배열에서 두 인덱스의 값을 바꾸는 함수
	public static void Swap(int[] arr, int i, int j) {
		if (i != j) {
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
	}
    
    
    ///////////////////////////////////////////
    // Quick_Select 후보 2
    // 출처 : https://www.acmicpc.net/board/view/15547
	public static int quick_selection(int n, int[] ArrList, int k)
	{
	    if (ArrList == null || n <= k)
	        return -1;
	    
	    int start = 0;
	    int end      = n - 1;
	    
	    while (start < end)
	    {
	        int i = start;
	        int j = end;
	        int mid = ArrList[(i + j)/2];
	        
	        while (i < j)
	        {
	            if(ArrList[i] >= mid)
	            {
	                int tmp = ArrList[j];
	                ArrList[j] = ArrList[i];
	                ArrList[i] = tmp;
	                j--;
	            } else {
	                i++;
	            }
	        }
	        
	        if (ArrList[i] > mid)
	            i--;
	        
	        if (k <= i)
	            end = i;
	        else
	            start = i + 1;
	    }
	    
	    return ArrList[k];
	}
    
    // Quick_Select 후보 3
    // 출처: http://twinparadox.tistory.com/160 [Twinparadox Factory]
	public static int Quick_Select3(int arr[], int left, int right, int select)
	{
	    // 찾고자 하는 인덱스가 범위 내에 존재할 때,
	    if (select > 0 && select <= right - left + 1)
	    {
	        int pos = Partition3(arr, left, right);
	 
	        // 찾고자 하는 숫자를 찾은 경우
	        if (pos - left == select - 1)
	        {
	            return arr[pos];
	        }
	        // 찾고자 하는 숫자가 small group에 있는 경우
	        else if (pos - left > select - 1)
	        {
	            return Quick_Select(arr, left, pos - 1, select);
	        }
	        // 찾고자 하는 숫자가 large group에 있는 경우
	        else
	        { 
	            return Quick_Select(arr, pos + 1, right, select - pos + left - 1);
	        }
	    }
	    // 탐색 실패 시,
	    return -1;
	}
	
	public static int Partition3(int arr[], int left, int right)
	{
	    // 기본적으로 QuickSort의 Pivot 선정 후 교환 과정과 동일
	    // pivot은 가장 왼쪽의 인덱스로 결정
	    int pos = arr[left];
	    int low = left + 1, high = right;
	    while (low <= high)
	    {
	        while (low <= right && arr[low] <= pos)
	        {
	            low++;
	        }
	        while (high >= (left+1) && arr[high] >= pos)
	        {
	            high--;
	        }
	        if (low <= high)
	        {
	            Swap(arr,low,high);
	        }
	    }
	    Swap(arr,left,high);
	    return high;
	}
    
    // Quick_Select 후보 4
    // http://sexycoder.tistory.com/101
	// 빠른선택 함수 (재귀적으로 k를 만족시키는 범위안에 들어가도록 호출된다.)
	public static int quickSelect(int[] list, int left, int right, int k)
	{
	    int nth = Partition(list, left, right);
	 
	    if (nth == k) return list[nth];
	    else if (nth > k) return quickSelect(list, left, nth - 1, k);
	    else return quickSelect(list, nth + 1, right, k);
	}

	// pivot이 첫번째 값인 경우
	public static int Partition(int list[], int left, int right)
	{
	    int pivot = list[left];
	    int i = left + 1, j = right;
	 
	    while (i <= j) {
	        while (list[i] <= pivot && i <= right) i++;
	        while (list[j] >= pivot && j >= (left + 1)) j--;
	        if (i <= j) Swap(list, i, j);
	    }
	    Swap(list, left, j);
	    return j;
	}
}

kimjh9434 5년 전 0

참고로, 제가 구현한 1번 코드에서, 피벗을 선정하는 기준은, 맨 왼쪽, 맨 오른쪽, 그 중간 인덱스의 값 중에서 중간값을 피벗으로 설정했습니다.

djm03178 5년 전 2

이 문제는 이제 퀵 셀렉션을 매우 잘 구현해야 하는 문제가 됐습니다. 하지만 채점 서버가 너무 빨라서, 입출력만 빠르게 받으면 단순 정렬로도 무리 없이 풀리는 수준이 되기도 했씁니다.

kimjh9434 5년 전 1

음...................

모든 수가 다 같은 경우에 대해서 돌려보니 무한루프가 돌더군요.

조건문에서 '<'로 하면 안되서 '<='를 하니까, 제대로 정렬도 안되더군요.

일단 이부분의 문제점은 인지했습니다.

이 후, 고민을 하다가, 전에도 3개의 인덱스(맨 처음, 중간, 맨 끝)의값 중 중앙값을 피벗값으로 삼고 진행했었는데,

앗싸리 3개의 인덱스(front, mid, rear)의 값을 진작에 정렬시키고, 중앙값(arr[mid])을 피벗값으로 삼은 다음,

해당 피벗값을 잠시 구석에 보내고, 파티션을 진행 후, 다시 돌아오는 방식으로 구현을 해보았습니다.

그렇게 구현을 했지만, 이번에도 어김없이 4%의 벽을 넘어서지 못하고 시간초과가 나와서...

코드를 올리려고 하다가 뭔가 걸리는 점이 있어서,

https://drive.google.com/file/d/1aJA7Oqhlal1_mUxLpFdJ7_KFWCcTjcf5/view

5000000 5000000
0 0 0 0 ... 으로 0이 5000000개

에 있는 값을 직접 입력해 봤는데, 갑자기 멈추더군요.

1. 일단 제가 맨 처음에 입력받던 방식은 아래에 코드를 첨부해 놓았지만, StringTokenizer를 이용한 방법이었습니다. [이 방법+Quick_sork에서 99%에서 깨짐]

2. 그러다가 문자열은 .split(" ");의 함수를 써서 쪼개서 입력받을수 있다는 방법을 알고, 저게 훨씬 더 편해서 2번 방법을 이용했었습니다.

근데, 내부에서 어떻게 돌아가는지 알수가 없으니 몰랐는데,

str = br.readLine().split(" "); 방식의 경우, String.split(" ") 이 str[131064]까지 밖에 못만들어줘서 거기서 멈춰있더군요.

아마 이 때문에 시간초과가 나지 않았나 하는 생각도 듭니다.

그래서 설마설마 하면서 입력받는 방식을 1번으로 돌아와서 푼 결과 맞더군요!...

후, 문제 자체는 제 힘으로 해결했습니다. 그리고 그것과는 별개로, Quick_Sort에서 피벗 설정의 중요성,

문자열이 너무 클 경우, split를 이용하면 안되고, StringTokenizer를 이용해야 한다는 교훈을 얻을 수 있었던 문제였내요.

		// 맨 처음에 입력받던 방식1
        StringTokenizer st;
		int i = 0;

		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		A = new int[N];
		st = new StringTokenizer(br.readLine());
		while (st.hasMoreTokens()) {
			A[i] = Integer.parseInt(st.nextToken());
			i++;
		}

        // 그 다음에 입력받던 방식2
        String[] str;
		
		str = br.readLine().split(" ");
		N = Integer.parseInt(str[0]);
		K = Integer.parseInt(str[1]);

		str = br.readLine().split(" ");
		A = new int[N];
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(str[i]);
		}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

quick Selection 알고리즘을 써보는데 4%에서 넘어가질 못합니다...

kimjh9434 5년 전 0

kimjh9434 5년 전 0

djm03178 5년 전 2

kimjh9434 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

문제

문제

출처

ICPC

​quick Selection 알고리즘을 써보는데 4%에서 넘어가질 못합니다...

kimjh9434 5년 전 0

kimjh9434 5년 전 0

djm03178 5년 전 2

kimjh9434 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

quick Selection 알고리즘을 써보는데 4%에서 넘어가질 못합니다...