Quiz of Week 3 - Disjoint sets

Quiz of Week 3 - Disjoint sets

Week 3의 나머지 절반 강의를 마치고 바로 퀴즈를 풀었다.


이번에는 절반만 맞추면 되는 조건이지만 최대한 많이 맞추고자 하는 마음가짐으로 문제를 보자.


1번 문제는 Disjoint sets에 대한 명령어들을 주고 이에 대한 smallest elements를 찾아내는 것이다.


2번은 위의 1번 문제와 거의 같은 명령어들로 인해 이들의 rank를 고려하고 또한 이를 통해 생성된 트리들의 높이를 계산하여 곱한 값을 내야한다.


3번 문제도 for문을 통해 명령어들을 나열하였고 이를 통해 rank를 통한 disjoint tree가 완성이 될 때 트리의 갯수와 높이를 맞추는 것이다.


마지막 문제는 약간 더 복잡한 상황에서 트리의 최대 높이를 맞추는 것이다.


1번 문제와 2번 문제는 비교적 간단하게 맞출 수 있었는데 이는 밑의 그림과 함께 보는 것이 빠를 것 같다.


우선 2번문제의 답이며,


 위 두문제의 Union까지의 코드는 동일하므로 이에 대한 트리들과 rank는 위와 같이 정리될 것이다.
 따라서 1번 문제에서 find문들에 의해서 6이 포함된 트리의 최소값은 1, 3이 포함된 트리에서의 최소값은 3, 11도 같은 트리에 있으므로 최소값이 3, 마지막으로 9가 포함된 최소값이 1로 답은 1, 3, 3, 1이 된다.
 2번 문제에서는 이 트리들의 높이가 1, 2, 1이므로 이들의 곱은 2가 된다.



3번 문제는 아래와 같이 정리할 수 있겠다.


우선 Union API를 통해 구성이 될 때 rank를 기반으로 발달하므로 높이가 최소인 상태를 유지하게 된다. 따라서 트리는 한개이고 높이가 1인 상태가 된다.


마지막 문제는 노가다를 피하기 위해 최대 복잡도의 방식을 적용해보았는데 아쉽게도 틀렸다. 하지만 1문제 맞추자고 노가다를 하고 싶지 않으므로 패스.

댓글

댓글 쓰기