정답
㉠ end, ㉡ (start + end) / 2, ㉢ (start + end) / 2 + 1이며, test() 함수의 호출 횟수는 127회이다.
출제 의도
이 문제는 이진 탐색 원리를 적용한 그룹 테스트 알고리즘의 동작을 이해하고, C 프로그램의 재귀 구조를 완성할 수 있는지와 함께 최악의 경우 테스트 함수 호출 횟수를 계산할 수 있는지를 평가한다.
풀이 과정
group_test 함수는 구간 [start, end]에 대해 한 번의 그룹 테스트를 수행한 뒤, 양성(POS)일 경우 구간을 둘로 나누어 재귀적으로 탐색하는 구조이다. 따라서 먼저 전체 구간에 대해 test 함수를 호출해야 하므로 ㉠에는 end가 들어간다.
구간이 하나의 혈액 샘플이 아닐 경우(start ≠ end), 이진 탐색 방식으로 구간을 반으로 나눈다. 첫 번째 재귀 호출은 왼쪽 구간 [start, mid], 두 번째 재귀 호출은 오른쪽 구간 [mid+1, end]가 되어야 하므로, 중간값 mid는 (start + end) / 2이다.
따라서 빈칸에 들어갈 코드는 다음과 같다.
㉠ end
㉡ (start + end) / 2
㉢ (start + end) / 2 + 1
이제 test() 함수의 호출 횟수를 계산한다. 혈액 샘플은 64개(0~63)이며, 이 중 1개만 감염된 경우를 가정한다. 최악의 경우, 매 단계에서 검사 결과가 양성이 되어 모든 하위 구간에 대해 테스트가 수행된다.
이는 높이가 6인 완전 이진 트리를 모두 방문하는 것과 같으며, 호출 횟수는 다음과 같다.
$$ 1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 $$
따라서 group_test(0, 63)을 수행할 때 test() 함수는 총 127회 호출된다.