복면산 문제

무엇을 만드나

글자 뒤에 숨은 숫자를 어떻게 찾을까요?

주어진 문제

AB + BA = CC가 성립하도록 A, B, C에 들어갈 숫자를 찾는 프로그램을 만듭니다. 같은 글자는 같은 숫자, 다른 글자는 반드시 다른 숫자입니다.

이렇게 숫자를 글자로 가려 놓은 퍼즐을 복면산이라고 합니다. 사람은 이런 문제를 머리를 써서 경우를 줄여 풉니다. 컴퓨터는 다르게 갑니다. 가능한 경우를 그냥 전부 넣어 봅니다. 이 방법을 완전 탐색이라고 합니다.

단계	여기서 답할 질문
1 요구 분석	몇 개를 찾을 것이고 어떤 제약이 있는가
2 설계	몇 가지를 넣어 봐야 하고 어떻게 줄일 것인가
3 구현	반복을 몇 겹으로 쌓고 어디서 건너뛸 것인가
4 테스트	답이 맞는지 어떻게 확인하는가

먼저 개발 문서 양식을 내려받으세요

읽기만 하지 말고 직접 채워 보세요. 단계마다 자기 답을 적어 두면 그 기록이 요구 사항 명세서이자 설계서가 됩니다. 답을 보기 전에 먼저 적어 봅니다.

Python 양식 내려받기 C 양식 내려받기

요구 분석과 설계는 언어와 상관없습니다. 두 양식의 앞부분은 같고, 구현을 적는 자리만 언어에 맞춰 다릅니다. 수업에서 쓰는 언어에 맞는 것을 받으면 됩니다. 이 강의노트의 코드 예시는 파이썬으로 되어 있습니다.

1단계 · 무엇을 만들 것인가

「답을 찾아라」는 몇 개를 찾으라는 말일까요?

되물어야 할 것들

답이 하나뿐인가요? 여럿이면 다 내놓나요, 하나만 내놓나요
0을 쓸 수 있나요? AB의 A가 0이면 두 자리 수가 아닙니다
정말 다 달라야 하나요? A와 C가 같아도 되나요
답이 없으면? 아무것도 못 찾으면 무엇을 내놓나요
어떤 모양으로 내놓나요? 숫자 셋만인가요, 식까지 보여 주나요

정리한 요구 사항

입력은 받지 않는다. 문제가 정해져 있으므로 실행하면 바로 답이 나온다.
A, B, C는 1부터 9까지의 숫자다. 세 자리 모두 맨 앞자리라 0이 될 수 없다.
A, B, C는 서로 모두 달라야 한다.
AB + BA = CC를 만족하는 모든 조합을 찾는다.
찾은 조합을 한 줄에 하나씩 내놓는다.

이 문제에서는 0까지 넣어 찾아도 답이 같습니다.

1번이 이 실습의 성격을 정합니다

입력을 받지 않는 프로그램입니다. 알고리즘이 갖춰야 할 조건으로 보아도 입력은 0개여도 됩니다. 출력은 반드시 있어야 하지만 입력은 없어도 됩니다.

스스로 확인

요구 사항 4번이 「모든 조합」이라고 되어 있습니다. 만약 「하나만 찾으면 된다」로 정했다면 프로그램이 어떻게 달라질까요?

2단계 · 몇 가지를 넣어 봐야 하나

다 해 본다는 것은 정확히 몇 번을 뜻할까요?

토막	무엇을 정하는가
입력	없다 — 문제가 프로그램 안에 들어 있다
처리	A, B, C에 넣을 수 있는 모든 조합을 만들어 식을 확인한다
출력	조건을 만족한 조합들 — 여러 줄일 수 있다

글자로 적힌 수를 계산식으로 바꾸기

AB는 A와 B를 곱하라는 뜻이 아니라 두 자리 수입니다. 십의 자리가 A, 일의 자리가 B이므로 A×10 + B입니다. 마찬가지로 BA는 B×10 + A, CC는 C×10 + C입니다. 이 옮겨 적기를 못 하면 문제를 코드로 옮길 수가 없습니다.

몇 번을 확인하게 되나

A가 9가지, B가 9가지, C가 9가지이니 9 × 9 × 9 = 729가지입니다. 사람에게는 많지만 컴퓨터에게는 눈 깜짝할 사이입니다. 「다 해 보면 되지 않나?」가 실제로 답이 되는 것이 사람의 문제 풀이와 가장 크게 다른 점입니다.

푸는 순서

A를 1부터 9까지 반복한다.
그 안에서 B를 1부터 9까지 반복한다.
A와 B가 같으면 더 볼 것 없이 건너뛴다.
그 안에서 C를 1부터 9까지 반복한다.
C가 A나 B와 같으면 건너뛴다.
(A×10 + B) + (B×10 + A)가 (C×10 + C)와 같으면 세 값을 내놓는다.

3번의 자리가 중요합니다

A와 B가 같은지 보는 검사가 C의 반복보다 앞에 있습니다. 여기서 걸러 내면 C를 아홉 번 도는 일을 통째로 건너뜁니다. 안쪽에서 검사하면 답은 같지만, A와 B가 같은 아홉 경우마다 C를 아홉 번씩 돌아 반복을 81번 더 돌게 됩니다. 완전 탐색에서는 거를 수 있을 때 최대한 빨리 거릅니다.

스스로 확인

설계 6번의 식을 손으로 정리해 보세요. (10A + B) + (10B + A)를 묶으면 무엇이 되고, 10C + C는 무엇이 되나요? 양쪽을 비교하면 놀랍도록 간단한 조건이 나옵니다.

3단계 · 파이썬으로 옮기기

반복을 세 겹으로 쌓아 봅니다.

먼저 스스로 적어 본 뒤에 코드를 보세요. 반복 안에 반복이, 그 안에 또 반복이 들어갑니다.

복면산.완전탐색.py

# A, B, C가 될 수 있는 모든 조합을 하나씩 넣어 본다
for a in range(1, 10):
    for b in range(1, 10):
        if a == b:
            continue  # 서로 다른 숫자여야 한다
        for c in range(1, 10):
            if c == a or c == b:
                continue
            # AB + BA 가 CC 와 같은지 그대로 확인한다
            if (a * 10 + b) + (b * 10 + a) == (c * 10 + c):
                print(a, b, c)

「건너뛰기」는 그만두는 것이 아닙니다

이번 한 바퀴만 그만두고 다음 값으로 넘어가라는 뜻입니다. 반복 전체를 끝내는 것이 아닙니다. 이것을 안 쓰고 조건이 맞을 때만 안으로 들어가게 적어도 결과는 같습니다. 다만 조건이 늘어날수록 안으로 계속 들여쓰게 되어 읽기 어려워집니다.

실행해 보면 답이 32개 나옵니다

답이 하나일 거라고 짐작했다면 놀랄 일입니다. 1과 2와 3, 1과 3과 4… 더해서 9를 넘지 않는 서로 다른 두 수면 모두 답입니다. 「답을 찾아라」라는 문제가 답이 여럿일 수 있다는 것을 요구 사항 4번에서 미리 정해 두었기에 당황하지 않는 것입니다.

스스로 확인

A와 B가 같은지 보는 검사를 가장 안쪽으로 옮기면 답이 달라질까요? 달라지지 않는다면 무엇이 달라질까요?

4단계 · 넣어 보고 확인하기

입력이 없는 프로그램은 어떻게 테스트할까요?

넣을 값이 없으니 나온 답이 정말 조건을 만족하는지 다시 확인해야 합니다. 답 몇 개를 골라 손으로 검산하고, 빠진 답이 없는지도 검토합니다.

확인할 것	어떻게 확인하나
답이 맞는가	1 2 3이 나왔다면 12 + 21 = 33인지 손으로 계산해 본다
개수가 맞는가	A + B = C이고 셋이 다른 경우를 세어 보면 32가지다
규칙을 어긴 답이 없는가	나온 줄 중에 같은 숫자가 두 번 나오는 줄이 있는지 순회한다
0이 안 나오는가	세 자리 중 어디에도 0이 없어야 한다

결과가 어긋났다면 여기부터 봅니다

같은 숫자가 겹친 답이 나온다 — 건너뛰는 조건이 빠졌거나 비교 대상을 하나 빠뜨렸습니다
0이 들어간 답이 나온다 — 반복 범위를 0부터 시작했고, 서로 다른지 보는 검사도 빠졌습니다. 이 식에서는 0이 끼면 두 숫자가 반드시 같아지므로 범위만 틀려서는 드러나지 않습니다
답이 하나도 안 나온다 — 두 자리 수로 옮기는 식에서 10을 곱하는 자리를 봅니다
답이 너무 많이 나온다 — 세 값이 서로 다른지 세 쌍 모두 확인하고 있는지 봅니다

「답이 나왔다」와 「답이 다 나왔다」는 다릅니다

답이 몇 개 보이면 잘 도는 것처럼 느껴집니다. 그런데 걸러 내는 조건을 잘못 적으면 맞는 답까지 함께 버려집니다. 나온 답이 전부 맞더라도 빠진 답이 있는지는 그것만으로 알 수 없습니다. 개수를 세어 보는 확인이 그래서 필요합니다.

스스로 확인

답 중에 1 8 9가 있습니다. 손으로 검산해 보세요. 그리고 2 8 10이 답이 될 수 없는 이유는 무엇인가요?

더 해 보기

손으로 줄이면 얼마나 빨라질까요?

설계 절의 「스스로 확인」에서 식을 정리해 보셨다면 알아차렸을 것입니다. AB + BA는 언제나 11 × (A + B)이고 CC는 언제나 11 × C입니다. 그러니 조건은 A + B = C 하나로 줄어듭니다. 요구 분석 절에서 0까지 넣어 찾아도 답이 같다고 한 까닭도 여기서 나옵니다. A나 B가 0이면 C가 나머지 하나와 같아져 서로 달라야 한다는 조건에 걸리기 때문입니다.

스스로 해 본 뒤에 열어 보세요

더 알아보기: 반복을 두 겹으로 줄인 코드

C를 찾아 돌 필요가 없습니다. A와 B가 정해지면 C는 계산으로 나옵니다. 최대 729가지를 검사하던 것이 최대 81가지로 줄었습니다.

# 손으로 정리해 두면 A + B = C 만 보면 된다
for a in range(1, 10):
    for b in range(1, 10):
        if a == b:
            continue
        c = a + b
        if c > 9 or c == a or c == b:
            continue
        print(a, b, c)

두 코드는 같은 32개를 내놓습니다. 같은 답을 내는 서로 다른 방법의 짝입니다. 다만 줄인 쪽은 이 문제에만 통합니다. 식이 조금만 달라져도 정리를 다시 해야 합니다. 완전 탐색은 느린 대신 어떤 식에든 통합니다.

한 걸음 더

식을 ABC + CBA = DDD로 바꿔 보기 — 반복이 몇 겹이 되고 몇 번을 돌까요
답의 개수만 세어 마지막에 한 번 내놓기
글자가 여덟 개인 복면산은 완전 탐색으로 몇 번을 돌아야 할지 계산해 보기. 수백만 번 정도는 컴퓨터가 금방 끝내지만, 글자가 하나 늘 때마다 경우의 수가 얼마나 불어나는지 감이 잡힙니다

스스로 확인

글자가 여덟 개인 복면산의 경우를 계산해 보세요. 서로 다른 글자 여덟 개에 0~9를 넣는 경우의 수는 얼마일까요? 「다 해 보면 된다」가 언제부터 통하지 않는지 생각해 보세요.