[python/알고리즘] 스무고개를 넘어보자

 

질문을 통해 답을 맞추는 놀이를 해보자

---

 

Q. 1,000 이하의 자연수 n을 생각할 테니 맞춰보시오.

 

A. 

   
  # 임의의 수 : 난수 (random 모듈 사용 : randint(a,b))
  import random

  def guess(answer, start, end):
      print(answer)
      while start < end :
          mid = (start+end) // 2
          if mid < answer :
              start = mid +1
          else:
              end = mid
      return start

  A = random.randint(1, 1000)
  print(guess(A, 1, 1000))
    

-> 1. 임의의 난수, 범위 시작 수, 마지막 수를 받는다.

    2.  범위의 중간을 계산하여 mid 변수에 넣고 임의의 난수와 비교한다.

    3.  중간값이 더 작을 경우에는 시작값을 중간값+1로 변경한다.

    4. 중간값이 더 클 경우에는 마지막값을 중간값으로 변경한다.

    5. 시작값이 마지막 값보다 커지면 끝난다.

 

Q. 몇 고개를 넘어야 답이 나올까?

 

A.

  
  # 몇 고개를 넘어야 답을 맞출까?
  def guess2(answer, start, end):
      count = 0
      while start < end :
          count += 1  # 카운트 추가
          mid = (start+end) // 2
          if mid < answer :
              start = mid +1
          else:
              end = mid
      return count

  B = random.randint(1,1000)
  print(guess2(B, 1, 1000))
    

-> count 변수를 추가하여 횟수를 세어본다.

 

---

 

log 란?

---

수학함수의 일종으로, 어떤 수를 나타내기 위해 고정된 밑을 몇 번 곱하여야 하는지를 나타내는 함수이다.

예를들어, a가 2이고 x가 3이면 b는 8이 된다. 이를 거듭제곱이라고 하며

반면에 a는 2, b가 8이면 x는 무엇일까? 이러한 x를 구하는 것을 로그(Logarithmic)라고 한다.

위의 수식에서 log다음의 a는 밑, b는 진수라고 한다.

로그에는 조건이 있다. 1. 밑은 1이 아닌 양수여야 한다.  ( a > 1 )

                             2. 진수는 1이상의 양수여야 한다.  ( b >= 1 )

 

• 이해를 돕기 위한 문제 풀기 

 

• python 으로 스무고개 문제를 풀고 문제와 log의 연관관계를 깨닫자

  
  start = 1
  for n in range(21):  # 0부터 20까지
      end = 2 ** n
      maxcount = 0
      for _ in range(1000):
          answer = random.randint(start,end)
          count = guess2(answer, start, end)
          if maxcount < count :
              maxcount = count
      print(start, end, maxcount, 2 ** n) 
      

< 출력 결과 >

start, end, count, 2**n

-> end는 2의 n(=count)승 값임을 알 수 있다.

    답을 구하기까지의 횟수(count)는 2의 지수를 뜻한다.

    즉, log의 식으로 보면 a는 2, b는 end값이 되고 x는 답을 구하기까지의 횟수가 된다.

 

 

출처 : Youtube 주니온TV 아무거나연구소의 코린아, 코딩하자! with 파이썬