글 읽기 - 수정]퀵 소트구현에서 궁금한게있습니다.

jow1025 4년 전 0

전에올렸던 질문이 애매해서 다시 수정해서올렸습니다.

이 소스에서 45행의 i<=end를 i<end로 바꾸면 예제의답은 출력되지만 시간초과로 오류가 뜹니다.

그림을그려서분석해봐도 i<end와 i<=end가 어떤차이가있는지 잘 모르겠습니다.

무한으로 루프가 도는걸방지하기위해 위 조건을 달아준건데 왜 =부등호가 빠지면 시간초과가 뜨는지 알려주시면감사하겠습니다!

#include<stdio.h>
int danji[315];
char graph[26][26];
int count;
int top;
int n;
void dfs(int x, int y);
void sort(int a[],int start,int end);
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", graph[i]);
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (graph[i][j] == '1')
			{
				dfs(i, j);
				danji[top++] = count;
				count = 0;
			}
		}
	}
	sort(danji,0,top-1);
	printf("%d\n", top);
	for (int i = 0; i < top; i++)
		printf("%d\n", danji[i]);
}
void sort(int a[], int start, int end)
{
	int temp;
	/*if (start >= end)
		return;*/
	if (start < end) {
		int key = start;
		int i = start + 1;
		int j = end;

		while (i <= j)
		{
			while (a[i] <= a[key] && i <= end)////문제의코드
			{
				i++;
			}
			while (a[j] >= a[key] && j > start)
			{
				j--;
			}
			if (i > j)
			{
				temp = a[j];
				a[j] = a[key];
				a[key] = temp;
			}
			else
			{
				temp = a[j];
				a[j] = a[i];
				a[i] = temp;

			}
		}
		sort(a, start, j - 1);
		sort(a, j + 1, end);
	}
}
void dfs(int x, int y)
{
	count++;
	graph[x][y] = '2';
	if (y != 0 && graph[x][y - 1] == '1')//왼
		dfs(x, y - 1);
	if (y != n - 1 && graph[x][y + 1] == '1')//오른쪽
		dfs(x, y + 1);
	if (x != 0 && graph[x - 1][y] == '1')//윗쪽
		dfs(x - 1, y);
	if (x != n - 1 && graph[x + 1][y] == '1')
		dfs(x + 1, y);

}

djm03178 4년 전 0

이 함수를 이용한 테스트입니다. 무엇이 출력되는지 보세요.

#include <stdio.h>

void sort(int a[], int start, int end)
{
	int temp;
	/*if (start >= end)
		return;*/
	if (start < end) {
		int key = start;
		int i = start + 1;
		int j = end;

		while (i <= j)
		{
			while (a[i] <= a[key] && i < end)////문제의코드
			{
				i++;
			}
			while (a[j] >= a[key] && j > start)
			{
				j--;
			}
			printf("%d %d\n", i, j);
			if (i > j)
			{
				temp = a[j];
				a[j] = a[key];
				a[key] = temp;
			}
			else
			{
				temp = a[j];
				a[j] = a[i];
				a[i] = temp;

			}
		}
		sort(a, start, j - 1);
		sort(a, j + 1, end);
	}
}

int main()
{
	int a[2] = { 2, 1 };
	sort(a, 0, 1);
}

jow1025 4년 전 0

코드분석할때 예제를 작은 경우부터 셈 해봐야겠네요. 감사합니다. !

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

문제

문제

출처

ICPC

수정]퀵 소트구현에서 궁금한게있습니다.

jow1025 4년 전 0

djm03178 4년 전 0

jow1025 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말