24 게임 솔버를 만든 방법: TypeScript로 구현한 브루트 포스(Brute-Force)와 우아함의 만남

24 게임(24 Game)은 보기에는 매우 단순합니다. 4개의 숫자가 주어졌을 때, 이를 +, -, ×, ÷ 연산자를 사용하여 정확히 24로 만드는 것입니다. 쉬워 보이나요? 1, 5, 5, 5를 풀어보려고 시도해 보세요. 대부분의 사람들을 당황하게 만들 것입니다.

저는 제 수학 퍼즐 플랫폼을 위해 완전한 솔버(Solver)를 구축했으며, 이 알고리즘은 조합론 (Combinatorics), 표현 트리 (Expression Trees), 그리고 부동 소수점 함정 (Floating-point traps)을 다루는 훌륭한 연습이 되었습니다. 그 과정을 안내해 드리겠습니다.

문제 공간 (The Problem Space)

4개의 숫자, 4개의 연산자, 그리고 괄호. 가능성은 얼마나 될까요?

• 4개 숫자의 순열 (Permutations): 최대 24개 (4!)
• 연산자 조합 (Operator combinations): 4³ = 64 (3개의 슬롯, 각 슬롯당 4개의 선택지)
• 괄호 배치 패턴 (Parenthesization patterns): 5개 (카탈랑 수 (Catalan number) C₃)

총합: 24 × 64 × 5 = 7,680번의 계산. 현대 하드웨어에게는 사소한 수준입니다.

핵심 통찰은 4개의 피연산자 (Operands)를 결합하기 위한 **5가지 이진 트리 구조 (Binary tree structures)**를 모두 열거해야 한다는 점입니다. 이는 4개의 항목으로 이루어진 수열에 완전히 괄호를 치는 5가지 방식에 대응합니다.

5가지 표현 패턴 (The Five Expression Patterns)

숫자 a, b, c, d와 연산자 op1, op2, op3에 대하여:

Pattern 1: ((a op1 b) op2 c) op3 d
Pattern 2: (a op1 (b op2 c)) op3 d
Pattern 3: (a op1 b) op2 (c op3 d)
...

이 다섯 가지 패턴은 이진 연산자 (Binary operators)로 4개의 숫자를 결합하는 모든 가능한 방법을 포괄합니다. 어떤 표현식도 탐색되지 않은 채 남겨지지 않습니다.

TypeScript로 구현한 알고리즘

1단계: 순열 생성 (중복 제거 포함)

입력값에 중복이 포함된 경우 (예: 5, 5, 5, 1), 많은 순열이 동일합니다. 저희는 이를 필터링하기 위해 Set을 사용합니다:

function permutations(arr: number[]): number[][] {
  if (arr.length <= 1) return [arr];

...

5, 5, 5, 1의 경우, 이 과정을 통해 24개의 순열이 단 4개로 줄어듭니다.

2단계: 각 패턴 평가

핵심 루프는 모든 순열 × 연산자 × 패턴을 반복합니다:

const operators = ['+', '-', '*', '/'];

function operate(a: number, b: number, op: string): number {
...

각 패턴에 대해 단계별로 평가하며, 0으로 나누기(Division by zero)나 유효하지 않은 결과가 발생하는 경우 쇼트서킷 (Short-circuiting) 처리합니다:

// 패턴 3: (a op1 b) op2 (c op3 d)
try {
  const r1 = operate(a, b, op1);
...

3단계: 부동 소수점 정밀도 (Floating-Point Precision) 처리

이 부분이 까다로운 지점입니다. 8 / (3 - 8/3) = 24와 같은 경우, 중간 결과값에 분수가 포함됩니다. 직접적인 일치 확인(r3 === 24)은 부동 소수점 오차(floating-point errors)로 인해 실패하게 됩니다.

해결책: 엡실론 비교 (epsilon comparison)를 사용합니다:

if (Math.abs(r3 - 24) < 0.0001) {
  // 이것은 유효한 해답입니다
}

이 작은 허용 오차(0.0001)는 잘못된 양성(false positives)을 피하면서 모든 예외 케이스를 처리합니다.

종합하기

export function solve24(numbers: number[]): Solution[] {
  const solutions: Solution[] = [];
  const seen = new Set<string>();
...

전체 솔버는 어떤 입력에 대해서도 1ms 미만으로 실행됩니다. 이 경우에는 브루트 포스 (Brute-force) 방식이 완벽하게 적합합니다.

까다로운 예시들

입력	해답
1, 5, 5, 5	5 × (5 - 1/5) = 24
...

이러한 퍼즐들은 사람들을 포기하게 만들곤 합니다. 그리고 바로 그렇기 때문에 솔버를 갖는 것이 만족스러운 것입니다.

직접 해보기

저는 이 솔버를 저의 수학 퍼즐 플랫폼에 통합했습니다. 이 알고리즘을 정확히 사용하는 내장 힌트 시스템과 함께 24 게임을 즐길 수 있습니다:

👉 MathPuzzleHub에서 24 게임 플레이하기

솔버는 "해답 보기 (Show Solution)" 버튼의 동력이 됩니다. 솔버는 모든 유효한 식을 찾아내고 이를 단계별로 표시합니다.

성능 참고 사항

• 최악의 경우 (1, 2, 3, 4와 같이 4개의 서로 다른 숫자): 약 7,680번의 연산, 여전히 1ms 미만
• 최선의 경우 (6, 6, 6, 6와 같이 모두 동일한 숫자): 단 1개의 고유 순열, 320번의 연산
• 메모리: 최소 수준 — 최대 10개의 해답 문자열만 저장

만약 이를 5개 또는 6개의 숫자로 확장하고 싶다면, 브루트 포스에서 재귀적 축소 (recursive reduction) 방식(임의의 두 숫자를 선택하여 결합하고, 더 작아진 집합에 대해 재귀 호출)으로 전환해야 합니다. 하지만 클래식한 4개 숫자 게임의 경우, 브루트 포스는 우아하고 빠릅니다.

핵심 요약

1. 브루트 포스 (Brute force)는 과소평가되어 있습니다. 7,680번의 연산은 아무것도 아닙니다. 과도한 엔지니어링 (Over-engineer)을 하지 마세요.
2. **5가지 괄호 배치 패턴 (Five parenthesization patterns)**은 4개의 피연산자에 대한 모든 이진 표현 트리 (Binary expression trees)를 커버합니다. 이는 카탈랑 수 (Catalan numbers)에서 기인합니다.
3. **부동 소수점 엡실론 비교 (Floating-point epsilon comparison)**는 필수적입니다. === 24 방식은 나눗셈이 포함된 유효한 해를 놓칠 수 있습니다.
4. **중복 제거 (Deduplication)**는 성능 (더 적은 순열)과 UX (중복된 해를 보여주지 않음) 측면 모두에서 중요합니다.

즐거운 문제 풀이 되세요! 🧮

TypeScript와 Next.js로 제작되었습니다. MathPuzzleHub에서 더 많은 수학 게임을 확인해보세요.