U E D R , A S I H C RSS

Basic알고리즘/63빌딩

Basic알고리즘/63빌딩

{{| 문제 : 64층 (옥상포함) 중에서 사람이 떨어져 죽을 수 있는 층이 정해져 있다.
그 층을 알기 위해서 다섯번을 떨어질 기회가 주어진다면, 어떤 방법으로 그 층을 찾을 수 있을까 ? (search알고리즘)
|}}

생각적기

  • 찾을 수 있나..;; 일단 코딩은 했는데 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의 배수일 수록 더 쉽게 찾아진다는 말이 있네요_ )
이진검색.gif

18층일때는?? 18층에서 떨어져 본다. 역시 죽는다(죽기 시작하는 층이므로..). 그러나 17층에서 떨어지면 안죽는다. 그러므로 18층이 정답이다.... 이러니까 6번탐색인게 아닌가요? - 조현태
그러고 보니, 그렇네 - 17층에서 죽느냐 안죽느냐에 따라서 그 층이 달라지는거잖아. 임의의 층이 17층이므로 17층에서는 죽어야겠네? -허아영
그렇지. 단순 바이너리 서치는 2의 n승개일때 n번의 탐색을 필요로 하니까... 이건 바이너리로는 안되.T.T - 조현태

코딩하기

코딩. 랜덤함수로 1 ~ 64 중의 수를 정한 다음, 자신의 방법을 통해서 찾아보자!
이름 사용언어 코딩

----
Basic알고리즘
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0850 sec