[정글 베이직 6] 백 트래킹

 

크래프톤 정글 · 베이직 6 백트래킹으로 조합을 구현한다는 것

BEFORE

for i in range(1, n+1):
  for j in range(i+1, n+1):
    result.append([i, j])

→

AFTER

current.append(num)    # Choose
backtrack(num+1)       # Explore
current.pop()          # Unchoose

cedis · 2026.3.8

이 문제 처음 봤을 때 그냥 for문 두 번 쓰면 되는 거 아닌가 생각했다.

근데 k가 3이면? 4이면? for문을 k개 중첩해야 한다는 걸 깨닫는 순간 — 이건 코드가 아니라 복사 붙여넣기다 싶었다.

그래서 백트래킹을 배웠다.

· · ·

문제 소개

1부터 n까지의 숫자 중에서 k개를 골라 만들 수 있는 모든 조합을 구하는 것.
순서는 상관없다. [1,2]와 [2,1]은 같은 조합이다.

항목	내용
입력	n (전체 개수), k (선택 개수)
출력	가능한 모든 조합의 리스트
핵심 도구	backtrack(), 재귀, 리스트

예제 입출력은 이렇다.

# 입력
n = 4, k = 2

# 출력
[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

· · ·

일단 중첩 for문부터 썼다

k=2일 때는 이렇게 해결할 수 있다.

# k=2 전용 코드 — 딱 이때만 쓸 수 있다
result = []
for i in range(1, n+1):
    for j in range(i+1, n+1):
        result.append([i, j])

동작은 한다. 결과도 맞다.
근데 k=3이 되는 순간 for문을 하나 더 써야 한다. k가 바뀔 때마다 코드를 통째로 다시 써야 한다는 뜻이다.

백트래킹을 사용하면 k가 얼마든 같은 코드로 처리할 수 있습니다

읽자마자 알았다. 이게 맞는 방향이라고.

· · ·

코드 구조를 먼저 뜯어봤다

함수가 실행되는

순서 — 공부하면서 직접 만든 다이어그램

주어진 템플릿은 이렇다.

def combinations(n, k):
    result = []
    def backtrack(start, current):
        # 베이스 케이스 — k개 골랐을 때
        pass
        # start ~ n 중 하나씩 고르면서 탐색
        pass
    backtrack(1, [])
    return result

처음엔 구조 자체가 낯설었다. 함수 안에 함수가 있고, 뭘 언제 실행하는지 감이 안 왔다.
팀 선발에 비유했더니 바로 이해됐다.

코드	비유
result	완성된 팀 명단을 적는 종이
current	지금 임시로 모인 팀원들
start	다음 후보를 찾기 시작하는 번호
backtrack()	선발하고, 탐색하고, 빼는 과정 전체

· · ·

백트래킹의 핵심은 3단계다

백트래킹은 항상 같은 패턴으로 움직인다.

1

Choose

current.append(num)

2

Explore

backtrack(num+1)

3

Unchoose

current.pop()

고르고 → 탐색하고 → 되돌린다.
되돌린다는 게 핵심이다. pop()이 없으면 한번 고른 숫자가 계속 쌓인다.
pop()이 있어야 "이 선택을 안 했다면?"을 시도할 수 있다.

for num in range(start, n+1):
    current.append(num)           # 1. Choose   — num을 고른다
    backtrack(num + 1, current)  # 2. Explore  — 다음을 탐색한다
    current.pop()                 # 3. Unchoose — 선택을 되돌린다

· · ·

베이스 케이스 — 언제 멈추나

재귀는 반드시 멈추는 조건이 있어야 한다.
k개를 다 골랐으면 — 그게 하나의 완성된 조합이다.

if len(current) == k:
    result.append(current[:])  # 복사해서 저장 — 슬라이싱이 중요하다
    return

current[:]로 복사하는 이유가 있다.
current는 이후에도 계속 바뀐다. 그냥 넣으면 나중에 result 안의 값도 같이 바뀐다.
슬라이싱으로 그 순간의 스냅샷을 저장해야 한다.

· · ·

n=4, k=2 실행 흐름

실제로 어떻게 동작하는지 따라가보면 이렇다.

①

backtrack(1, []) 시작
비어있는 팀, 1번부터 후보 탐색

②

1 선택 → backtrack(2, [1])
2 선택 → [1,2] 완성, result에 추가

③

2 pop() → 3 선택 → [1,3] 완성
3 pop() → 4 선택 → [1,4] 완성

④

1 pop() → 2 선택 → backtrack(3, [2])
[2,3], [2,4] 순서로 완성

⑤

마지막 → [3,4] 완성
result = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

num+1을 넘기는 이유가 여기서 보인다.
항상 이전에 고른 것보다 큰 숫자만 탐색하니까 [1,2]와 [2,1]이 중복 생성되지 않는다.

· · ·

C 스타일 중첩 for문이랑 뭐가 다른가

C 언어 배경이 있으면 이게 그냥 중첩 루프처럼 보인다. 맞는 직관이다.

중첩 for문 (k 고정)	백트래킹 (k 가변)
k=2: for 2개 중첩	k=2, 3, 10 모두 같은 코드
k가 바뀌면 코드를 다시 써야 함	k를 매개변수로 전달하면 끝
깊이가 컴파일 타임에 고정됨	재귀로 깊이를 런타임에 결정

백트래킹은 중첩 for문을 재귀로 일반화한 것이다.
개념은 완전히 같다. 다만 깊이가 고정이냐, 유동이냐의 차이다.

· · ·

최종 코드

BEFORE — k=2 전용

result = []
for i in range(1, n+1):
  for j in range(i+1, n+1):
    result.append([i, j])

# k=3이면 for를 하나 더 써야 함
# k=4이면 또 하나 더...

AFTER — k 제한 없음

def combinations(n, k):
  result = []
  def backtrack(start, cur):
    if len(cur) == k:
      result.append(cur[:])
      return
    for num in range(start,n+1):
      cur.append(num)
      backtrack(num+1, cur)
      cur.pop()
  backtrack(1, [])
  return result

전체 함수로 정리하면 이렇다.

def combinations(n, k):
    result = []

    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])   # 스냅샷 저장
            return

        for num in range(start, n + 1):
            current.append(num)            # Choose
            backtrack(num + 1, current)   # Explore
            current.pop()                  # Unchoose

    backtrack(1, [])
    return result


# 테스트
print(combinations(4, 2))
# [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

print(combinations(4, 3))
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

중첩 for문이랑 백트래킹은 같은 생각이다.

다른 건 딱 하나 — 깊이가 고정이냐, 코드가 스스로 결정하냐.

Choose → Explore → Unchoose.
이 세 줄이 백트래킹의 전부다.

다음 문제로 넘어갔다.

🌿