글 읽기 - 메모리 초과, 혹은 런타임에러...

hnryu 7년 전 0

메모리 초과 혹은 런타임 에러가 나는데 소스를 어떻게 정리해야될지 조언 부탁드립니다.

개념적으로나 스킬부분이나 많이 부족합니다. 자세히 설명해주시면 감사하겠습니다. ㅜㅜ

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n;
	int *arr;    // char *arr 의 경우 : 메모리 초과  // int *arr 의 경우 : 런타임에러

	scanf("%d", &n);
	arr = (int *)malloc(sizeof(int)*n); //
	int i, j, temp;

	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);


	for (i = 1; i < n; i++) {
		for (j = 0; j < n - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	for ( j = 0; j < n; j++) {
		printf("%d\n", arr[j]);
	}
}

bupjae 7년 전 1

작성하신 프로그램은 공간복잡도 O(n) 시간복잡도 O(n²) 이며, 이 문제를 풀기엔 양쪽 다 너무 많습니다.

공간복잡도 O(1) 시간복잡도 O(n) 인 Counting sort 알고리즘이 있습니다. 이 알고리즘을 사용하기 위해서는 입력 데이터에 몇가지 조건이 붙는데, 이 문제는 그 조건들을 충족합니다.

Counting sort 구현 방법을 공부하시면서 어떨 때 사용할 수 있는지도 같이 공부해 보시기 바랍니다.

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

문제

문제

출처

ICPC

메모리 초과, 혹은 런타임에러...

hnryu 7년 전 0

bupjae 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말