글 읽기 - 제가 heapsort를 잘못 구현한건가요??

rhdtka21 5년 전 0

처음 stl 의 sort를 쓰니까 시간오류가 나서 heapsort를 구현했더니 제출하면 런타임 에러가 뜨네요

그래서 mergesort를 써서 통과는 했는데 heapsort 구현을 잘못한건가요?

#include <cstdio>

void swap(int *num1, int *num2){
	int temp;
	temp = *num1;
	*num1 = *num2;
	*num2 = temp;
	return;
}
void maxheap(int arr[], int i, int len){
	int p = i;
	int lc = p*2 + 1, rc = p*2 + 2;
	if(arr[lc] >= arr[p] && lc < len){
		swap(&arr[lc], &arr[p]);
		maxheap(arr, lc, len);
	}
	if(arr[rc] >= arr[p] && rc < len){
		swap(&arr[rc], &arr[p]);
		maxheap(arr, rc, len);
	}
} 

void heapsort(int arr[], int len){
	for(int j=0; j<len; j++){
		for(int i=(len-j)/2 - 1; i>=0; i--){		//초기 힙구조.
			maxheap(arr, i, len-j);
		}
		swap(&arr[0], &arr[len-j-1]);
	}
}
void merge(int arr[], int left, int mid, int right){
	...
}

void mergesort(int arr[], int left, int right){
	if(left>=right)
		return;
	int mid = (left + right)/2;
	mergesort(arr, left, mid);
	mergesort(arr, mid+1, right);
	merge(arr, left, mid, right);
}
int main(void){
	int N, K;
	scanf("%d %d", &N, &K);
	int arr[N];
	
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
    //heapsort(arr, N-1);
	mergesort(arr, 0,N-1);
	printf("%d", arr[K-1]);
	
	return 0;
}

bupjae 5년 전 1

13번째 줄과 17번째 줄에서 배열 범위를 검사하기 전에 배열 내용을 먼저 읽고 있습니다. 이래서야 배열 범위 검사가 의미가 없습니다.

rhdtka21 5년 전 0

bupjae 조언해주신대로 수정해서 제출하니 시간초과가 뜨는데요, 제가 알기론 힙정렬은 항상 nlogn을 보장한다고 들었는데 5,000,000 * log( 5,000,000) 하면 시간 내에 되는것 아닌가요?

bupjae 5년 전 1

24번째 줄 루프 안에 25번째 줄 루프를 넣어버리면 알고리즘 성능이 O(n^2) 이 나옵니다.

제일 처음에 배열을 힙으로 만들 때에는 전체 배열에 대해서 heapify 를 해야 하지만

정수를 하나 뺀 뒤에는 그 뺀 정수 하나에 대해서만 heapify 를 해야 합니다.

rhdtka21 5년 전 0

초기 heapify후에는 root를 계속 빼니까 저렇게 수정해봤는데 여전히 시간초과가 뜨네요 ㅠㅠ 이것도 제가 힙을 잘못구현한 것일까요?

void heapsort(int arr[], int len){

	for(int i=len/2 - 1; i>=0; i--){		//초기 힙구조.
		maxheap(arr, i, len);
	}
	for(int j=1; j<=len; j++){
		swap(&arr[0], &arr[len-j]);
		maxheap(arr, 0, len-j);
	}
	
}

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

문제

문제

출처

ICPC

제가 heapsort를 잘못 구현한건가요??

rhdtka21 5년 전 0

bupjae 5년 전 1

rhdtka21 5년 전 0

bupjae 조언해주신대로 수정해서 제출하니 시간초과가 뜨는데요, 제가 알기론 힙정렬은 항상 nlogn을 보장한다고 들었는데 5,000,000 * log( 5,000,000) 하면 시간 내에 되는것 아닌가요?

bupjae 5년 전 1

rhdtka21 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말