문제 개요
의사와 엔지니어로만 구성된 특별한 가족이 있다고 가정해 보겠습니다. 이 가족에는 다음과 같은 규칙이 적용됩니다.
- 모든 사람은 반드시 두 명의 자녀를 둡니다.
- 엔지니어의 첫째 자녀는 엔지니어가 되고, 둘째 자녀는 의사가 됩니다.
- 의사의 첫째 자녀는 의사가 되고, 둘째 자녀는 엔지니어가 됩니다.
- 모든 세대는 항상 엔지니어부터 시작합니다.
예를 들어 4세대(level 4)의 2번째 위치(pos 2)에 있는 사람의 직업을 구하면 그 결과는 의사(Doctor)가 됩니다.
접근 방법
핵심 아이디어는 매우 간단합니다. 한 사람의 직업은 다음 두 가지 요소에 의해 결정됩니다.
- 부모의 직업: 자녀의 직업은 부모의 직업에 영향을 받습니다.
- 노드의 위치: 노드의 위치가 홀수라면 부모와 같은 직업을 갖고, 짝수라면 부모와 다른 직업을 갖습니다.
따라서 재귀적으로 부모의 직업을 먼저 구한 뒤, 위의 두 번째 규칙을 적용하면 현재 노드의 직업을 손쉽게 판별할 수 있습니다. 재귀 호출은 레벨이 1이 될 때까지 계속되며, 레벨 1의 첫 번째 사람은 항상 엔지니어('E')입니다.
예제 코드
#include<iostream>
using namespace std;
char getProfession(int level, int pos) {
if (level == 1)
return 'E';
if (getProfession(level-1, (pos+1)/2) == 'D')
return (pos%2)? 'D' : 'E';
return (pos%2)? 'E' : 'D';
}
int main(void) {
int level = 4, pos = 2;
cout << "The profession is: ";
if(getProfession(level, pos) == 'E'){
cout << "Engineer";
} else {
cout << "Doctor" ;
}
}실행 결과
The profession is: Doctor
코드 설명 및 복잡도 분석
getProfession 함수는 현재 노드의 부모 위치인 (pos+1)/2를 인자로 넘겨 재귀 호출을 수행합니다. 부모의 직업이 'D'(의사)라면 현재 위치가 홀수일 때 의사, 짝수일 때 엔지니어를 반환하고, 부모가 'E'(엔지니어)라면 그 반대로 반환합니다.
이 알고리즘의 시간 복잡도는 재귀 깊이에 비례하므로 O(log n)이며, 여기서 n은 노드의 위치(pos)입니다. 공간 복잡도 역시 재귀 스택 때문에 O(log n)입니다. 전체 트리를 탐색하지 않고도 원하는 위치의 직업을 빠르게 구할 수 있다는 점이 이 방법의 가장 큰 장점입니다.