[프로그래밍] Fizzbuzz 문제에 대하여(2)

지난 포스팅의 마지막에 Fizzbuzz 를 풀어 내는 희한한 예제를 게시한 바 있습니다. 좀 오래 되긴 했지만, 궁금해 하는 후배가 있어 한 번 같이 분석해 보았고 독특하고 엉뚱한 생각에 재미를 조금 느끼기도 했습니다.

실제 인터뷰시의 사례인지는 알 수 없지만, 이 해법을 소개한 페이지(Fizzbuzz 에 지겨워진 개발자들)을 잠깐 보면, "일단 똑똑하다", "뽑고 싶다" 거나 "생각이 한쪽으로 쏠린 사람", "팀웍을 해칠 것 같다" 는 등의 다양한 반응를 예로 들고 있네요. 글 쓴이(Samuel Tardieu) 자신은 일을 하면서 이런 식의 재미를 추구하는 방식을 좋아한다고 적고 있기도 합니다. 여러분은 어떠신가요?

우선, 소개된 원본 소스를 그대로 두고 한 번 훑어 보기로 합니다. 참, 한 번 실행시켜 보셨나요? 다른 잘 짜여진 소스와 마찬가지로 정확하게 결과를 출력해주고 있습니다. 희한하네? ^^;;

#include <stdio.h>

static const char *t[] = {"%d\n", "Fizz\n", "Buzz\n", "FizzBuzz\n"};

int main()
{
  unsigned int i;
  for(i = 1; i <= 100; i++) printf(t[3&19142723>>2*i%30], i);
  return 0;
}

C 프로그램이고, t 라는 문자열들을 초기화해서 가지고 있는 문자열 포인터 배열이 보입니다. t[0] 는 "%d\n", t[1] 은 "Fizz\n" ...이 되겠지요.

그 외에는 for loop 에서 printf 함수를 쓴게 답니다. 그럼 어디에서 저런 괴물같은 결과가 나온 걸까요?

가만히 보면 printf 에서 사용하는 파라미터의 t[3 & 19142723 >> 2 * i % 30] 부분에 뭔가 비밀이 숨어 있다는 얘긴데요. [] 내부의 값은 t[] 배열의 index 로 0~3 사이의 정수값을 가지게 되겠네요.

(1) 어떤 트릭일지 들여다봅시다. 3 & 19142723 >> 2 * i % 30 ... 부분을 보면 우리 눈을 현혹시키는 것이 한 가지 숨어 있습니다. 다름 아닌 연산자 우선순위! 이게 첫번째 포인트.

저 계산식을 우선 연산자 우선순위에 맞게 괄호를 써서 어떤 값을 어떻게 가지게 되는지 확인해 보아야겠습니다.

3 & (19142723 >> ( (2 * i) % 30) ) 이렇게 됩니다. &는 bit AND 연산으로 가장 우선순위가 낮고, 그다음 낮은 것이 >> 즉 RShift(오른 쪽 비트와이즈 쉬프트 연산) 이지요.

자 그러면 (2*i) 가 가장 먼저 계산됩니다. i는 1~100 사이의 카운터니까, (카운터 * 2) 를 계산한 값을 30으로 나눈 나머지를 취하는군요. 즉 2%30, 4%30, 6%30, ..., 28%30, 30%30 처럼 {2, 4, 6, ..., 28, 30, 0, 2, 4, ....} 와 같이 나열해 보면 15를 주기로 0부터 리셋되어 2씩 값이 증가하는 수들이 나열됩니다.

(2) 그럼 위의 식은 19142723 이라는 묘한 숫자값을 처음에는 2회 Rshift, 그 다음 4회 Rshift, 이런 식으로 반복해서 2칸씩 Rshift 하고 3(2진수로 11)과 bit AND 연산을 하는 겁니다. 그렇다면...

(3) 모든 비밀은 19142723 이라는 숫자에 숨어 있는 거군요. 이 숫자를 2진수로 출력해 보면(아래 예제에 2진수 출력 함수가 있으니 확인해보세요) 00 00 01 00 10 01 00 00 01 10 00 01 00 00 11 이렇게 됩니다. 이해하기 쉽게 2자리씩 끊어서 보자구요.

위의 (2)에서처럼 생각하면, 카운터 i 가 1일 때 00 00 01 00 10 01 00 00 01 10 00 01 00 00 11 을 오른쪽으로 2칸 밀면 끝 자리에 00이 나오고 2진수 11과 AND 연산을 하면 00 즉 0이 나옵니다. 카운터 i가 2일 때는 오른쪽으로 4칸 밀면 끝자리에 00, 2진수 11과 AND 연산을 하면 00, 카운터 i 가 3일때는 6칸 밀고 끝자리에 01 과 2진수 11 AND 연산하면 01 이 나오지요.

즉 주어진 숫자를 2번씩 Rshift 하면서 2비트씩 뽑아 먹는 일을 계속 반복하는 겁니다.

자, 여기서 다른 Correct한 예제 솔루션들에서 출력되는 결과를 다시 한 번 보면,

1	i 값 = t[0]
2	i 값 = t[0]
Fizz	t[1]
4	i 값 = t[0]
buzz	t[2]
Fizz	t[1]
7	i 값 = t[0]
8	i 값 = t[0]
...
15	t[3]
16	i 값 = t[0]

이 패턴이 15개씩을 주기로 반복되고 있습니다(당연하겠지요 ^^;; 아마도 짖궂은 코더는 여기서 아이디어를 착안했겠지요).

이제, 위 표 오른쪽 칼럼의 t[]의 인덱스를 보니 {0, 0, 1, 0, 2, 1, 0, ...} 이렇게 되는데, 2자리의 2진수로 바꿔서 다시 나열해 보면 {00, 00, 01, 00, 10, 01, 00, ...} 이렇게 됩니다.

위의 (3)에서 보이는 2진수를, 오른쪽에서부터 11를 제외하고 숫자를 2개씩 묶어서 나열해 보면 정확히 맞아 떨어지지요.

이제 감이 조금씩 잡히시나요? 매직넘버로 보였던 19142723 이라는 숫자가, 사실은 미리 관찰된 패턴에 의해 나오는 t[]의 인덱스 값을 오른쪽(가장 낮은 값에는 11을 채우고) 에서부터 왼쪽으로 채워나가서 만들어지는 2진수를 10진수로 표현한 값이라는 얘기입니다. 한 마디로 줄이면, 솔루션이 아니라 '사기' 입니다.

이해를 돕기 위해 아래 C++ 프로그램을 작동시켜 보시기 바랍니다. 말로 설명하는 것보다 프로그램을 보고 실행해 보는 것이 더 직관적으로 이해가 잘 될 수 있을 것 같습니다.

#include <iostream>

using std::cout;
using std::endl;

void fizzbuzz7(int _n)
{
    static const char *t[] = {"%d\n", "Fizz\n", "Buzz\n", "FizzBuzz\n"};

    for(int i = 1 ; i <= _n; i++)
        printf(t[3 & (19142723 >> ((2 * i)%30))], i);
}

// 10진수를 2진수 값으로 출력
void binary_cout(int _n)
{
    if( _n <= 0)
        return;

    binary_cout(_n >> 1);

    cout << _n % 2;
}

int main()
{
    // Magic number 19142723는 2진수로 00 00 01 00 10 01 00 00 01 10 00 01 00 00 11 (2자리씩 끊어서 표기)
    int x, y;

    // fizzbuzz7 과 같은 로직에 해설을 추가하여 다시 써 봅니다
    for(int i = 1; i <= 100; i++) {
        cout << i << ": Magicnumber 를 " << (x = (2 * i) % 30) << "회 Rshift -> ";
        binary_cout(y = (19142723 >> x));
        cout << " 이 되고 이것을 0x11 과 bit and를 하면: " << (3 & y) << " 이 되며, 이것은 배열의 index." << endl;
    }

    return 0;
}

누가 작성했는지 모르지만 이 프로그램의 코더는 분명 일반인들의 허를 찌르는 센스를 가진 사람일 것 같습니다. 틀에 얽매이지 않는 자유로운 영혼, 저도 이런 분들을 좋아하고 또 본받으려고 노력합니다. 물론 프로그래머로서의 목표의식과 인성이 갖추어져 있다는 전제하에서.

발칙하다는 것은 기발하고 독창적이라는 말과 비슷합니다. 하지만 또 어떻게 보면 사회성이 떨어지고 규범을 지키지 않을 것 같은 부정적인 느낌을 주기도 합니다. 위의 솔루션은 사실 예상되는 답의 패턴에 문제해결 과정을 끼워 맞춘 것으로, 엄밀하게 말하자면 문제해결에 적합한 코딩은 아닙니다. 즉 나누는 수를 3과 5에다가 새로운 수인 7을 하나 더한다든지 하게 되면, 예상되는 결과로부터 패턴을 추출하여 프로그램 내의 매직넘버를 다시 계산하고 t[]의 index 를 계산하는 식도 다시 써야 하니까요.

또 이 솔루션은 문제를 출제한 사람을 사실은 조롱하고 있다고 생각할 수 있습니다. 하지만 그 기발한 방법으로 보아 좋은 직관력을 가졌다고 생각되며, 동적계획법이든 뭐든 적당한 훈련 과정을 거친 사람이고 문제해결을 위한 코딩의 감각이 어느 정도 갖추어져 있는 사람임은 분명해 보입니다.

이전 글: 

2015/12/07 - [Technical/Development] - [프로그래밍] Fizzbuzz 문제에 대하여(1)

- Barracuda -