공간-시간 트레이드오프와 백트래킹(Backtracking)

알고리즘 디자인에서는 메모리(공간)를 더 써서 시간(속도)을 버는 트레이드오프 기법과, 가능성 없는 경로를 빠르게 포기하는 백트래킹(Backtracking) 기법이 매우 중요하게 다루어집니다.

1. 공간으로 시간을 버는 공간-시간 트레이드오프

• 개념: 보조 메모리 공간을 미리 할당하거나 데이터를 특수한 구조로 정렬해 두어 연산 속도를 극적으로 단축시킴.
• 대표 기법:
  1. 해싱 (Hashing): 키(Key)를 해시 함수에 입력하여 인덱스로 직접 접근함으로써 평균 $O(1)$ 탐색 달성.
  2. 루트업 테이블 / 사전 계산: 미리 계산된 값을 배열에 보관 (예: 삼각함수 테이블, 동적 계획법).
  3. 보이어-무어 문자열 매칭: 이동 테이블을 미리 생성하여 불필요한 문자열 비교 건너뛰기.

2. 백트래킹(Backtracking) 알고리즘

모든 가능한 해를 찾는 상태 공간 트리(State Space Tree) 탐색 도중, 어떤 노드가 유망하지 않다(Non-promising)고 판단되면 부모 노드로 되돌아가(Backtrack) 다른 자식 노드를 탐색하는 조건부 완전 탐색 기법입니다.

• 가지치기 (Pruning): 유망하지 않은 노드의 서브트리 방문을 즉시 중단하여 탐색 시간을 대폭 절감함.

3. 백트래킹의 대명사: N-Queen 문제

$N imes N$ 체스판 위에 $N$개의 퀸을 서로 공격할 수 없도록 배치하는 대표적인 백트래킹 문제입니다.

def solve_n_queens(n):
    col = set()
    pos_diag = set()  # (r + c)
    neg_diag = set()  # (r - c)
    res = 0

    def backtrack(r):
        nonlocal res
        if r == n:
            res += 1
            return
        for c in range(n):
            if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
                continue
            col.add(c)
            pos_diag.add(r + c)
            neg_diag.add(r - c)

            backtrack(r + 1)

            col.remove(c)
            pos_diag.remove(r + c)
            neg_diag.remove(r - c)

    backtrack(0)
    return res

print(solve_n_queens(4))  # 4-Queen 해의 개수: 2

4. 백트래킹 vs 단순 완전 탐색(DFS)

5. 자주 묻는 질문 (Q&A)

Q. 해싱에서 해시 충돌(Hash Collision)이 발생하면 어떻게 해결하나요? A. 체이닝(Chaining, 동일 버킷을 연결 리스트로 연결) 방식이나 개방 주소법(Open Addressing, 선형 탐사/이차 탐사/이중 해싱)을 통해 빈 슬롯을 찾아 저장합니다.