IBM인가 Google의 면접 문제랍니다(재미있는 논리퀴즈).

글쓴이: 홍원범 / 작성시간: 금, 2007/04/20 - 8:48오후

미국에서 프로그래머로 활동 중인 사촌 동생이 심심할 때 풀어보라고 내준 문제입니다. IBM인지 Google이었는지 잘 기억이 나지 않습니다만(아마 IBM이었을 겁니다), 면접 때 자신이 직접 받았던 문제라고 했습니다. 15분인가 시간을 주어지는데, 면접관들 앞에서 문제를 해결해야한답니다. 답보다는 그 답에 접근해가는 방식을 유심히 관찰하더라고 전하더군요. 저는 고심 끝에 못풀고 포기한 뒤 답을 들었습니다. 컴퓨터를 공부하는 제 동생은 풀어내더군요.

키가 모두 다른 100명의 사나이가 있는데, 이들을 키 순서대로 세운 뒤(맨 앞에 제일 작은 사나이),
다음과 같이 발표를 합니다.

"이제 당신들에게 흰 모자와 검은 모자 도합 100개를 분배하여 한 사람 당 하나씩
무작위로 씌울 것이다. 그리고 뒤(제일 키가 큰 사람)에서부터 한 사람씩 자신이 쓴
모자의 색이 무엇인지 질문을 받게 될 것이다. 모자는 위에서 내려오기 때문에 당사자는
자신의 모자색을 알 수 없다. 그래도 맞춰야 한다. 맞추지 못하면 탈락할 것이다.
대신, 여러분은 모자를 쓰기 전에 한번 모두 모여 토의를 할 시간을 얻는다.
이 토의 시간 동안 최대한 많은 인원이 살아 남을 수 있는 방법을 고안하라.
단, 일단 모자를 쓰고 질문을 받은 이후에는 '검정색', '흰색'이라는 두 단어 이외에는
다른 말을 할 수가 없다는 점에 유의하고 신중하게 답하도록. 줄을 서 있는 상황에서는
상호 간에 아무런 대화도 할 수 없으니 토의 때 열심히 이야기하길 바란다."

그래서 이 사나이들은 모두 모여서 열심히 토의를 했습니다. 그리고 다시 키 순서대로 줄을 좌악 선 뒤에 모자가 위에서 내려왔고, 맨 뒤의 제일 키가 큰 사람부터 한 명씩 자신의 모자 색을 이야기했습니다. 그리고 99명의 사나이가 시험에 합격했습니다. 한번 더 시험을 치뤘을 때에는 100명이 모두 합격하기도 했습니다. 아무튼 100명 모두가 합격하거나 한 사람을 제외하고는 모두 합격할 수 있는 방법을 고안해 낸 것입니다.

과연 이들이 고안한 그 방법이란 과연 무엇일까요?

추가 설명 조건 - 키 순서대로 서 있으므로, 나는 나보다 키가 작은 사람들의 모자 색을 모두 알 수 있습니다. 100명이 좀 많은 숫자이긴 하지만, 제일 키가 큰 사나이는 제일 키가 작은 사나이의 모자 색도 알 수 있을 만큼 이 사나이들의 눈이 모두 좋다는 점을 전제로 합니다.

먼저 충분히 생각해보신 뒤에 댓글들(스포일러와 답이 숨어있을 수 있습니다! 주의하세요!)을 확인하세요^^

아아, 제가 부디 문제를 정확히 기억하고 있는 것이길 바라는 바입니다.

Forums:

자유 게시판

제가 생각한

글쓴이: withwind / 작성시간: 금, 2007/04/20 - 9:05오후

제가 생각한 방법입니다.

조건
1. 키가 큰 사람은 작은사람의 모자를 볼수 있다.
2. 힌색 , 검정색 외에는 다른말은 할수 없다.

방법
1. 제일 키가 큰 맨뒤 첫번째 사람이 자신의 모자 색(50% 확률)
말한뒤 앞사람의 모자색을 말한다.
( 조건 2에 의해 한마디만 해야 한다는 조건이 없으므로)

그렇다면 맨뒤의 사람이 정답일 확률이 50% 이므로
99명 혹은 100명이 정답이 될 것 이다.

2. 방법 1과 같은 사항이지만 조건 2의 제약 조건이 한마디만 해야
한다 라면 사람들은 각각의 프로토콜을 만들어 다음과 같은 방법으로
대답을 한다.(발음의 길이를 이용한다.)

자신 | 앞사람 | 대답
힌색 힌색 하~~얀색
힌색 검정 하얀색
검정 힌색 검~~정색
검정 검정 검정색

타당한가요??

평가 부탁 드립니다.

ps. 재미 있었습니다. 저는 2분정도 소요 되었습니다.
-----------------------------------------------
바람처럼 살고 싶지만 그리 하지 못함을 분명히 안다.

-----------------------------------------------
바람처럼 살고 싶지만 그리 하지 못함을 분명히 안다.

이런 식으로 풀 수

글쓴이: 익명사용자 / 작성시간: 금, 2007/04/20 - 9:20오후

이런 식으로 풀 수 있다면

100번째 사람은 99번째 사람의 모자색을 얘기하며
99번째 사람은 자신의 모자색과 98번째 모자색이 같으면
앞으로 나란히 같은 행동으로 표시를 하며 얘기하고
다르면 그냥 얘기하면 되겠군요.

자신의 모자색은 전 사람이 앞으로 나란히 하며 얘기했다면
그가 말한 모자색이 자신의 모자색이고
그런 표시가 없으면 반대색입니다.

물론 자신의 모자색을 얘기할때는 옆사람의 것과 같은지 다른지
앞으로 나란히로 표시합니다.

출제자가 원한 답은

글쓴이: creativeidler / 작성시간: 일, 2007/04/22 - 11:40오후

출제자가 원한 답은 아니겠지만 현실 세계(?)에서라면 패리티 비트를 이용한 방법보다 더 말이 되는 것 같네요.

헉.. 위엣분 엄청 빨리 푸셨는데 정답은 아닌듯...

글쓴이: zilitwo / 작성시간: 금, 2007/04/20 - 9:17오후

전 한참 생각했습니다. 한 20분 정도..
풀긴 푼것 같습니다.
예를 들어 젤 뒷사람이 나머지 99사람의 모자를 보고
흰색 모자가 짝수개 일때 젤 뒷사람은 "흰색" 이라 말합니다.
또한 99명의 흰색 모자가 홀수개일때 "검은색" 이라고 말합니다.
그렇다면 99번째 사람은 자신의 모자 포함 흰색모자의 갯수가 짝수개인지 홀수개 인지 알수가 있습니다.
예를 들어 젤 뒷사람이 "흰색" 이라고 말했습니다.
이경우 99명의 모자중 흰색모자의 갯수가 짝수개라는 뜻이되겠죠?
자신이 보고 있는 98개의 모자중 흰색이 짝수개라면 자신의 모자는 검은색이 되고 홀수개라면 자신의 모자는 흰색이 됩니다.
그렇다면 98 번째 사람은 자신의 모자포함 흰색 모자가 짝수개인지 홀수개인지 알고 99번째 사람의 모자색을 99번째 사람이 말할때 들어서 알고있으므로 자신의 모자색도 바로 나오게 되는거죠
이런식으로 1번째 까지 가면 100번째사람만 틀릴수가 있고 나머지 사람들은 다 정답을 알 수가 있습니다 ^^

오랜만에 왔는데 재미있는 문제가 있네요 ㅋㅋ
오랜만에 이런문제 풀어보니까 재미있네요 ^^

전 한참 뒷사람이 앞사람의 모자색을 말해줘야 한다고 생각을 하고 한참 고민을 했는데.. 뒷사람 모자색이 어떤색이 될수도 있으니까 불가능 하더라고요;;
그래서.. 흰색 검은색이 컴퓨터에 0 과 1 을 말하는거겠고..
자신의 모자색을 맞춰야 하기때문에.. 그와 관련된 알고리즘을 생각을 해봤죠, 바로 패리티비트가 떠오르더군요 ㅋㅋ
패리티비트를 이용한 문제네요 ^^

-----------------------------------
속좀 썩이지 마라~~ 잉???

사람의 수가 x명이고,

글쓴이: masoris / 작성시간: 금, 2007/04/20 - 9:51오후

사람의 수가 x명이고, 모자의 종류가 y가지 일때, 가장 마지막에 대답한 x-y+1명의 사람이 자신의 모자를 정확히 알 수 있네요.

zilitwo님 글을 보고 나서야 정답을 알았습니다.

____
The limits of my language mean the limits of my world. - Ludwig Wittgenstein

zilitwo님 풀이가 맞긴 한가요?

글쓴이: cliffet / 작성시간: 화, 2010/04/06 - 3:30오후

3년이나 되가는 글타래에 답글다는게 좀 그렇긴한데

글이 새로 갱신이 되서 올라왔길래 우연히 보게됐습니다. 풀이를 보니 zilitwo님 풀이에 다들

수긍해하시는거 같아서 반례를 하나 들어볼까합니다.

흰색을 o, 검은색을 x라고 봅시다. 키작은 순으로 나열해보면

oooxoxoo ... ooxxx <--100번째 사람
|---o가 짝수개---|

zilitwo님의 방법대로라면 위의 예에서 마지막 100번째 사람이 흰색이라고 말하겠죠

그러면 99번째 사람은 자신이 검은 모자라는 사실을 알겁니다. 하지만 자신의 모자가 검은색인

것을 알 수는 있지만 검은색이라고 말할 수는 없죠. 자신앞의 흰색모자가 짝수이기때문이죠.

zilitwo님 방법은 모든 사람이 자신의 모자색깔을 알 수는 있지만 최소 99명이 면접시험에서 합

격할 수는 없는 방법입니다

패리티란 개념을

글쓴이: neogeo / 작성시간: 화, 2010/04/06 - 3:37오후

패리티란 개념을 상상해 보시면 간단히 풀립니다.

99 번째 사람은 앞사람의 모자갯수랑 상관없이 검은색이라고 말합니다.

98 번째 사람은 뒷사람이 검은색이라고 말했으므로 자신의 시야내에 보이는 하얀모자수가 짝수인지 홀수인지 알고 있고, 앞사람이 검은색이라고 말했던 것을 참조해보면 현재 자신을 포함한 전체 하얀모자수가 짝수인지 홀수인지 알 수 있지요.( 99번째사람이 검정이라고 했으니 98번째 사람입장에선 100번째 사람이 말했던 전체의 홀수 짝수 여부는 바뀌지 않았음을 쉽게 유추 가능합니다. ) 따라서 자신의 모자가 흰색인지 검은색인지 알 수 있습니다.

한사람 한사람의 목소리가 100명 전체에게 들린다는 가정이 있었으므로 각 사람은 마음속에 자신의 시야내에 보이는 하얀모자가 홀수인지 짝수인지 여부와 현재 남은 모자가 짝수상태인지 홀수 상태인지 뒷사람의 목소리를 들으면서 하얀색이란 답이 나올때마다 state 를 change 해주면 됩니다. ( 짝수 -> 홀수 , 홀수 -> 짝수 ) 그리고 자신의 보아두었던 시야내의 모자가 홀수인지 짝수인지와 현재 남은 모자가 홀수인지 짝수인지 여부를 비교하면 손쉽게 자신의 모자색깔을 유추할 수 있고 답도 말할 수 있습니다.

핵심은 뒷사람이 말하는걸 앞사람이 전부 듣고 있다는겁니다.

Neogeo - Future is Now.

다시 제 생각을 설명드리면

글쓴이: cliffet / 작성시간: 화, 2010/04/13 - 10:09오후

이 문제는 최소 99명이 면접에서 합격하는게 목표이지 모자의 색을 알아내는게 목표가 아닙니다.
제가 지적한 부분은 ===자신의 모자색을 알 수는 있지만=== 자신의 모자색을 답으로 말할 수는 없다는 겁니다.
모든 사람들은 문제풀이를 시작하기 전에 자신이 말해야 하는 색깔이 이미 처음부터 결정되어 버립니다.
(뒷사람의 말을 듣지 않아도 자신 앞의 흰색모자가 짝수냐 홀수냐는 알 수 있는거니까요)

자기 차례에 말해야 하는 색깔이 '자신의 모자 색'과 '자신 앞의 흰색모자의 홀/짝 여부' 두가지 의미를 (이 방법으로는) 동시에 담을 수가 없는거죠. 그래서 이 풀이가 문제에서 요구하는 답은 아니라는 것이었습니다

w가 흰색, b가 검은색이라고 하면
1234567890
wwbwbbwbwb 순으로 서있다고 하면 위 방법에 따라 답을 한다고 하면 1번부터 차례대로 색을 말한다고 할 때
wbbwwwbbww 순으로 답해야 합니다.

적어도 2~0번까지는 모두 답을 맞힐 수 있어야하지만 그러지 못함을 알 수 있죠

음 자신의 모자색을 그냥 답으로

글쓴이: ilios / 작성시간: 수, 2010/04/14 - 12:26오전

음 자신의 모자색을 그냥 답으로 얘기하면 됩니다.

그리고 앞사람들이 쓰고있는 흰색 모자 갯수를 센후에 바로 답을 낼 수 있는 사람은 키가 젤 큰사람 혼자이죠.
("모든 사람들은 문제풀이를 시작하기 전에 자신이 말해야 하는 색깔이 이미 처음부터 결정되어 버립니다." 라고 쓰셨길래...)

나머지 사람들은 자신보다 키가 큰 사람들이 얘기를 한 후에서야, 자신의 모자색깔을 알아낼 수 있겠네요.

그런데 문제에는

글쓴이: ydhoney / 작성시간: 일, 2007/04/22 - 6:18오후

흰색 모자와 검은색 모자의 숫자가 동일하다는 조건이 없지 않아요?　이를테면 흰색 20개와 검은색 80개라거나..

추가;;

아..그거랑 상관없이 자기 앞에서 보이는 홀짝이구나..

=3=33
　
====================여기부터 식인어흥====================
어흥 몰라 어흥? 호랑이 어흥!! 떡 하나 주면 어흥!! 떡 두개 주면 어흥어흥!!

제 생각이 무척

글쓴이: withwind / 작성시간: 금, 2007/04/20 - 9:29오후

제 생각이 무척 짧았습니다.

zilitwo님의 답을 보고 무릎을 탁~ 치게 되는군요.

하지만 재미있었습니다. ^^;;
-----------------------------------------------
바람처럼 살고 싶지만 그리 하지 못함을 분명히 안다.

-----------------------------------------------
바람처럼 살고 싶지만 그리 하지 못함을 분명히 안다.

countx //앞쪽의 검은색

글쓴이: 익명사용자 / 작성시간: 토, 2007/04/21 - 12:02오전

countx //앞쪽의 검은색 모자의 카운트갯수
county // 뒷사람이 부른 검은 모자 카운트
sum=x+y

if sum==49
printf("당신 모자의 색깔은 검은색입니다.")

else
printf("당신 모자의 색깔은 하얀색입니다.")
fi

//검은모자:하얀모자의 갯수가 동일할 경우..
//검은모자와 하얀모자의 비율을 알 수 없을 때는 오류..

.. 허접..

쩝.. 죄송.. 문제를

글쓴이: 익명사용자 / 작성시간: 토, 2007/04/21 - 12:35오전

쩝.. 죄송..
문제를 자세히 읽지 않았습니다.

100명이 다 맞추는 것이 아니라 99명이 맞추고 1명이 틀릴 수도
맞출 수도 있을 경우네요..

모두 카운터하지 않고 자기 바로 뒷사람의 모자색깔만 알고
자기 앞의 모자만 카운트 되면 알수 있는 것 같습니다.

제일 앞에 선 사람은 카운트할 수 없으므로
계산이 되지.. 않으니.. 확률은 반반..

잘못된 해답.. 죄송.. 재밌네요..

이와 비슷한 문제가 있었는데...

글쓴이: ultrasound / 작성시간: 토, 2007/04/21 - 12:43오전

ㅋ 저는 한참을 생각 하다가 못 풀었었는데...저런 방법들이 있었군요..
항상 이런 문제들을 마주치게 되면 이상하게 문제속에서 자신의 생각을 제한하게 되어 더욱 풀지 못하고 빙빙 도는 경우가 많이 생기 는거 같습니다.ㅋ

ㅎㅎㅎ 재밌네요

글쓴이: ixevexi / 작성시간: 토, 2007/04/21 - 5:02오전

하나 더 가볼까요?
어디서 읽었는지 가물가물 한데...
여기에서 올라온 적은 없는듯 합니다.

문제 들어갑니다.

한 섬에는 몇명의 주민들이 있습니다.
이 주민들은 의사소통을 서로 하지 못합니다.
1. 다만 하루에 한번 서로 한 장소에 모여서 다른사람들을 봅니다.

어느날 몇명의 마을 사람들은 어떤 전염병에 걸리게됩니다.
(모든 마을 사람들은 전염병이 발생했다는 걸 알게됩니다.)

2 .이 마을 사람들은 자신이 병에 걸렸는지 안걸렸는지 스스로
알 수 없지만 다른 사람이 병에 걸린 것은 눈으로 불 수 있습니다.

3. 이 마을 사람들은 자신이 전염병에 걸렸다는 사실을 알면
모임에 나오지 않습니다.

전염병이 마을에 발병했다는 것을 알고
15번을 모인 후(15일 후겠죠?) 16일쨰 되던날 전염병에
걸린 사람들은 모두 모임에 나오지 않았습니다.
그동안 추가적으로 병에 걸린 사람이 없다고 했을 때
몇명이나 전염병에 걸렸던 걸까요?
-----------------------------------------------
C++, 그리고 C++....
죽어도 C++

C++, 그리고 C++....
죽어도 C++

아무도 답을 안달았길래...

글쓴이: zilitwo / 작성시간: 일, 2007/04/22 - 10:09오후

제가 알고 있는문제랑 엄청 비슷하네요
전 자신의 개가 미쳤다고 생각하면 쏴죽이라는 거였는데
4일째 되던날밤 몇발의 총성이 울렸죠
미친개는 몇마리일까요? 였는데..
내용은 완전히 같은 문제네요..
16일째날 모임에 나오지 않았다면 15명이 전염병 환자네요 ^^

-----------------------------------
속좀 썩이지 마라~~ 잉???

아차.. 왜 15명이 전염병 환자인지 설명이 필요하겠군요..

글쓴이: zilitwo / 작성시간: 일, 2007/04/22 - 10:18오후

예를 들어 전염병에 1명이 걸렸다고 생각합시다.
이때 전염병이 퍼진걸 알기때문에 전염병이 걸린사람은 최소한 1명은 존재합니다.
이때 1명이 걸렸다고 생각한다면 전염병이 걸린 사람의 입장에서 한번 모였을때 다른 모든 사람을 봤을때 아무도 전염벙에 걸리지 않았다면 그사람은 바로 다음날 나오지 않았을것입니다.

예를 들어 2명이 전염병 환자라면..
첫번째 모임에서 1번 전염병 환자가 마을사람들을 봤을때 2번전염병 환자를 보게되고, 전염병 환자가 하나 있으니까 자신이 전염병환자인지 아닌지 알수 없습니다. 고로 1번 전염병 환자는 다음날도 모임에 참석을 하겠죠.
2번 전염병 환자 역시 같은 이유로 다음날 모임에 참여를 하게 됩니다.

2번째 모이는날..
2번째 모이는날 역시 모든 사람이 모였습니다.
이때 1번 전염병 환자가 봤을때 전염병 환자가 2번전염병 환자 혼자라면 2번전염병 환자가 나오지 않아야 하는데 2번째 모임에 2번 전염병 환자가 나왔으므로, 전염병 환자가 더 있다는 예기가 되겠죠?
물론 그게 자신이 됩니다.
고로 3번째 모이는날 2명의 전염병 환자가 나오질 않습니다.

전염병 환자가 3명일때..
역시 위와 같은 방법대로 3번째 모이는날도 모두다 참석을 하게되죠
그리고 3명모두 자신이 전염병 환자임을 알고 4번째 모이는날 참석을 하지 않게 됩니다.

고로.. 16일째 되던날 전염병에 걸린 사람이 모두 참석하지 않았다면 전염병 환자는 15명이 됩니다. ^^

예전에 풀었던 문제네요 ^^

;;; 추가로~
전제조건이 더 필요한게 마을사람들 전체가 머리가 꾀 좋아야 합니다.
모두 이정도 논리력을 가지고 있어서 이런 생각을 한다는 전제조건입니다. ^^;;;

-----------------------------------
속좀 썩이지 마라~~ 잉???

재미로 귀납적으로 증명을 붙여봤습니다

글쓴이: Ooryll Qrygg / 작성시간: 월, 2010/04/05 - 2:44오후

there are total S people dwelling in an island.
if there are n patients, after n_th meeting only healthy people are left (in the meeting)

proof.

for the case of one patient, this holds as shown above.

Given that this holds for n patients, suppose that there are n+1 patients.
Then, after n_th meeting, each patient will see n patients attending the meeting, concluding that there are more than n patients (according to induction hypothesis)
Because he sees n patients and S-(n+1) healthy people, he comes to aware that he is one of the patients, and he does not attend the next meeting.
Therefore, after n+1 th meeting, only healthy people attend the meeting.

Thus, after as many meetings as the number of patients, only healthy people attend the meeting.

정답+첨언

글쓴이: 홍원범 / 작성시간: 일, 2007/04/22 - 2:47오후

여러 분들께서 답을 달아주셨네요^^
Zilitwo님 패리티비트까지 생각하셨군요. 대단하십니다^^
정확하게 파악하고 계신 것 같습니다. 애초에 문제를 내 준 사촌동생이 저에게 말해준 답안도 바로 그것이었습니다.
첨가를 더 하자면(여기서부터는 문제를 풀어본 제 후배가 지적한 부분과 그에 대한 해결책입니다), zilitwo님의 답변에는 맨 뒷의 제일 키 큰 사나이부터 주욱 흘러내려오는 모든 답안을 맨 앞의 가장 작은 사나이까지 다 들을 수 있다는 전제가 들어있습니다. 그렇지 않으면 모자의 색을 맞출 수가 없는 것이죠. 제 후배는 이 지점에 태클을 걸더군요. '어떻게 100명의 소리를 다 들을 수 있느냐? 못맞추면 시험에 탈락한다는데 쉽게 목소리가 나올 수 있겠냐? 행여나 자칫해서 못들으면 어떻게 하나? 게다가 그 상황에서 내(x) 앞의 100-x 명의 모자 색이 어땠는지 계산하는 것도 쉽지 않은 것이 아니냐?(모든 종류의 계산이 어려운 사회과학도입니다..;;)'라고 의문을 제기했습니다. 그 지적도 일리가 있다고 생각합니다. 그래서 다른 방법을 곰곰히 생각해봤습니다.

제가 이 문제의 댓글들을 처음 보고 가장 놀란 게 withwind님의 답변때문이었습니다. 제가 방금 제기한 문제의 해답이었거든요. 모자를 쓴 나는, 나 이전에 모자색을 말한 사람들의 발언들을 모두 다 들을 필요없이 내 뒷 사람의 말을 듣고 내 모자색을 파악하여 말하면서 동시에 내 앞에 남은 사람들의 홀짝을 이야기해주는 것입니다. withwind님이 지적하신대로 사람들 간의 프로토콜을 정해서 정보를 끊임없이 전달해주는 것이죠. 그래서 zilitwo님과 withwind님의 답안을 결합하면 제 후배가 제기한 문제도 함께 해결할 수 있습니다.

홀짝 계산과 장단음 구분을 합치는 것입니다. 이를테면, 내 모자색이 흰색이라고 판명이 된 경우(zilitwo님의 방법으로), 저는 '흰색'이라고 답을 하면서도 제 앞의 흰 모자의 갯수가 홀수라면 '흰~~색'이라고 이야기하고, 그 갯수가 짝수라면 '흰!색!'이라고 이야기합니다. 그러면 이제 제 앞 사람은 굳이 맨 뒤의 제일 큰 사나이부터 지금까지의 모자색을 모두 다 듣지 않았더라도 자신의 모자가 어떤 색인지 파악할 수 있게 됩니다. 그렇게 주욱 가장 작은 사람까지 가면 되구요.^^

함께 풀어보니 재밌습니다^^

근데 ixevexi님, 저는 그 문제는 도저히 못 풀겠습니다. 마을 주민들이 서로 의사소통을 할 수 없는데도 자신의 발병을 인지한다는 건, 각각의 사람들이 추측을 한다는 것이겠죠? '나는 병에 걸린 것 같다. 그러니 모임에 나가지 말아야지.' 혹은 '나는 병에 안 걸린 것 같다. 그러니 모임에 나가야지.'라고 말이죠. 근데 그렇게 되면 너무 경우의 수가 많아지는 것 같고 계산이 안 될 것 같습니다. 가령 실제로 발병하지 않은 사람은 두 가지 방식으로 생각할 수 있겠죠? '엇, 병에 걸린 사람들이 있잖아? 그럼 혹시 나도?'라고 생각한다거나, '엇, 병에 걸린 사람들이 있잖아? 근데 안 걸린 사람들도 있네? 나도 아마 안 걸렸을거야.'라고 생각할 수 있을 겁니다. 마찬가지로 발병한 사람들도 이 두 가지 방식으로 생각하겠죠? 제가 너무 심리적, 사회과학적으로 접근하고 있나요?^^ 저도 ultrasound님처럼 빙빙 한 곳에서만 돌고 있는 모양입니다. ixevexi님, 부디 답을 가르쳐주세요~~^^

Open-Source Anthropology

"홀수라면

글쓴이: fortson / 작성시간: 일, 2007/04/22 - 5:28오후

"홀수라면 '흰~~색'이라고 이야기하고, 그 갯수가 짝수라면 '흰!색!'이라고 이야기합니다."
앞에있는 사람 모자가 검은색이면 길게 발음하고 흰색이면 짧게 발음하는거랑 별반 차이가 없을듯

ㅎ 전이문제

글쓴이: ㅡ,.ㅡ;; / 작성시간: 월, 2007/05/28 - 6:27오후

ㅎ 전이문제 읽는면서 이게 문제가 될까 생각했었습니다..ㅎㅎ

그냥 앞사람이 흰색이면 억양을 올리고 검은색이면 억양을 내립니다..

첫번째 사람은 아무렇게나 말하면되고 두번째사람부터는 뒷사람의 억양으로 자신의 색을 알수있고.

앞사람색은 다시 억양으로 정보를 전달하면되는데.. 라고...

그런데 이렇게 쉽게 푸는건 역시 논리문제가 아니겠죠?ㅋ 뒷쪽리플들을 조금더읽어보니 답이나와있군요.ㅎ
그런데 발음에 복잡하게 홀짝을 표시할필요까지 없는듯.

----------------------------------------------------------------------------
C Library Development Project

----------------------------------------------------------------------------

ixevexi님 퍼즐의

글쓴이: Ooryll Qrygg / 작성시간: 토, 2010/04/03 - 1:50오후

ixevexi님 퍼즐의 트릭은
전염병 환자는 건강한 사람보다 전염병 환자를 한명 덜 보게된다는 데 있읍니다.
따라서 건강한 사람보다 한 모임 일찍 제거됩니다.

만일 총 전염병 환자가 x 명이면 환자는 x-1명의 환자를 보게되고
건강한 사람은 x명의 환자를 봅니다.
zilitwo님의 증명에서 보듯이 보이는 환자수 + 1 에 해당하는 모임 날짜에 환자들이 인식되어 제거되며
따라서, 전염병환자를은 건강한 사람보다 한 모임 일찍 제거되며
건강한 사람들만 남게 됩니다.

99명이 다 맞췄다면

글쓴이: nalrim / 작성시간: 일, 2007/04/22 - 5:54오후

99명이 다 맞췄다면 뒷통수에 거울을 단게 아닐지.. 푸헐.. ㅈㅅ ㅡㅡ;;

근데 말이죠

글쓴이: ydhoney / 작성시간: 일, 2007/04/22 - 6:14오후

흰색과 검은색이라면, 챙이 넓은 모자를 착용시켜줄 경우 힐끔힐끔 보면 보여요..-_-;

그리고 좀 심각하게 생각해보자면, 말만 못하지 만지지도 못하게 하는건 아니니까 뒤엣사람이 앞사람이 흰색이면 한번 툭 건드리고, 검은색이면 두번 툭툭 건드리고..

그러면 맨 뒷 큰 사람은 본인이 검은색인지 흰색인지 잘 찍기에 따라서 통과를 하겠고, 나머지는 뒷사람이 찍어주므로 패스..
　
====================여기부터 식인어흥====================
어흥 몰라 어흥? 호랑이 어흥!! 떡 하나 주면 어흥!! 떡 두개 주면 어흥어흥!!

흰색과 검정색은

글쓴이: moonhyunjin / 작성시간: 일, 2007/04/22 - 11:33오후

흰색과 검정색은 0,1이라는 바이너리로 인식하고 코드를 만들지 않았을까요?

그나저나 저런 문제로 사람이 평가 가능하다는 것이 이해가 안 가요.

<- 이거면 안되는 게 없어~
정품 소프트웨어 사용 캠패인

<- 이거면 안 되는 게 없어~
정품 소프트웨어 사용 캠패인

저도 비슷하게 생각하고 있습니다만

글쓴이: ydhoney / 작성시간: 일, 2007/04/22 - 11:39오후

일단 면접과정에서 저런 불필요한 것을 강요하는 회사는 가고 싶지도 않습니다.　
　
====================여기부터 식인어흥====================
어흥 몰라 어흥? 호랑이 어흥!! 떡 하나 주면 어흥!! 떡 두개 주면 어흥어흥!!

굉장히

글쓴이: 익명사용자 / 작성시간: 월, 2007/04/23 - 12:17오전

굉장히 공격적이시군요. --;

제가 보기엔 저런 문제야말로 프로그래머의 논리적 사고력을 측정하기에 딱인 것 같은데요. 면접 과정에서 "우리 회사는 검색엔진을 만드는 회사니 웹 검색 엔진을 만들어보세요. 시간은 30분 드리겠습니다." 이럴 수는 없지 않겠습니까.

(이렇게 말하면 제가 공격적인 게 되겠지만) 저런 문제를 보고 "이런 불필요한 걸!" 하고 성내는 사람이라면 IBM, google에서 (개발자로는) 별로 뽑고 싶어하지 않을 것 같습니다.

- jick

어떻게 저런것이 불필요 하며 저걸로 능력을 평가하는것이 이해가 되지 않습니까?

글쓴이: c0d3h4ck / 작성시간: 월, 2007/04/23 - 12:57오전

어떻게 저런것이 불필요 하며 저걸로 능력을 평가하는것이 이해가 되지 않습니까?
두분이 공격적으로 말씀하시기에 저도 과감하게 말하겠습니다.

우선 엔지니어는 모르겠습니다..
그리고 설계해준대로 코드로 옮기기만 하는 일반 코더들은 모르겠습니다만
개발자 특히 고급개발자들에겐 랭귀지의 특성, 플랫폼의 특성과 같이
환경 따라 다르고 금방 익힐 수 있는 기술적인 내용 보다는
저런 사고 능력이 훨씬 더 중요합니다..

IT 쪽 직업을 갖고 계시는 분들이 그런 말씀 하시면 곤란 합니다.

아 이것이 프로그래머 관련 채용 면접이라면 이해를 하겠습니다.

글쓴이: ydhoney / 작성시간: 월, 2007/04/23 - 1:23오전

그런데 대체 사무직 사원 뽑는데 "당신이 귤이 몇개가 있는데, 어쩌고 저쩌고 해서 이 귤을 공평하게 어떻게 하는 방법을 생각해볼 수 있겠나?" 라는 알고리즘 문제에 가까운 문제를 풀라고 하는건 정말 이해를 하지 못하겠습니다. 그 관리자도 이렇게 하면 유능한 직원들을 뽑을 수 있다고 어딘가에서 주워들었겠지요. 대체 그것이 어떤 효과가 있는지는 생각을 안해보는건지는 모르겠습니다만..

당연히 저런 문제가 프로그래머 채용 면접 전용이라면 상당히 당연한 질문이지요. 진짜로 당연한 문제 말이지요.

그런데 국내 기업들 중 뭐 좀 잘 나간다고 하는 기업들의 경우 저런 것을 뭐를 뽑던 물어보더군요. 예전 건설회사에 지원 나갔을 때 해당 회사에서 인력 관리직 신입직원을 뽑는데 저런 부류의 질문을 하는것을 본 적이 있습니다. 흔히 건설업계에서는 가장 잘 나간다는 업체중 하나였습니다만, 그 면접보는 상황 자체는 정말 웃기지도 않더군요. 이런 회사까지 좋게 봐줘야 정상적이겠습니까? 그건 정말 말도 안되지요. 업무 능력이 어떤지, 업무 성향은 어떤지등은 고려하지 않고 저런 문제들만을 물어보는데 정말 대체 이 회사 뭐지? 라는 생각밖에는 들지 않았습니다.
　
====================여기부터 식인어흥====================
어흥 몰라 어흥? 호랑이 어흥!! 떡 하나 주면 어흥!! 떡 두개 주면 어흥어흥!!

흠..위 글 내용에 이런 말이 있습니다..

글쓴이: c0d3h4ck / 작성시간: 월, 2007/04/23 - 1:35오전

'미국에서 프로그래머로 활동 중인 사촌 동생이 심심할 때 풀어보라고 내준 문제입니다. IBM인지 Google이었는지 잘 기억이 나지 않습니다만(아마 IBM이었을 겁니다), 면접 때 자신이 직접 받았던 문제라고 했습니다'

이 스레드는 '글쓴이의 프로그래머 사촌동생이 면접때 받았던 질문' 에 대한 스레드 라는것을 우선 확인하겠습니다.

그리고 야동꿀님 말처럼 저런 능력이 필수가 아닌 사무직 직책을 면접 보는데 저런 질문을 하는것은 그 면접관이 오버 했음을 인정합니다.

하지만 위의 답글에서는 불쑥 불필요하다는 말씀만 하셨길래 반박글을 달았던것입니다.

오홍 그런것 같아요

글쓴이: ydhoney / 작성시간: 월, 2007/04/23 - 1:39오전

제가 좀 오버한 느낌;;

=3=33　
　
====================여기부터 식인어흥====================
어흥 몰라 어흥? 호랑이 어흥!! 떡 하나 주면 어흥!! 떡 두개 주면 어흥어흥!!

저도 좀 오바한 것 같습니다;;

글쓴이: c0d3h4ck / 작성시간: 월, 2007/04/23 - 1:46오전

저도 좀 오바한 것 같습니다;;
불쾌하셨다면 죄송합니다 (_ _

괜찮아요

글쓴이: ydhoney / 작성시간: 월, 2007/04/23 - 2:43오전

요즘 트롤들 때문에 예민해져서 그럴 뿐인걸요. -_-a　
　
====================여기부터 식인어흥====================
어흥 몰라 어흥? 호랑이 어흥!! 떡 하나 주면 어흥!! 떡 두개 주면 어흥어흥!!

아이쿠야, 면접

글쓴이: 홍원범 / 작성시간: 월, 2007/04/23 - 1:51오후

아이쿠야, 면접 문제로서의 타당성에 관한 댓글들이 달렸군요^^
말씀드린대로 제 사촌동생은 프로그래머입니다. IBM에서 오픈소스쪽에 근무하다가 지금은 지금은 막 시작하는 신생 벤쳐 회사에 프로그래머로 일하고 있습니다. 지난 여름에 제가 사촌동생을 만나서 이 문제와 해답을 들을 때, 패리티비트에 대한 이야기도 덧붙여 하더군요. 검은 모자와 흰 모자를 0과 1의 2진수로 생각해낼 수 있는지의 여부가 문제 해결의 중요한 실마리가 될 수 있다고 말이죠. 사실 저는 컴퓨터를 좋아하기는 합니다만 프로그래밍 등의 전문 기술에 대한 지식이 전무하고, 생각하는 기반도 너무 다른 것 같아서 패리티비트 같은 것을 전혀 떠올릴 수 없었습니다. 그런데, 문제를 풀어낸 제 동생은(컴퓨터공학을 전공하고 있습니다) 그걸 금방 생각해내더군요. 그때 들었던 생각이, 아 뭔가 사고 방식이 다르긴 다르구나 싶었습니다. 그리고 프로그래머를 선발하기에는 문제가 참 괜찮다는 생각도 했구요(물론 저는 어떤 능력이 요구되는지는 잘 모릅니다만 그런 느낌이 들었습니다).
덧붙여서, 미국의 회사들은 면접을 굉장히 여러차례 실시한다고 합니다. 구글같은 곳은 15번 이상 면접을 실시하는데 개중에 저런 문제들이 나오는 것 같습니다. IBM도 마찬가지구요. 저것만 가지고 능력을 판단할 수는 없겠지만, 저것도 포함이 된다면 다른 문제들과 더불어 면접자의 능력을 '더 잘' 파악할 수 있지 않을까 싶습니다.

Open-Source Anthropology

다들 비슷한 답을

글쓴이: alwaysrainy / 작성시간: 월, 2007/04/23 - 2:50오후

다들 비슷한 답을 생각하셨네요. 큰 소리로 '흰', '검'
외치는 것은 웬지 부정행위 같아서.. ^^;
자신의 모자를 벗어서 앞으로 건네줄 때 앞에 분의 모자색에
따라 오른쪽, 왼쪽으로 건네줍니다.

#define 흰모자 0
#define 검은모자 1
 
if ( 앞사람의 모자색 == 0 )
 toLeftHand(); // 앞사람의 왼손에 자신의 모자를 건넨다.
else 
 toRightHand();

맨 뒤에 분은 50%의 확률로 맞추고, 그 앞분들은 100%의
확률로 맞추겠죠.

---------------------------------------
세계는 넓고, 할일은 많다.

와!! 대단합니다..

글쓴이: 익명사용자 / 작성시간: 화, 2007/04/24 - 4:25오전

저는 생각도 못하겠는 문제였습니다.

그렇지만 글 중간에 단순히 흰색,검은색을 말하는 게 아니라
말의 장단이나,어떤 신호를 주는 것이라면 이건 출제자가 원하는 방법이 아닐 겁니다..

만약 뒷사람이 그 두가지 말인 [흰색,검은색]말고 다른 행동을 취할 수 있다면 굳이 홀수니 짝수니 이런 계산을 할 필요도 없습니다.

즉, 그런 방식까지 통용된다면 다음과 같이 더 간단한 방식을 써도 됩니다.

-------------------------------------------------
1.맨 뒷사람은 자기 모자색깔을 모른다..따라서 흰색이든 검은색이든
앞사람의 모자가 검은색인면 길게,흰색이면 짧게 발음한다.

2.뒷사람의 힌트로 자기모자 색을 알게된 다음 사람은 자기모자색깔을
앞사람의 모자색에 따라 길게 또는 짧게 발음한다.
-------------------------------------------------

결국 [흰색,희인색,검은색,거므은색]4가지 방식의 대답으로 최소한 99명은 무조건 자기 모자 색깔을 맞힐 수 있습니다.

하지만,, 출제가가 원한 건 두가지방식의 대답만을 통한 해결이었지,
저런 4가지 방식의 대답은 아니었을 겁니다.

미리 알려주지 않았다고 해서 4가지 다른패턴의 대답을 한다면,
문제의 의도를 모르는 것이므로 제대로 답을 풀었다고 말할 수 없습니다.

따라서 머리속으로 홀짝을 생각하고, 대답만 [흰색,검은색] 두가지로 대답한 것이 출제자의 의도에 딱 맞아떨어지는 문제해결법입니다.

다른 방식을 쓴다고 해도 두가지패턴의 대답만으로 다음사람에게 힘트를 넘겨줄 수만 있다면 또다른 답이 될 수 있을 겁니다.

모자 도합이 100개

글쓴이: lovian / 작성시간: 화, 2007/04/24 - 10:49오전

모자 도합이 100개 라는데, 그 것이 50개 50개 딱 반반인지는 어떻게 알고 계시는거죠?
저는 여기서부터 진척이 안됩니다.

-----------------
한글을 사랑합니다.

개수는 상관없이

글쓴이: pung96 / 작성시간: 화, 2007/04/24 - 11:26오전

개수는 상관없이 개수가 홀수냐 짝수냐가 중요하겟죠.

전체 수는 상관이

글쓴이: Risty / 작성시간: 화, 2007/04/24 - 11:33오전

전체 수는 상관이 없습니다.

홀수에서 1을 빼면 짝수, 짝수에서 1을 빼면 홀수라는 성질만 이용합니다.

모자의 색깔이 각각

글쓴이: 익명사용자 / 작성시간: 화, 2007/04/24 - 11:46오전

모자의 색깔이 각각 50개 일때.

1. 내 뒤의 사람은 나의 모자 색을 불러준다.
2. 앞 사람과 자신의 색이 틀렸을때, 음의 장~음으로
모자색이 반대임을 알린다.

무작위의 색깔일때
???????????????????
???????????????????

하해와 같은 도움 부탁드립니다.

모자의 색깔이 50가지가 아닙니다..

글쓴이: 익명사용자 / 작성시간: 화, 2007/04/24 - 1:00오후

모자의 색깔은 [흰색, 검은색] 단 두가지입니다..
물론 사람수가 100명이므로 모자수도 100개일 거고, 때론
흰색모자 50개, 검은색 모자 50개일 수는 있지만 그렇지 않을 경우가 더 많습니다.

어떤 경우이든 맨 뒷사람이 봤을 때 모자는 99개가 보이므로

흰색모자가 짝수개라면, 검은색모자는 홀수개이고....
반대로 흰색모자가 홀수개라면, 검은색 모자는 짝수개가 됩니다.

따라서 맨마지막 사람이 자기를 제외한 홀수개의 숫자를 가진 모자색을 말한다면(가령 흰색)

그 앞사람은 자기 모자까지 합쳐서 [흰색모자는 홀수]라는 사실을 알게됩니다..

그러니 흰색모자 숫자를 셈해서 자기앞사람의 모자까지 짝수개라면 [흰색]이라고 대답하고, 셈한 게 홀수라면 [검은색]이라고 대답합니다.

마찬가지로 그 앞의 사람은 뒷사람의 대답을 통해서 자기모자까지 합쳐서 [흰색모자]가 짝수개인지 홀수개인지 알 수 있으므로 자기모자색깔을 알 수 있습니다.

음..

글쓴이: 익명사용자 / 작성시간: 화, 2007/04/24 - 7:10오후

패리티 비트까지 생각하시다니 대단하시네요 ㅎㅎ

글쓴이: 아톰8 / 작성시간: 목, 2007/05/03 - 7:51오후

제가 생각한거는 뒷 사람이 바로 앞 사람의 모자 색깔을 말해주는 겁니다.

그럼 99명은 확실하게 알 수 있고 100번째 사람은 어짜피 흰색 아니면 검은색

50%의 확률로 맞을 수 있으니까요. :)

문제에서도 100명 다 맞히기도 했다라고 한 거보면

여러번 시도해도 확실하게 100명을 다 맞추지는 못한 것으로 보입니다.

동의

글쓴이: drinkme / 작성시간: 월, 2007/05/28 - 4:15오후

님의 의견에 동의합니다.
저도 문제를 보는 순간 님처럼 생각했습니다.

이건 틀린

글쓴이: charsyam / 작성시간: 월, 2007/05/28 - 5:24오후

이건 틀린 생각같습니다.

왜냐하면, 앞사람의 색깔과 자신의 모자 색이 틀릴 경우는 언제든지 발생합니다.
딱 한번만 말해줄 수 있기 때문에, 검정 - 빨강 - 검정 일때, 앞사람 껄 말하면 자신이
틀리게 됩니다.

제 생각도, 전체 모자에서 빨강이나 검정 모자중에 하나를 정해서 그게 홀수이면 빨강

짝수이면 검정 이런식으로 말해주는게 가장 옳을듯 합니다.

나머지 사람들이 앞사람의 모자 수를 세어서 그걸로 계산해서

말하는게 옳은 답일꺼 같습니다.

=========================
CharSyam ^^ --- 고운 하루
=========================

첫번째 테스트에서는

글쓴이: sunshout / 작성시간: 월, 2007/05/28 - 5:40오후

첫번째 테스트에서는 잴 키큰 사람이 맞출 확률이 50%이기 때문에 첫번째 사람이 틀려서 99명이 정답을 말했고,

두번째 테스트에서는 이제 전체 모자 중 흰모자가 짝수개인지 홀수개인지를 알기 때문에 첫번째 사람도 정답을 맞추는군요.

그래서 100명 모두 정답을 말할 수 있었군요...

대단합니다.!!

Nothing will be happen.

이거 잼있네요.

글쓴이: cats96 / 작성시간: 금, 2008/08/08 - 5:47오후

저는 틀렸습니다.

제 조건에서는 행동도 포함이 된다 였네요.

제 짧은 생각으로는 젤 키큰 사람은 확률 50% 로 가정하고,

하나의 색을 말하면서 검정색이면 앞의 사람을 툭 치고, 하약색이면 그냥 색을 말만 합니다.

위의 조건에 행동에 제약이 있다는 말이 없어서 ^^;;

zilitwo 님 대단 하십니다.

오늘 면접 봣는데 답알수 있을까요?

글쓴이: killerpd / 작성시간: 목, 2010/01/07 - 8:02오후

100층 짜리 건물이 1층 부터 옥상 까지 있다고 하자
근데 1층 부터 옥상 까지 n개의 전선이 연결되어 있다
근데 어느부분이 같이 연결 되어 잇는지 모른다
설사가상으로 엘리베이터 까지 고장났다
그럼 어떻게 하여 고치겠는가?
1) 옥상, 1층부터 a전선, b전선 씩 하나씩 확인하면서 고친다
2) 옥상, 1층부터 a전선, b전선 씩 건전지 와 전구를 직렬로 연결 하여 고친다
3) 1층과 옥상을 바꾼다.

1번 비용 1, 2번 비용 2, 3번 비용 10
어느 방법이 더 효율적이면서 비용이 적게 고치는겠는가?
방법과 그 이유에 대하여 설술 하여라.

문제가 정확합니까?

글쓴이: hiseob / 작성시간: 금, 2010/01/08 - 12:05오후

1.
100층짜리 건물엔 당연히 1층과 옥상(또는 지붕)이 있습니다.
1층부터 옥상까지 있다는 표현이 이해가 안됩니다.

2.
1번 > 1층과 옥상사이의 N개의 전선을 하나씩 확인하면서 고친다
2번 > 1층과 옥상사이의 N개의 전선 각각에 전압원과 전구를 직렬로 연결하여 확인하여 고친다.
3번 > 1층의 끝단을 옥상으로 끌어올리거나 옥상의 끝단을 1층으로 끌어내린다
문제를 이렇게 고쳐도 1번을 수행하는 방법이 2번이기 때문에 문제 자체에 오류가 있습니다. (테스터기가 있지 않느냐? 하신다면 애초에 전구를 쓴다는거 자체가 -.-)

3.
비용에서 '개당' 수행비용인지 '총' 수행비용인지 알수가 없군요 :D

마지막 사람은 자신 앞의 두 사람이 쓴 모자 색을...

글쓴이: freestyle / 작성시간: 목, 2010/01/07 - 9:31오후

같으면 흰색, 다르면 검정색이라 말해줍니다.

그 앞 사람은 자신 앞 사람의 색을 보고 자기가 쓴 모자의 색을 알 수 있고,
자신의 앞의 두 사람 모자 색이 같으면 흰색, 다르면 검정색이라 말해줍니다.

....

2번째 선 사람이 자신의 모자 색을 알고 난 뒤,
앞 사람의 모자 색을 말해줍니다.

....

마지막 사람은 찍는 것이죠.
그래도 두 번 안에는 성공하겠지요.

그리고 위의 글은... 질문을 이해 못하겠습니다.
----------------------
Go to the U-City

----------------------------------------------------------------------------------------
Don't Feed the Trolls!
----------------------------------------------------------------------------------------

블로그에 퍼 가겠습니다.

글쓴이: isty2e / 작성시간: 목, 2010/01/07 - 11:50오후

혹시 동의가 필요한가요?

앞 사람의 모자 색을 말하는 것도.

글쓴이: madhatter / 작성시간: 금, 2010/01/08 - 1:30오후

가능합니다.

1. 100번째 사람이 앞 사람의 모자 색을 말합니다.
2. 99번째 사람은 자기 모자 색과 앞사람의 모자 색을 알 수 있습니다. 만약 두 색이 같으면 앞사람의 모자 색을 말하고 틀리면 패스합니다.
3. 98번째는 99번째가 말하던 패스하던 자기 모자색을 압니다. 말하면 그 색이고 패스하면 다른 색입니다.
4. 2,3을 반복해서 1번까지 갑니다.
5. 1번까지 가면 패스한 사람들도 모두 자신의 모자색을 알 수 있습니다.

패스가 허용 되느냐 아니냐에 대한 조건이 없으므로 가능한 얘기지만, 이 경우는 자기 뒷사람 말만 듣고 있으면 됩니다. 패리티 체크가 가장 확실하지만 목소리를 다 듣거나 홀짝 계산을 해야하는 부담이 없습니다. 일종의 async 프로토콜이고 패리티는 sync 프로토콜이죠.