꼬리에 꼬리를 무는 퀴즈

컴퓨터와 아무 상관 없지만,

매우 상관 많은 퀴즈들을 소개합니다.

퀴즈 1.

  • 100명을 넘지 않는 해적 n명이 있다. 서열이 있다: 해적 1 > 해적 2 > … 해적 n.

  • 금화는 총 100개가 있다.

  • 가장 서열이 높은 해적만이 금화를 어떻게 분배할지 제안할 수 있다.

  • 제안자를 포함, 남아 있는 모든 해적들이 투표를 하며 과반수 이상의 동의가 있을 경우, 그 제안에 따라 금화를 분배한다. 반수 이상이 동의하지 않을 경우 제안자를 죽인다.

  • 가장 높은 서열의 해적이 죽는다면, 이제 그 다음 서열의 해적이 제안권을 가지고 위 규칙을 반복한다.

  • 모든 해적들은 돈에 대해서 철저히 합리적이다.

문제: 가장 높은 서열의 해적이 차지할 수 있는 최대 금화의 수는?

어려우신 분은… 아래 문제.

퀴즈 2.

stones

완전한 원형의 평평한 탁자가 하나 있다. 이 위에 A와 B가 순서대로 바둑돌을 놓아 나간다. 바둑돌을 놓을 자리가 없는 사람이 진다.

문제: 이 게임의 승자는 누구일까?

이것도 어려우면…? 마지막 문제.

퀴즈 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/

이렇게 놓고 보면 1번 문제도 쉽게 풀 수 있다. 해적들이 투표를 하는 가장 극단적으로 간단한 경우는, 서열이 높은 해적들이 다 죽고 두 명만 달랑 남은 경우다. 그런데 이 경우 자기 자신이 가진 1표만으로도 충분히 제안을 통과시킬 수 있으니까, 서열이 높은 쪽 해적이 금화를 독차지할 수 있다. 100:0으로 분배안을 내 놓고 그냥 통과시키면 되기 때문이다.

여기서 중요한 것은, 이 경우 막내는 아무 것도 차지할 수 없다는 것이다. 즉, 막내 입장에서는 두 명만 남는 상황이 절대로 오면 안 된다. 한 푼도 못 챙기니까.

그렇다면 해적이 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))

위 문제들은 모두 제각각이다. 하지만 풀이 방법은 완전히 동일하다. 우선 극단적으로 간단한 경우의 수(Base Case)에 대해 문제를 푼다. 그러면 그 다음 경우의 수(Inductive Case)가 자동으로 풀리게 된다.

그러면 google이나 facebook같은 소프트웨어 회사에서 이런 문제를 물어 보는 이유1는? 전공자들은 이미 눈치 챘겠지만, 위 밑줄 쳐 놓은 부분은 컴퓨터과학 공부를 제대로 했다면 모를 수가 없다. 기초 과목부터 컴파일러 이론에 이르기까지, 컴퓨터 과학의 거의 모든 분야에서 반복되며 사용되는 원리이기 때문이다. 구체적으로 이야기하자면, 퀴즈 3은 사실 내 1학년 1학기 첫 전공 중간고사 3번 문제였다.

  • 위 경우에 못지않게 중요한 문제로 ‘정보를 어떻게 컴퓨터가 알아볼 수 있는 형태로 표현해야 하는가’ 에 대한 문제도 있다. 이건 꽤나 중요한 문제라서, 인간이 역사적으로 어떤 식으로 이 문제를 해결해 왔는지에 대한 책이 있을 정도다. 구글 입사 문제로 유명한 전구-스위치 문제가 바로 이 케이스.

  1. 사실 1번 문제의 변형판은 facebook 입사 문제로 유명하다. 

11 thoughts on “꼬리에 꼬리를 무는 퀴즈

  1. 저도 알고리즘 수업에서 1번 문제가 중간고사에 나왔었죠… 여러가지로 재밌는 문제입니다 ㅎㅎ

    • 헐, 저 문제가 아예 수업에서 다뤄지는 경우도 있군요!! 저는 그냥 넷상에서 본 것이었거든요. ㅇ_ㅇ;

  2. ‘과반수’는 ‘반수를 넘는’, 즉 x > 0.5 를 의미하므로,
    두 명이 남는 경우 두 명 모두 합의해야만 ‘과반수’ 혹은 ‘과반수 이상’이 됩니다. : )

    그러면 시나리오의 흐름이 살짝 달라지는데,
    합리적인 전개를 위해서는 한 가지 가설을 더 끼워넣어야 할 것 같습니다.
    ‘자신에게 돌아올 이득이 동일할 경우, 다른 사람이 더 죽는 걸 원하지는 않는다’ 라는 가정이죠.

    서열이 가장 낮은 사람을 1, 가장 높은 사람을 n 이라고 가정합니다.

    2명일 때: 100:0
    0:100으로 분배하지 않으면 반드시 2가 죽게 되므로, 2의 기대는 0이 됩니다.

    3명일 때: 0:1:99
    3이 99를 가지고, 2에게 1을 제안하더라도, 2 입장에서는 3이 죽으면 안되므로 수용하게 됩니다. 1은 3이 죽어야 유리하므로 100을 주지 않는 이상 거절하게 됩니다.

    4명일 때: 1:1:0:98
    1의 입장에서는 3명이 되는 상황을 막아야 하고, 2의 입장에서는 상관이 없지만, 3의 입장에서는 4가 죽어야 3명인 상황이 오므로, 3에게 0을 주고 2에게 1을 주면 됩니다.

    5명일 때: 1:1:0:0:98
    1의 입장에서는 3명이 되는 상황이 오지만 않는다면 어차피 분배는 똑같으므로, 1에게는 1만 주면 됩니다. 2도 마찬가지로, 2에게 0을 주지만 않는다면 4명일 때와 기대값이 같으므로 굳이 반대할 이유는 없습니다. 자신을 포함해 이렇게 3명으로 찬성 과반수를 채웠으므로, 나머지 3,4에게는 0으로 분배해도 됩니다.

    6명일 때: 1:1:1?:0?:0:97
    1과 2에 대해서는 찬성을 얻으려면 0을 줘서는 안됩니다. 안그러면 다음 서열이 결정하는 상황을 원하려 할테니까요. 그러므로 안정적으로 1과 2를 각각 1을 주고, 3, 4 중 한 사람에게 1을 줍니다. 5는 다음 1을 줘봤자 다음 단계의 기대값이 더 크므로 반대를 할 것이므로, 5는 배제합니다. 3에게만 1을 주면 4,5가 반대해도 통과하므로 6은 최대 97을 가질 수 있습니다.

    7명일 때: 1:1:1?:0?:0?:0:97
    6명일 때와 동일합니다. 바로 자기 아래 서열은 자기 돈을 모두 주지 않는 이상 반대하므로, 0을 주는게 최선이고, 1과 2에게는 1을 줘서 찬성하게 만듭니다. 나머지 사람들에게는 과반이 넘을 숫자만큼만 1씩 주면 됩니다.

    그러므로 n명의 해적이 과반수 표결 시스템에서 돈을 나눈다고 할 때, 가장 높은 서열의 해적이 가질 수 있는 최대 금액 m은
    m = 100 – ceil(n / 2) (단, n은 3이상)
    이 될 것 같습니다.

    생각하다가 중간에 다른 이해관계를 빼먹었을 수도 있을 듯한데요,
    과반수에 대해 생각하다가 정리해본 부분이니, 혹시 틀린 부분이 있다면 지적 부탁 드립니다.

  3. 2번 답은 A가 이기는 게 맞지만, 설명은 좀 이상한데요. 각각 바둑돌 한 개씩을 놓고 바둑판의 눈 숫자가 홀수(19*19=361)이므로 A가 이기는 게 맞죠. 하지만 바둑판 크기가 변할 수 있다면, 그래서 눈 숫자가 짝수가 될 수 있다면 그 경우에는 B가 이깁니다. 눈 숫자가 짝수인 경우에는 ‘가운데’ 지점이 존재하지 않으므로 말씀하신 알고리즘은 적용할 수 없고요.

    • 문제 다시 읽어보세요.
      “원형 탁자 위에 놓는다.” 고 해 놓았습니다.

    • 그건 관계없는 이야기입니다. 완전한 정사각형이라고 해서 눈 숫자가 홀수라는 법이 없듯이, 완전한 원이라고 해서 ‘가운데’ 점이 있으라는 법은 없습니다. 원 한가운데가 격자점이 될지 사각형 한가운데가 될지 어떻게 알 수 있습니까?

    • 그 말씀이 문제의 풀이와 관계가 없다는 것은 저도 알고 고어핀드님도 압니다. 말장난으로라도 어떻게든 넘어가고 싶으시다면 저도 더이상 거론하지 않겠습니다.

    • 원에 가운데가 없다는 말은 처음 듣는군요. 남의 블로그에 와서 시비를 걸기 전에 초등학교 산수 도형이나 좀 공부하시길 바랍니다.

  4. 상당히 흥미로운 문제들이네요 … 1번 문제는 … 어떻게든 공평하게 나눠주려고 생각했었는데, 알고보니 독차지였군요 ㅠㅠ…

    하노이의 탑은 자료구조 알고리즘 책에서는 안나오는곳이 없더군요 …

    • 예, 하노이의 탑 정도 되면 모르는 사람이 없죠. 사실 신입생들이 알아듣기 쉬우면서도 이 문제의 본질을 꿰뚫고 있는 문제인지라…

Comments are closed.