면접관이 자연수 하나를 생각할테니 그 수를 질문을 통해 맞춰보라고 합니다. 단, 질문에 대한 답은 예/아니오밖에 존재할 수 없으며 면접관은 거짓말을 하지 않습니다.
최소한의 질문으로 수를 맞추려면 어떤 전략을 짜야 할까요?
생각한 수가 X가 맞냐는 질문을 해서 맞다는 답이 나왔을 경우 최종적으로 수를 맞췄다고 인정합니다. 예를 들면
Q: 수가 1이 맞나요?
A: No
Q: 수가 2가 맞나요?
A: Yes
위와 같은 대화에선 2번만에 수를 맞춘 것입니다.
풀이 가리기
저는 이런 방법으로 풀었습니다.
- 바이너리 서치가 가장 빠를 것 같지만 수의 범위가 제한이 없으니 1의 자리부터 거꾸로 해나가면 된다.
- 언제 끝날지는 모르니 중간중간 계산을 해서 그 수가 맞는 지 확인을 해봐야 한다.
제가 생각한 시나리오는 다음과 같습니다.
Q: 생각한 수를 2진수로 변환했을 때 맨 오른쪽 자릿수가 1입니까?
A: Yes
Q: 그러면 생각한 수가 1입니까?
A: No
Q: 생각한 수를 2진법으로 변환했을 때 오른쪽에서 2번째 자릿수가 1입니까?
A: Yes
Q: 그러면 생각한 수가 3입니까?
A: Yes
그래서 다음과 같은 소스가 나왔습니다.
def is_number(orig, guess):
if orig == guess:
return True
return False
def is_number_nth_field_one(orig, n):
num = orig / (2 ** (n - 1))
if num % 2:
return True
return False
def guess_number(num):
count = 0
n = 1
guessing = 0
correct = False
while not correct:
count += 1
if is_number_nth_field_one(num, n):
guessing += 2 ** (n - 1)
count += 1
if is_number(num, guessing):
correct = True
n += 1
return count
if __name__ == '__main__':
total = 0
for i in xrange(1, 1000001):
count = guess_number(i)
total += count
print "guess %d, count: %d, total: %d" % (i, count, total)
print "Total: %d" % total
위의 방법으로 1부터 1000000까지의 수를 모두 돌려보면 총 37902890번의 질문을 합니다.
하지만 뭔가 더 질문의 수를 줄일 수 있을 것 같았습니다.
잘 살펴보면 알겠지만, 쓸모 없는 질문이 있습니다. N번째 자릿수를 물어봤을 때 0이었다면 생각한 수를 확인하는 과정에서 아까 아니라고 한 수를 또 물어봅니다. 다음과 같은 대화가 오가는거죠.
Q: 생각한 수를 2진수로 변환했을 때 맨 오른쪽 자릿수가 1입니까?
A: Yes
Q: 그러면 생각한 수가 1입니까?
A: No
Q: 생각한 수를 2진법으로 변환했을 때 오른쪽에서 2번째 자릿수가 1입니까?
A: No
Q: 그러면 생각한 수가 1입니까?
A: No
그래서 자릿수가 0일 땐 질문을 하지 않고 바로 다음 자리수로 넘어가게 했습니다.
def is_number(orig, guess):
if orig == guess:
return True
return False
def is_number_nth_field_one(orig, n):
num = orig / (2 ** (n - 1))
if num % 2:
return True
return False
def guess_number(num):
count = 0
n = 1
guessing = 0
correct = False
while not correct:
count += 1
if is_number_nth_field_one(num, n):
guessing += 2 ** (n - 1)
count += 1
if is_number(num, guessing):
correct = True
n += 1
return count
if __name__ == '__main__':
total = 0
for i in xrange(1, 1000001):
count = guess_number(i)
total += count
print "guess %d, count: %d, total: %d" % (i, count, total)
print "Total: %d" % total
아까랑 아주 살짝 다르죠. 이번에는 총 28836444번 질문을 했습니다. 아까보다 훨씬 줄었죠.
이것보다 더 좋은 해법이 있는지는 모르겠습니다. 더 좋은 답이 있다면 알려주세요.