공지사항 / Notices

[15번 과제] 채점 데이터 및 예시 코드

by 조교_박상운, 12월 4일, 19:02

수강생 여러분 안녕하세요.

과제 15번 QUAD의 채점 데이터 및 예시 코드를 공지드립니다.

2의 거듭제곱 쿼드트리는 전체를 단위 화소까지 4분면으로 계속 나눌 수 있다는 특징을 이용해서 재귀함수를 이용해서 구현합니다.

이는 트리의 부모-자식관계를 하나하나 저장하는 구현 방식이 필요 없으며, 구성된 문자열 하나가 고유한 트리의 정보를 나타낸다는 특징을 가집니다.

따라서 정사각형의 꼭짓점 P1, 그 대각선 반대편 꼭짓점 P2를 인수로 받는 재귀함수 f(P1, P2)를 정의하고, P1과 P2의 좌표를 이용해 해당 정사각형을 사분할 하는 각각의 범위에 대해서 base case(단위 화소)까지 스캔을 실시하면 O(N log N)의 시간복잡도를 가지는 솔루션을 통해 Composition / Decomposition을 구현할 수 있습니다.