Test of Week 3
3주차 강의를 마치고 테스트를 보았다.
3문제 중 2문제 이상을 맞추면 통과한다.
1번 문제는 Heap의 정의에 대해 한번 더 설명하며 뒤죽박죽인 n개의 정수 배열을 O(n)의 반복으로 정렬할 수 있는지 묻는 문제이다.
2번 문제는 파티에 손님들에게 인사하는 로봇의 기능을 구현하는 것이다. 먼저 온 손님에게 그리고 나이 많은 손님에게 우선적으로 인사를 건네도록 구현하는 코드를 찾아야 한다.
마지막 문제는 Disjoint set에 Union 기능에 대한 정의를 하는 것이다. path compression과 rank heuristics를 모두 고려하여야 한다. 게다가 size까지 최신화해야 된다.
운좋게도 이번 시험은 한번에 모두 맞았으며 1번 문제부터 보자면 위와 같은 이유로 No가 답변이 되겠다. 복잡도는 O(n log n)이다.
2번문제는 3, 4 보기 중 헷갈렸는데 A를 우선순위로 보고 풀면 금방 해결 할 수 있다.
3번문제는 a와 b의 rank를 고려하여 결합하고(부모노드로 받아들이고) rank를 갱신시키는 부분이 추가 되어있으면 되겠다. 물론 size도 업데이트를 할 수 있는 코드까지. 모두 포함하는 것은 4번 보기가 되겠다.
3주차 강의를 마치고 테스트를 보았다.
3문제 중 2문제 이상을 맞추면 통과한다.
1번 문제는 Heap의 정의에 대해 한번 더 설명하며 뒤죽박죽인 n개의 정수 배열을 O(n)의 반복으로 정렬할 수 있는지 묻는 문제이다.
2번 문제는 파티에 손님들에게 인사하는 로봇의 기능을 구현하는 것이다. 먼저 온 손님에게 그리고 나이 많은 손님에게 우선적으로 인사를 건네도록 구현하는 코드를 찾아야 한다.
마지막 문제는 Disjoint set에 Union 기능에 대한 정의를 하는 것이다. path compression과 rank heuristics를 모두 고려하여야 한다. 게다가 size까지 최신화해야 된다.
운좋게도 이번 시험은 한번에 모두 맞았으며 1번 문제부터 보자면 위와 같은 이유로 No가 답변이 되겠다. 복잡도는 O(n log n)이다.
2번문제는 3, 4 보기 중 헷갈렸는데 A를 우선순위로 보고 풀면 금방 해결 할 수 있다.
3번문제는 a와 b의 rank를 고려하여 결합하고(부모노드로 받아들이고) rank를 갱신시키는 부분이 추가 되어있으면 되겠다. 물론 size도 업데이트를 할 수 있는 코드까지. 모두 포함하는 것은 4번 보기가 되겠다.
😍😍
답글삭제