컴퓨터와 아무 상관 없지만,
매우 상관 많은 퀴즈들을 소개합니다.
퀴즈 1.
- 100명을 넘지 않는 해적 n명이 있다. 서열이 있다: 해적 1 > 해적 2 > ... 해적 n.
- 금화는 총 100개가 있다.
- 가장 서열이 높은 해적만이 금화를 어떻게 분배할지 제안할 수 있다.
- 제안자를 포함, 남아 있는 모든 해적들이 투표를 하며 과반수 이상의 동의가 있을 경우, 그 제안에 따라 금화를 분배한다. 반수 이상이 동의하지 않을 경우 제안자를 죽인다.
- 가장 높은 서열의 해적이 죽는다면, 이제 그 다음 서열의 해적이 제안권을 가지고 위 규칙을 반복한다.
- 모든 해적들은 돈에 대해서 철저히 합리적이다.
문제: 가장 높은 서열의 해적이 차지할 수 있는 최대 금화의 수는?
어려우신 분은... 아래 문제.
퀴즈 2.
http://www.flickr.com/photos/kreppart/68727303/
문제: 이 게임의 승자는 누구일까?
이것도 어려우면...? 마지막 문제.
퀴즈 3: 하노이의 탑
아래와 같이 서로 크기가 다른 n개의 원판이 쌓여져 있다. 이제 첫 번째 기둥에 꽂힌 원판들을 순서 그대로, 모두 3번째 기둥으로 옮기려고 한다. 단, 다음 두 가지 조건을 준수해야 한다.
http://en.wikipedia.org/wiki/Tower_of_Hanoi
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
문제: 어떻게 하면 이것들을 옮길 수 있을까?
동일한 해법
3번 문제를 먼저 풀어보자. 이 문제에서 극단적으로 간단한 경우는?
간단하다. n = 1, 즉 원판이 하나만 있는 경우다. 이 경우 1개만 옮면 끝난다. 아주 쉽다.
그 다음은? 재미있어지는 건 여기서부터다. 2개를 옮기는 문제는 아래와 같이 풀 수 있다:
1. 1에 위치한 1개의 원판을 2로 옮긴다. 하나만 옮기는 경우는 위에서 다루었다.
2. 1에 마지막으로 남은 하나의 원판을 3으로 옮긴다. 역시 위에서 다루었다.
3. 2에 옮겨진 1개의 원판을 3으로 옮긴다. 역시 위에서 다루었다.
3개면?
1. 1에 위치한 2개의 원판을 2로 옮긴다. 2개를 옮기는 경우는 위에서 다루었다.
2. 1에 마지막으로 남은 하나의 원판을 3으로 옮긴다. 역시 위에서 다루었다.
3. 2에 옮겨진 2개의 원판을 3으로 옮긴다. 역시 위에서 다루었다.
그러니까, 극단적으로 간단한 경우의 문제를 일단 풀면, 그 다음으로 간단한 경우, 그 다음 경우... 에 해당하는 문제가 연쇄적으로 풀리는 것이다. 이 문제의 가장 큰 특징은 바로 이거다.
2번 문제도 마찬가지다. 원탁의 크기 중 가장 극단적으로 간단한 경우는 바둑돌이 1개만 올라갈 수 있는 초미니 탁자다. 이 경우 A가 무조건 이긴다.
그러면 그게 아닌 경우는? 간단하다. A가 일단 가운데 바둑돌을 놓고, 그 다음부터는 B가 놓는 자리에 정확히 반대되는 위치에만 놓으면 된다. 탁자와 바둑돌 모두가 원형이기 때문에 가능하다. 따라서 이 게임의 승자는 무조건 A다.
http://www.flickr.com/photos/motoyen/733936081/
여기서 중요한 것은, 이 경우 막내는 아무 것도 차지할 수 없다는 것이다. 즉, 막내 입장에서는 두 명만 남는 상황이 절대로 오면 안 된다. 한 푼도 못 챙기니까.
그렇다면 해적이 3명 남았을 때, 가장 서열이 높은 해적이 내놓을 수 있는 최선의 제안은? 99:0:1로 분배하는 것이다. 막내는 현재 제안자가 죽으면 한 푼도 못 챙기니까, 금화 1개만으로도 찬성할 수밖에 없다. 따라서 제안자는 스스로의 표와 막내의 표, 2개를 확보하면서 안전하게 금화를 차지하게 된다.
여기서 중요한 것은? 두 번째로 낮은 서열이 아무 것도 차지할 수 없다는 것이다. 즉, 두 번째로 낮은 서열 입장에서는 해적이 4명 남았을 때 제안자가 죽는 사태를 절대 피해야 한다.
여기까지 오면 해적이 4명인 경우는 아주 쉽다: 99:0:1:0. 두 번째로 낮은 서열이 찬성하므로, 제안자 포함 2표 확보. 마찬가지 방법으로 5명의 경우 98:0:1:0:1, 6명인 경우는 98:0:1:0:1:0 이 된다. 이런 식으로 풀어 나가면, n이 구체적으로 얼마인지 몰라도 충분히 답을 구할 수 있다.
꼬리에 꼬리를 무는 해결
n factorial 계산 문제는 위 퍼즐들과 완전히 동일한 구조를 가진 문제다. (http://en.wikipedia.org/wiki/Recursion_(computer_science))
그러면 google이나 facebook같은 소프트웨어 회사에서 이런 문제를 물어 보는 이유1는? 전공자들은 이미 눈치 챘겠지만, 위 밑줄 쳐 놓은 부분은 컴퓨터과학 공부를 제대로 했다면 모를 수가 없다. 기초 과목부터 컴파일러 이론에 이르기까지, 컴퓨터 과학의 거의 모든 분야에서 반복되며 사용되는 원리이기 때문이다. 구체적으로 이야기하자면, 퀴즈 3은 사실 내 1학년 1학기 첫 전공 중간고사 3번 문제였다.
* 위 경우에 못지않게 중요한 문제로 '정보를 어떻게 컴퓨터가 알아볼 수 있는 형태로 표현해야 하는가' 에 대한 문제도 있다. 이건 꽤나 중요한 문제라서, 인간이 역사적으로 어떤 식으로 이 문제를 해결해 왔는지에 대한 책이 있을 정도다. 구글 입사 문제로 유명한 전구-스위치 문제가 바로 이 케이스.
- 사실 1번 문제의 변형판은 facebook 입사 문제로 유명하다. [본문]
