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 2021-02-07 05:22:34
Processing time 0.0066 sec