💻 백트래킹(Backtracking): "가보고 아니면 돌아와, 그게 정답이야"
안녕? 87년생 시니어 개발자 형이야. 오늘은 알고리즘 공부하다 보면 한 번은 꼭 마주치는 '백트래킹'에 대해 이야기해 줄게. 실무에서도 의사결정 최적화할 때 자주 쓰니까 잘 들어봐.
컴퓨터 과학에서 백트래킹(Backtracking)은 모든 가능성을 다 뒤져보되, "어? 이 길은 답이 아니네" 싶은 순간 바로 포기하고 직전 단계로 돌아가는 영리한 탐색 기법이야. 이걸 제약 충족 문제라고 하는데, 가장 유명한 게 바로 체스판에 퀸을 놓는 N-Queen 문제지. 그냥 다 해보는 브루트 포스랑 비슷해 보이지만, 안 될 싹을 미리 잘라버리는 가지치기(Pruning)가 핵심이야.
1. 백트래킹의 핵심 기술 원리와 작동 방식
백트래킹은 기본적으로 깊이 우선 탐색(DFS)을 베이스로 해. 상태 공간 트리라는 가상의 지도를 그리면서 내려가다가, 조건에 안 맞으면 자식 노드는 쳐다보지도 않고 부모로 올라오지. "미로에서 막다른 길을 만나면 다시 갈림길로 돌아가서 다른 길을 찾는 것"이랑 똑같아. 이걸 재귀 함수로 짜면 코드가 아주 우아해지는데, '유망성(Promising)'을 판단하는 함수가 이 알고리즘의 심장이야.
가지치기(Pruning): 노가다를 줄이는 기술
성능은 결국 얼마나 잘 쳐내느냐에 달렸어. N-Queen에서 퀸을 놓을 때, 지금 자리가 다른 퀸한테 공격받는 자리인지 빛의 속도로 판단해서 쳐내야 해. 가지치기를 안 하면 $N^N$이라는 말도 안 되는 연산을 해야 하지만, 백트래킹을 쓰면 탐색 범위가 확 줄어들어. 실무에서도 불필요한 CPU 오버헤드를 줄이는 데 결정적이지.
이론적으론 $O(N!)$이라 무서워 보이지만, 실무에선 가지치기 한 번에 연산량이 수천 배씩 차이 나니까 제약 조건을 얼마나 정교하게 설계하느냐가 실력이야.
2. 효율적인 백트래킹 구현 방법 및 단계별 가이드
제대로 짜려면 상태의 변경과 복구를 귀신같이 관리해야 해. 다음 단계로 갈 때 선택을 기록했다면, 돌아올 때는 반드시 그 기록을 지워야 해. 안 그러면 다음 탐색 때 유령 데이터 때문에 결과가 다 꼬여버리거든.
비트마스킹(Bitmasking)으로 튜닝하기
여기서 한 단계 더 나가는 팁! 퀸의 공격 경로를 배열 대신 비트마스킹으로 관리해봐. "전구 스위치 여러 개를 한 번에 조절하듯이 이진수 비트로 상태를 체크하는 방식"인데, 메모리도 적게 먹고 하드웨어 수준에서 비트 연산을 하니까 속도가 진짜 빨라져.
기저 조건(Base Case)은 생명줄이야
재귀 함수 짤 때 "언제 멈출지"부터 정해. N-Queen은 모든 행에 퀸을 다 놨을 때가 끝이지. 이거 명확하게 안 하면 스택 오버플로우 맛보게 될 거야. 형은 실무에서 메모리 아끼려고 1차원 배열로 위치를 관리하는 편인데, 이런 공간 복잡도 최적화도 꼭 고민해 봐.
파이썬(Python) 기반의 N-Queen 표준 소스 코드
def n_queen(row, n, pos, diag1, diag2):
if row == n:
return 1
count = 0
for col in range(n):
# 유망성 판단 (열, 대각선 체크)
if not (pos[col] or diag1[row + col] or diag2[row - col + n - 1]):
# 상태 변경
pos[col] = diag1[row + col] = diag2[row - col + n - 1] = True
count += n_queen(row + 1, n, pos, diag1, diag2)
# 상태 복구 (Backtrack - 이게 제일 중요!)
pos[col] = diag1[row + col] = diag2[row - col + n - 1] = False
return count
3. 시니어 형의 실무 삽질기
3년 전쯤 퍼즐 게임 레벨 에디터를 만들 때였어. 물체들을 안 겹치게 자동 배치하는 로직을 짰는데, 의욕만 앞서서 백트래킹을 돌렸지. 근데 실행만 하면 자리가 없다고 나오는 거야. 알고 보니 재귀에서 돌아올 때 상태를 초기화(Undo)하는 걸 빼먹었더라고. 한 번 놨던 자리가 계속 채워진 걸로 인식되니 나중엔 퀸은커녕 쫄병 하나도 못 놓는 먹통 시스템이 된 거지.
그때 인천 개발자 모임 선배님이 "형씨, 갔던 길은 지우고 와야지?"라고 한마디 하시는데 정말 뒤통수를 세게 맞은 기분이었어. 고작 코드 한 줄 차이였거든. 너희는 형처럼 상태 복구 잊어서 퇴근 늦어지지 마라. 복잡한 문제일수록 되돌아오는 과정을 꼼꼼히 챙기는 게 실력이다!
- 백트래킹 핵심: 안 되는 길은 즉시 유턴! 불필요한 연산을 획기적으로 줄이는 게 목표야.
- 가지치기: 제약 조건을 빡빡하게 설계해서 트리의 가지를 최대한 일찍 쳐내야 해.
- 상태 복구: 재귀에서 돌아올 때는 반드시 `Undo` 처리를 해서 이전 상태로 원상복구 할 것.
- 최적화: 배열 대신 비트마스킹을 써보길 권장해. 하드웨어가 좋아할 거야.
코딩은 결국 엉덩이 싸움이다. 이 글들도 같이 보면서 끝까지 포기하지 마라. 형이 응원한다.
궁금한 게 있으면 언제든 댓글 남겨줘. 재택근무 하다가 짬짬이 확인해서 도와줄게!
