글 읽기 - 정답 속도에따른 성능차이가 궁금합니다!

jow1025 4년 전 0

코딩초보입니다.

평소에정답제출후 다른분들의 정답속도와 메모리잡아먹는양을 보는데요

초보다보니 4ms~0ms 사이내외로 잘 푸시는(메모리도 적당히만 사용하고)분들의 코드를 분석하려해도 이해가 아직 힘듭니다.

예를들어 4ms와 200ms 차이가 많이 심한건가요?

(단위를 여쭈어보는게아니라 보통 이정도의 차이가 코드의 질을 매기는데에 크게 관여가 되는지 궁금합니다)

아래의 제코드 같은경우도 나름 만족스럽게 짠 코드인데 실행속도를 비교해보니 썩 좋은 코드가 아닌것같아서 여쭙니다...

#include<stdio.h>
#include<stdlib.h>
int visited[10000];
int max;
int root;
typedef struct graphNode {
	int vertex;
	int weight;
	struct graphNode*link;
}graphNode;
graphNode**head;
void insertEdge(graphNode*Node, int v,int w);
void dfs(int vertex,int weight);
int main()
{
	int n;
	int parent,child, w;
	scanf("%d", &n);
	head = (graphNode**)malloc(sizeof(graphNode*)*n);
	for (int i = 0; i < n; i++)
	{
		head[i] = (graphNode*)malloc(sizeof(graphNode));
		head[i]->link = NULL;
	}
	for (int i = 1; i < n; i++)
	{
		scanf("%d %d %d", &parent,&child,&w);
		parent--;
		child--;
		insertEdge(head[parent],child, w);
		insertEdge(head[child], parent,w);
	}
	dfs(0, 0);
	dfs(root, 0);
	for (int i = 0; i < n; i++)
	{
		free(head[i]);
	}
	free(head);

	printf("%d\n", max);
}
void insertEdge(graphNode*Node, int v, int w)
{
	graphNode*newNode = (graphNode*)malloc(sizeof(graphNode));
	newNode->vertex = v;
	newNode->weight = w;
	newNode->link = NULL;

	while (Node->link != NULL)
	{
		Node = Node->link;
	}
	Node->link = newNode;
	
}
void dfs(int vertex, int weight)
{
	graphNode*temp = head[vertex]->link;

	if (max < weight)
	{
		root = vertex;
		max = weight;
	}
	visited[vertex] = 1;
	while (temp != NULL)
	{
		if (!visited[temp->vertex])
		{
			dfs(temp->vertex, weight+temp->weight);
		}
		temp = temp->link;
	}
	visited[vertex] = 0;
	
}

chogahui05 4년 전 0

insertEdge에 걸리는 복잡도가 O(n)입니다.

이것은 50번째 줄의 while문 때문에 나타나는 현상인데요. Node -> link가 NULL일 때 까지 계속 탐색하고 있어요.

그리고 Node -> link가 NULL일 때 Node -> link에 new_node를 넣는데 이것은 그냥 Tail에다가 추가한다는 의미거든요.

당장 Tree가

10000

1 2

1 3

...

1 10000

이렇게 주어지면 insert 함수 때문에 시간이 오래 걸릴 듯 싶네요.

순서가 중요하지 않다면

head에 추가하는 것이 적합합니다.

//add head[target] --> v
void insertEdge(graphNode*Node, int target, int v, int w)
{
	graphNode*newNode = (graphNode*)malloc(sizeof(graphNode));
	newNode->vertex = v;
	newNode->weight = w;
	newNode->link = head[target]; // [newNode] --> [original_head_data]
    head[target] = newNode; //head updated.
}

jow1025 4년 전 0

알려주신방법은 인접리스트를 이용한 그래프표현시에 각 vertex의 헤드포인터가 가리키는 graphNode가

오름차순으로 입력(표현)된다는 전제하에 사용되는방법이잖아요??

근데 인접리스트를 이용한 그래프 표현+dfs 돌릴시에 오름차순과 상관없이 입력된다는 전제하에

이런 툴을 사용하면 오름차순으로입력(표현)했을떄의 탐색루트가 다르잖아요.

그러나 말씀하신 "순서와 상관없다면"이 의미하는게 결국은 오름차순,내림차순 입력상관없이(탐색하는 순서가 달라도)결국은 이 툴 사용이 어차피 한번씩 방문하여 탐색하는것이므로 단순히 지름만 구하면되는거라 위의 툴을 사용해도되는거라고 이해해도되는건가요?

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

문제

문제

출처

ICPC

정답 속도에따른 성능차이가 궁금합니다!

jow1025 4년 전 0

chogahui05 4년 전 0

jow1025 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말