{{| 문제 : 64층 (옥상포함) 중에서 사람이 떨어져 죽을 수 있는 층이 정해져 있다.
|}}

• 찾을 수 있나..;; 일단 코딩은 했는데 6번 죽어야 하던데... 알고리즘을 개선해야 하나..T.T 그런데 2의 6승이니까.. 6번죽어야 할꺼 같기도 한데..- 조현태
  
• 떨어졌을때... 뭔가 떨어진 거에 대한.. 답이 나오는건가? 더 높은 층으로 가라던지, 더 낮은 층으로 가라던지.? --(snowflower)
  
  • 떨어졌을 때 죽었으면 더 아래층,또는 그 층이고, 안죽었다면 더 윗층에서 죽겠죠? -아영
    

이 문제는 이진검색으로 풀 수 있습니다.
이진검색 이란 순서대로 (이진트리안에) 보관되어 있는 데이터를 검색하기 위해서 중간에 있는 (혹은 이진 트리의 루트에 해당하는) 값을 고른다음, 찾는 값이 그보다 크면 오른쪽으로 (값이 더 큰 쪽으로 ) 이동하고, 작으면 왼쪽으로 (값이 더 작은 쪽으로) 이동하는 방법을 의미한다. 유명한 알고리즘이므로 모르는 사람이 없으리라고 생각한다. -저자^_
예제;
임의의 층을 17층이라고 보자.

• 32층에서 떨어져 본다. 당연히 죽는다. 따라서 문제의 층은 32층보다 아래에 있다. 32를 다시 2로 나눈 값은 16.
  
• 16층에서 떨어져 본다. 죽지않는다. 따라서 문제의 층은 16층 보다 위에 있다. 32와 16사이에 존재하는 중앙값은 24이다.
  
• 24층에서 떨어져 본다. 죽는다. 따라서 24층보다 아래에 있다. 24층과 16층 중앙은 20층이다.
  
• 20층에서 떨어져 본다. 또 죽는다. 20층과 16층 사이에 있는 중앙은 18층이다.
  
• 18층에서 떨어져 본다. 역시 죽는다. 따라서 문제의 층은 18층 아래에 있다.
  

그러므로 16층과 18층의 중간인 17층이 정답이다.
(이 이진검색은 2의 배수일 수록 더 쉽게 찾아진다는 말이 있네요^_ )

이름

사용언어

코딩

----
Basic알고리즘