kgood1   3년 전

유니온 파인드에서 부모 노드를 찾는  find함수를 정의할때 저는 1번코드로 정의해 왔는데

1번코드로는 계속 시간초과이고 2번으로 정리해서 쓴 코드만 통과할 수 있었습니다

차이가 뭔지 알려주실 수 있나요?

혹시 몰라서 전체 코드도 첨부하였습니다

39dll   3년 전

예를 들어 설명해드리겠습니다.

루트가 1인 집합이 있고, 해당 집합의 구조가 다음과 같다고 합시다.

1 - 2 - 3 - 4

이 때 2의 parent는 1, 3의 parent는 2, 4의 parent는 3입니다.

4의 parent를 구하는 과정은 다음과 같습니다.

1. 4의 parent를 구한다. (3)

 2. 3의 parent를 구한다. (2)

3. 2의 parent를 구한다. (1)

4. 1의 parent를 구한다. (1)

5. 1의 parent와 1이 같으므로 1을 반환한다.

우리가 4의 parent을 구할 때, 위와 같은 재귀함수의 구조로 인해 최악의 경우 O(N)의 시간 복잡도가 걸린다는 것을 알 수 있습니다. 그렇지만, 우리가 4의 parent를 구하면서 얻은 정보들을 활용할 수 있습니다.

우리는 3과 4의 parent가 1이라는 것을 알고 있습니다. 그렇기 때문에, 3과 4의 parent를 1로 바꿀 수 있습니다.

그 뒤부터는, 3과 4의 parent를 구할 때, 바로 1이 나오기 때문에 시간 복잡도가 O(1)이 됩니다.

이 테크닉을 경로 압축(Path Compression)이라고 합니다.

kgood1   3년 전

정말 감사드려요 ㅎㅎ

덕분에 하나 알아갑니다~~

lsj6445z   3년 전

좋은 질문 감사드립니다!

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