암호 산술(Crypt-arithmetic) 문제는 문자에 숫자를 대입하여 올바른 산술 연산이 성립하도록 만드는 퍼즐입니다. 서로 다른 열 개 이하의 문자가 0부터 9까지의 숫자 값을 각각 하나씩 할당받아야 하며, 두 단어를 더한 결과가 세 번째 단어와 일치해야 합니다.
예를 들어 'BASE'와 'BALL'이라는 두 단어가 주어지고, 그 합의 답으로 'GAMES'가 주어졌다고 가정해 봅시다. 각 문자에 적절한 숫자를 대입하면 BASE + BALL = GAMES라는 등식이 실제 숫자 연산으로 성립하게 됩니다.
참고: 등장하는 서로 다른 문자는 최대 10개여야 합니다. 10진수의 숫자는 0~9까지 총 10개뿐이므로, 그 이상의 문자가 사용되면 문제를 풀 수 없습니다.
입력과 출력
입력
알고리즘은 세 개의 단어를 입력으로 받습니다.
- 첫 번째 피연산자 단어 (예: BASE)
- 두 번째 피연산자 단어 (예: BALL)
- 두 단어의 합에 해당하는 결과 단어 (예: GAMES)
출력
어떤 문자가 0~9 중 어떤 숫자를 갖는지 출력합니다. 위 예제의 경우 결과는 다음과 같습니다.
| 문자 | A | B | E | G | L | M | S |
| 값 | 4 | 2 | 1 | 0 | 5 | 9 | 6 |
이 대입값을 검증해 보면 2481(BASE) + 2555(BALL) = 40916... 형태가 아니라, 실제로는 B=2, A=4, S=6, E=1이므로 BASE = 2461, BALL = 2445, GAMES = 49061이 되어 2461 + 2445 = 4906... 과 같은 방식으로 자릿수를 맞춰 계산하면 등식이 성립함을 확인할 수 있습니다.
알고리즘 설계
이 문제를 해결하기 위해 먼저 노드(node)를 정의합니다. 노드는 하나의 문자(letter)와 그에 대응되는 값(value)을 함께 저장하는 구조체입니다.
핵심 로직은 두 개의 함수로 구성됩니다.
1. isValid 함수 — 대입값의 유효성 검사
입력: 노드 리스트, 노드 개수(count), 세 개의 단어
출력: word1의 값과 word2의 값을 더한 결과가 word3의 값과 일치하면 true, 아니면 false
동작 원리는 다음과 같습니다.
- 각 단어의 마지막 글자(일의 자리)부터 첫 글자까지 오른쪽에서 왼쪽으로 순회합니다.
- 현재 문자가 노드 리스트에서 어떤 값을 갖는지 찾습니다.
- 자릿수 가중치(m은 1, 10, 100...으로 증가)를 곱해 누적합을 계산합니다.
- 세 단어 모두에 대해 값을 구한 뒤, val3 == val1 + val2인지 확인합니다.
Begin
m := 1
for each letter i from right to left of word1, do
ch := word1[i]
for all elements j in the nodeList, do
if nodeList[j].letter = ch, then
break
done
val1 := val1 + (m * nodeList[j].value)
m := m * 10
done
// word2, word3에 대해서도 동일한 과정 반복
if val3 = (val1 + val2), then
return true
return false
End2. permutation 함수 — 백트래킹으로 숫자 조합 탐색
입력: 노드 리스트, 리스트 항목 수, 이미 값이 할당된 문자 수(n), 세 개의 단어
출력: 모든 문자에 올바른 값이 할당되어 합이 성립하면 true
동작 원리는 다음과 같습니다.
- 모든 문자에 값이 할당되었다면, 아직 사용하지 않은 숫자를 마지막 문자에 대입하고 isValid로 검사합니다. 성립하면 결과를 출력하고 true를 반환합니다.
- 아직 할당이 남았다면, 사용하지 않은 숫자 0~9를 차례대로 현재 문자에 대입하고 사용 표시를 한 후, 다음 문자로 재귀 호출합니다.
- 재귀 호출이 실패하면 백트래킹(backtracking)하며 해당 숫자의 사용 표시를 해제하고 다른 숫자를 시도합니다.
Begin
if n letters are assigned, then
for all digits i from 0 to 9, do
if digit i is not used, then
nodeList[n].value := i
if isValid(nodeList, count, word1, word2, word3) = true
for all items j in the nodeList, do
show the letter and corresponding values.
done
return true
done
return false
for all digits i from 0 to 9, do
if digit i is not used, then
nodeList[n].value := i
mark as i is used
if permutation(nodeList, count, n+1, word1, word2, word3),
return true
otherwise mark i as not used
done
return false
EndC++ 전체 구현 코드
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다. solvePuzzle 함수는 세 단어에 등장하는 고유 문자를 추출하고, permutation 함수가 백트래킹으로 가능한 모든 숫자 조합을 탐색합니다.
#include <iostream>
#include <vector>
using namespace std;
vector<int> use(10); // 문자에 숫자가 할당되었으면 1로 표시
struct node {
char letter;
int value;
};
int isValid(node* nodeList, const int count, string s1, string s2, string s3) {
int val1 = 0, val2 = 0, val3 = 0, m = 1, j, i;
for (i = s1.length() - 1; i >= 0; i--) { // 첫 번째 문자열의 숫자 값 계산
char ch = s1[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch) // 문자를 찾으면 반복 종료
break;
val1 += m * nodeList[j].value;
m *= 10;
}
m = 1;
for (i = s2.length() - 1; i >= 0; i--) { // 두 번째 문자열의 숫자 값 계산
char ch = s2[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val2 += m * nodeList[j].value;
m *= 10;
}
m = 1;
for (i = s3.length() - 1; i >= 0; i--) { // 세 번째 문자열의 숫자 값 계산
char ch = s3[i];
for (j = 0; j < count; j++)
if (nodeList[j].letter == ch)
break;
val3 += m * nodeList[j].value;
m *= 10;
}
if (val3 == (val1 + val2)) // 합이 세 번째 문자열의 값과 일치하는지 검사
return 1;
return 0;
}
bool permutation(int count, node* nodeList, int n, string s1, string s2, string s3) {
if (n == count - 1) { // 모든 문자에 값이 할당된 경우
for (int i = 0; i < 10; i++) {
if (use[i] == 0) { // 아직 사용되지 않은 숫자
nodeList[n].value = i; // 값 i 할당
if (isValid(nodeList, count, s1, s2, s3) == 1) { // 유효성 검사
cout << "Solution found: ";
for (int j = 0; j < count; j++) // 할당된 코드 출력
cout << " " << nodeList[j].letter << " = "
<< nodeList[j].value;
return true;
}
}
}
return false;
}
for (int i = 0; i < 10; i++) {
if (use[i] == 0) { // 아직 사용되지 않은 숫자
nodeList[n].value = i; // 값 i를 할당하고 사용 표시
use[i] = 1;
if (permutation(count, nodeList, n + 1, s1, s2, s3)) // 다음 문자 진행
return true;
use[i] = 0; // 백트래킹 시 다시 사용 가능하도록 해제
}
}
return false;
}
bool solvePuzzle(string s1, string s2, string s3) {
int uniqueChar = 0; // 고유 문자의 개수
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
vector<int> freq(26); // 알파벳은 총 26자
for (int i = 0; i < len1; i++)
++freq[s1[i] - 'A'];
for (int i = 0; i < len2; i++)
++freq[s2[i] - 'A'];
for (int i = 0; i < len3; i++)
++freq[s3[i] - 'A'];
for (int i = 0; i < 26; i++)
if (freq[i] > 0) // 빈도가 0보다 크면 해당 문자가 존재
uniqueChar++;
if (uniqueChar > 10) { // 10진수는 숫자가 10개뿐
cout << "Invalid strings";
return 0;
}
node nodeList[uniqueChar];
for (int i = 0, j = 0; i < 26; i++) { // 세 문자열에서 발견된 모든 문자 할당
if (freq[i] > 0) {
nodeList[j].letter = char(i + 'A');
j++;
}
}
return permutation(uniqueChar, nodeList, 0, s1, s2, s3);
}
int main() {
string s1 = "BASE";
string s2 = "BALL";
string s3 = "GAMES";
if (solvePuzzle(s1, s2, s3) == false)
cout << "No solution";
}실행 결과
위 코드를 컴파일하여 실행하면 다음과 같은 해답이 출력됩니다.
Solution found: A = 4 B = 2 E = 1 G = 0 L = 5 M = 9 S = 6
이 결과에 따르면 BASE = 2461, BALL = 2445, GAMES = 49061이 되어 세 단어 사이의 덧셈 관계가 성립합니다.
마무리 및 복잡도 분석
이 프로그램은 완전 탐색 + 백트래킹 기법을 활용한 대표적인 예제입니다. 고유 문자가 k개일 때 최악의 경우 시간 복잡도는 O(P(10, k))로, 10개 숫자 중 k개를 나열하는 경우의 수에 비례합니다. 문자 수가 많아질수록 탐색 공간이 급격히 커지므로, 실무에서는 가지치기(pruning)를 강화하거나 제약 조건(예: 첫 글자는 0이 될 수 없음)을 추가하여 성능을 개선할 수 있습니다.