alssel2525   2년 전

일단 질문들에서 답을 구해서 주석처리한 8번 줄을 추가해서 맞았습니다!는 받았습니다.

저 줄이 없었을 경우에는 런타임에러가 났는데 무슨 차이가 있어서 어떤 과정으로 오류가 날 수 있는지 이해를 못하겠습니다.

저 줄이 없으면 에러가 나는 반례라도 구해주시면 감사하겠습니다.

구조를 트리형태로 생각하고 parents 집합에 각 노드의 부모노드를 저장하도록 했습니다.

시작할 때는 parents 집합에 각 인덱스와 같은 값을 집어넣어서 루트노드는 부모노드가 자기 자신인 것으로 했습니다.

bupjae   2년 전

8번 줄은 트리의 높이를 "압축"합니다.


예를 들어서 트리의 모양이 (부모) 1 - 2 - 3 - 4 - 5 (자식) 이런 식으로 되어있을 때 find(4) 를 수행하면 4의 부모인 1을 반환함과 동시에 1의 부모를 찾는 과정에서 방문한 4, 3, 2 를 직접 부모에 연결합니다.

find 를 하고 난 뒤에는 트리의 모양이 1 - 2, 1 - 3, 1 - 4 - 5와 같이 됩니다.

혹시 다음번에 다시 find(4)를 하게 될 때에는 굳이 3, 2를 방문할 필요 없이 곧장 1을 방문한 뒤 1을 반환하게 되겠지요.

또한, 이러한 압축을 하지 않는다면, 트리의 모양이 완전히 선형일 때, 재귀호출의 깊이가 최대 n단계가 되는데, 이를 버틸 수 있는 파이썬 구현체는 보기 힘들 겁니다.

alssel2525   2년 전

@bupjae 

답변 감사합니다. n의 범위를 간과했었네요. 

그렇다면 8번줄이 없더라도 비효율적인 알고리즘이 될 뿐, find 자체가 작동을 못하는 것은 아닌거지요?

bupjae   2년 전

올바른 답을 출력하긴 합니다.


하지만, 알고리즘의 수행 속도가 매우 느리고 ( O(m) vs O(nm) ), 재귀호출 깊이로 인한 오류 발생 가능성도 있기 때문에 이 알고리즘을 구현할 때는 높이 압축을 반드시 해야 한다라고 이해하는 것이 좋습니다.

alssel2525   2년 전

답변 감사합니다!

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