Tag: python

면접관이 자연수 하나를 생각할테니 그 수를 질문을 통해 맞춰보라고 합니다. 단, 질문에 대한 답은 예/아니오밖에 존재할 수 없으며 면접관은 거짓말을 하지 않습니다.
최소한의 질문으로 수를 맞추려면 어떤 전략을 짜야 할까요?

생각한 수가 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번 질문을 했습니다. 아까보다 훨씬 줄었죠.

이것보다 더 좋은 해법이 있는지는 모르겠습니다. 더 좋은 답이 있다면 알려주세요.