글 읽기 - find 함수 구현에 따른 시간차이

octo756 5년 전 1

find함수를 구현한 아래의 두가지 방식에서

첫번째 방식은 시간초과

두번째 방식은 정상통과 됩니다.

이

러한 차이를 가져오는 이유를 알고싶습니다.

int find(int a) {
	/*1번
	while (arr[a] != a) a = arr[a];
	return a;
	*/
    /*2번
	if (arr[a] == a) return a;
	else return arr[a] = find(arr[a]);
    */
}

djm03178 5년 전 1

2번은 path compression 기법입니다. Union find를 설명한 글이라면 대부분 이 기법에 대한 설명을 가지고 있고 1번이 안 좋은 이유도 설명하고 있으니 찾아보세요.

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

문제

문제

출처

ICPC

find 함수 구현에 따른 시간차이

octo756 5년 전 1

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말