인터넷을 하다가 재미있는 문제를 하나 발견했습니다.
처음에는 도저히 방법이 떠오르지 않아 한참 고민했고, 결국 힌트를 하나씩 보면서 풀어봤습니다.
원리를 이해하고 나니
“와, 이런 방법으로 풀 수 있구나!”
하는 생각이 들었습니다.
이런 문제를 힌트 없이 풀어내는 사람들은 정말 대단하다는 생각도 들었습니다.
저는 힌트를 보고서야 풀었지만, 이런 문제들을 계속 고민하고 풀어보다 보면 제 머리도 조금씩 발전하지 않을까 생각해봅니다.
나중에 제가 다시 풀어볼 수도 있고, 다른 분들도 함께 고민하면서 재미를 느끼면 좋을 것 같아 하나씩 기록해보려고 합니다.
요즘 게임에서는 판단력이나 머리 쓰는 능력을 흔히 ‘뇌지컬’이라고 부르기도 하죠.
그럼 같이 뇌지컬을 키워봅시다.
뇌지컬 테스트 1번, 바로 시작합니다.
문제 – 64개의 동전과 체스판 문제
8×8 체스판의 64개 칸에 동전이 하나씩 놓여 있습니다. 각 동전은 무작위로 앞면 또는 뒷면을 향하고 있습니다.
두 사람 A와 B는 미리 전략을 정할 수 있습니다.
A가 먼저 방에 들어가면 64개의 칸 중 하나가 목표 칸으로 지정됩니다. A는 현재 동전 상태를 확인한 뒤 동전 하나만 뒤집고 방을 나와야 합니다.
그다음 B가 들어와 최종 동전 상태만 보고 A에게 지정되었던 목표 칸을 정확히 맞혀야 합니다.
두 사람은 서로 대화하거나 다른 표시를 남길 수 없습니다.
어떤 초기 동전 배치와 어떤 목표 칸이 주어져도 항상 성공할 수 있는 방법이 있을까?
우선 많은 고민을 해보고 정 풀리지 않으면 힌트를 하나씩 보는 것을 추천합니다.
힌트1
이진법으로 생각해보기
64는 다음과 같이 표현할 수 있습니다.
64 = 26
0부터 63까지의 64개 위치는 6비트 이진수로 모두 표현할 수 있습니다.
힌트2
XOR 연산을 이용하기
XOR은 비트 연산 방법 중 하나입니다.
일반적인 OR 연산은 둘 중 하나라도 1이면 1이 되지만, XOR은 두 값이 서로 다르면 1, 같으면 0이 됩니다.
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
그리고 XOR에는 이 문제를 푸는 데 아주 중요한 성질이 있습니다.
A XOR A = 0
A XOR 0 = A
이 성질을 이용하면 현재 동전들의 상태를 하나의 값으로 표현하고, 그 값을 원하는 위치의 값으로 바꿀 수 있습니다.
내가 이해한 방법
처음부터 8×8 체스판과 64개의 동전을 생각하니 너무 복잡했습니다.
그래서 문제를 최대한 작게 줄여서 생각해봤습니다.
8×8에서 가능한 방법이라면 2×2에서도 같은 원리로 가능하지 않을까?
우선은 2×2로 줄였지만 이것 역시 쉽지 않은 문제였습니다. 어떻게 하나만 바꿔서 확실한 값을 만들 수 있을까?
우선 두개의 힌트를 보고 나서야 정확히 이해 할수 있었습니다.
2×2라면 칸은 총 4개입니다. 각 칸에 0부터 3까지 번호를 붙이고 이진수로 표현하면 다음과 같습니다.
| 위치 | 이진수 |
|---|---|
| 0번 | 00 |
| 1번 | 01 |
| 2번 | 10 |
| 3번 | 11 |
예를 들어 현재 1번과 2번 위치의 동전이 앞면이라고 가정해보겠습니다.
앞면인 동전들의 위치를 XOR하면
01 XOR 10 = 11
이 됩니다.
즉, 현재 동전 상태를 나타내는 값은 11(3번)입니다.
이제 A에게 지정된 목표 칸에 따라 어떤 동전을 뒤집어야 하는지 생각해보겠습니다.
목표가 0번이라면
현재 상태는 11, 목표는 00입니다.
11 XOR 00 = 11
따라서 3번 동전을 뒤집습니다.
그러면 최종 XOR 값은 00이 되고, B는 이를 보고 목표가 0번이었다는 것을 알 수 있습니다.
목표가 1번이라면
현재 상태는 11, 목표는 01입니다.
11 XOR 01 = 10
따라서 2번 동전을 뒤집습니다.
그러면 최종 XOR 값은 01이 되고, B는 목표가 1번이었다는 것을 알 수 있습니다.
목표가 2번이라면
현재 상태는 11, 목표는 10입니다.
11 XOR 10 = 01
따라서 1번 동전을 뒤집습니다.
그러면 최종 XOR 값은 10이 되고, B는 목표가 2번이었다는 것을 알 수 있습니다.
목표가 3번이라면
현재 상태와 목표가 둘 다 11입니다.
11 XOR 11 = 00
따라서 0번 동전을 뒤집습니다.
0번은 이진수로 00이므로 XOR 결과에 영향을 주지 않습니다.
따라서 최종 XOR 값은 그대로 11이고, B는 목표가 3번이었다는 것을 알 수 있습니다.
여기까지 해보면 하나의 규칙이 보입니다.
현재 앞면인 동전들의 위치를 모두 XOR한 값을 S, A가 전달해야 할 목표 위치를 T라고 하면,
S XOR T = 뒤집어야 할 동전의 위치
가 됩니다.
예를 들어 현재 상태가 11이고 목표가 01이라면
11 XOR 01 = 10
이므로 10, 즉 2번 동전을 뒤집으면 됩니다.
결국 A는 현재 상태와 목표 위치를 XOR해서 어떤 동전을 뒤집을지만 결정하면 됩니다.
그리고 B는 방에 들어온 뒤 앞면인 동전들의 위치를 모두 XOR하면 A에게 지정되었던 목표 위치를 알아낼 수 있습니다.
다시 8×8로 돌아가면
2×2에서 원리를 이해했다면 8×8도 똑같습니다.
차이는 사용하는 비트의 수 뿐입니다.
2×2에서는 4개의 위치가 있으므로 2비트가 필요했습니다.
00 ~ 11 → 0 ~ 3
8×8에서는 64개의 위치가 있으므로 6비트가 필요합니다.
000000 ~ 111111 → 0 ~ 63
따라서 64개의 칸에 0번부터 63번까지 번호를 붙이고, 앞면인 동전들의 위치를 모두 XOR합니다.
그 값을 S, 전달해야 하는 목표 칸을 T라고 하면,
S XOR T
로 나온 번호의 동전 하나를 뒤집으면 됩니다.
그러면 B가 들어와 앞면인 동전들의 위치를 모두 XOR했을 때 결과는 정확히 T, 즉 A에게 지정되었던 목표 칸이 됩니다.
처음에는 동전 하나만 뒤집어서 64개의 위치 중 하나를 어떻게 전달하나 싶었는데, XOR을 이용하면 어떤 초기 상태에서도 정확한 위치를 전달할 수 있었던 것입니다.
마치며
특히 저는 처음부터 8×8 전체를 이해하려고 하기보다 2×2로 문제를 줄여서 직접 계산해보니 훨씬 이해하기 쉬웠습니다.
비록 힌트를 보고 풀었지만 이런 문제를 하나씩 고민하다 보면 언젠가는 비슷한 문제를 봤을 때 스스로 아이디어를 떠올릴 수 있지 않을까 기대해봅니다.
앞으로도 이렇게 신기하고 재미있는 퀴즈를 발견하면 뇌지컬 테스트 시리즈로 하나씩 올려보겠습니다.
같이 재미있게 풀어보고 뇌지컬을 키워봅시다.
