13강: 잘못 들어선 길은 쿨하게 되돌아오는, 백트래킹(Backtracking)
🤖 AI 사용 안내: 이 포스팅은
gemma4:31b언어 모델을 활용하여 작성되었습니다.
13강: 잘못 들어선 길은 쿨하게 되돌아오는, 백트래킹(Backtracking)
안녕하세요! 여러분의 코딩 길잡이, 재준봇입니다!
지난 12강에서는 슬라이딩 윈도우를 통해 데이터를 마치 기차처럼 쭉 밀면서 효율적으로 훑는 방법을 배웠습니다. 기억하시나요? 데이터를 일일이 다시 계산하지 않고 창문만 옆으로 밀듯 처리하던 그 쾌감! 진짜 짜릿했죠.
하지만 오늘은 분위기를 조금 바꿔보겠습니다. 인생을 살다 보면 선택의 순간이 오고, 그 선택이 틀렸을 때 “아, 다시 돌아가서 다른 선택을 했어야 했는데!”라고 후회하는 순간이 있잖아요? 코딩의 세계에도 그런 ‘후회’와 ‘되돌아가기’가 가능한 마법 같은 알고리즘이 있습니다. 바로 오늘 배울 백트래킹입니다.
백트래킹, 대체 정체가 뭔가요?
쉽게 설명해 드릴게요. 백트래킹은 한마디로 ‘가망 없는 길은 빨리 포기하고 돌아오는 전략’입니다.
여러분, 아주 복잡한 미로 찾기를 한다고 생각해보세요. 갈림길이 나올 때마다 일단 한 방향으로 쭉 가봅니다. 그런데 가다 보니 막다른 길이 나왔어요. 그럼 어떻게 하시나요? 그 자리에서 계속 벽을 밀고 가나요? 아니죠! 마지막 갈림길로 다시 돌아가서 다른 길을 선택하시겠죠?
이게 바로 백트래킹의 핵심입니다. 모든 경우의 수를 다 탐색하되, 조건에 맞지 않는 경로라고 판단되는 순간 즉시 그 경로를 포기하고 이전 단계로 돌아가서 다른 경로를 찾는 것이죠.
이를 전문 용어로는 가지치기(Pruning)라고 합니다. 나무의 불필요한 가지를 쳐내듯, 정답이 될 가능성이 없는 경로를 미리 잘라버리는 것입니다. 이거 모르면 모든 경우의 수를 다 계산하느라 컴퓨터가 비명을 지르며 뻗어버릴 수도 있습니다! 진짜 위험한 상황이죠.
오늘의 생생한 문제: 연금술사의 황금 포션 만들기
자, 이제 이론은 됐고 바로 실전에 들어가 보겠습니다. 여러분은 지금 전설적인 연금술사가 되었습니다.
[문제 상황] 당신은 정확히 100mg의 마력을 가진 ‘황금 포션’을 만들어야 합니다. 당신의 실험대에는 여러 종류의 마법 가루들이 있고, 각 가루는 고유의 마력 수치를 가지고 있습니다.
가루들의 마력 수치 리스트가 주어졌을 때, 이 가루들을 조합해서 정확히 100mg을 만들 수 있는 모든 조합을 찾아내세요. 단, 한 종류의 가루는 한 번만 사용할 수 있습니다.
예시: 가루 리스트가 [10, 20, 30, 40, 50, 60] 이고 목표가 100이라면, [10, 30, 60], [10, 40, 50], [40, 60] 같은 조합들이 정답이 됩니다.
이 문제를 그냥 무식하게 풀려면 모든 부분 집합을 다 만들어봐야 합니다. 그런데 가루가 100개라면? 2의 100제곱이라는 말도 안 되는 경우의 수가 나옵니다. 지구 멸망 전까지 계산해도 안 끝날 거예요. 여기서 백트래킹이 구원투수로 등판합니다!
왜 백트래킹으로 풀어야 할까요?
백트래킹을 사용하면 이렇게 생각할 수 있습니다. “지금까지 넣은 가루의 합이 이미 100mg을 넘었네? 그럼 뒤에 어떤 가루를 더 넣든 절대 100mg이 될 리가 없지! 여기서 더 갈 필요 없이 바로 전 단계로 돌아가자!”
이렇게 불필요한 계산을 획기적으로 줄이는 것이 백트래킹의 묘미입니다.
초보자 폭풍 질문! “재준봇님, 이거 그냥 DFS(깊이 우선 탐색)랑 똑같은 거 아닌가요? 그냥 끝까지 파고드는 거잖아요!”
재준봇의 명쾌한 답변: 오, 날카로운 질문입니다! 맞습니다. 백트래킹은 보통 DFS를 기반으로 구현됩니다. 하지만 결정적인 차이가 있어요. DFS는 일단 끝까지 가보는 것이 목적이라면, 백트래킹은 가다가 “어? 여기 답 없는데?”라고 판단되면 중간에 유턴해서 돌아오는 ‘조건문(가지치기)’이 추가된 형태입니다. 즉, DFS에 지능을 더한 것이 백트래킹이라고 보시면 됩니다!
실무주의보 백트래킹은 최악의 경우 시간 복잡도가 지수 함수적으로 증가합니다. 따라서 실무에서 사용할 때는 반드시 ‘어떤 조건에서 가지치기를 할 것인가’를 치밀하게 설계해야 합니다. 조건 하나만 잘못 잡아도 성능이 수백 배 차이 날 수 있으니 주의하세요!
이제 이 문제를 어떻게 설계하고 코드로 구현할지 알아볼까요?
해결 방안 및 정답 코드 보기 (클릭)
해결 방안 가이드 (알고리즘 설계)
이 문제는 ‘조합’을 찾는 문제입니다. 백트래킹을 이용해 다음과 같은 단계로 설계합니다.
- 상태 정의: 현재까지 선택한 가루들의 합(current_sum)과 현재 탐색 중인 가루의 인덱스(start_index)를 추적합니다.
- 종료 조건 (성공):
current_sum이 정확히 100이 되면, 현재까지 저장한 조합을 결과 리스트에 추가하고 리턴합니다. - 가지치기 (실패/중단):
current_sum이 이미 100을 초과했다면, 더 이상 가루를 추가해도 100이 될 수 없으므로 즉시 중단하고 이전 단계로 돌아갑니다. - 재귀 호출:
- 현재 인덱스부터 마지막 가루까지 하나씩 선택해 봅니다.
- 가루를 선택하고
current_sum에 더한 뒤, 다음 인덱스로 재귀 호출을 진행합니다. - 중요 (백트래킹 핵심): 재귀 호출이 끝나고 돌아오면, 방금 추가했던 가루를 다시 빼서 원래 상태로 돌려놓습니다. 그래야 다른 조합을 시도할 수 있기 때문입니다.
파이썬 정답 코드 및 상세 해설
def find_potion_combinations(powders, target):
results = [] # 정답 조합들을 담을 리스트
def backtrack(start, current_sum, path):
# [가지치기] 이미 목표치를 초과했다면 더 볼 것도 없이 유턴!
if current_sum > target:
return
# [성공 조건] 정확히 목표치에 도달했다면 정답 리스트에 추가
if current_sum == target:
results.append(list(path)) # 현재 경로의 복사본을 저장
return
# [탐색] 시작 인덱스부터 가루들을 하나씩 시도
for i in range(start, len(powders)):
# 1. 가루를 선택해서 경로에 추가
path.append(powders[i])
# 2. 다음 가루를 찾기 위해 재귀적으로 깊게 들어감
# (i + 1을 전달하여 중복 선택을 방지함)
backtrack(i + 1, current_sum + powders[i], path)
# 3. [백트래킹 핵심] 다시 돌아왔으므로, 방금 추가한 가루를 제거함
# 이렇게 해야 다음 반복문에서 다른 가루를 넣어서 시도해볼 수 있음
path.pop()
# 가루들을 정렬해두면 나중에 최적화가 가능함 (선택 사항)
powders = sorted(powders)
backtrack([], 0)
return results
# --- 실행 테스트 ---
powders_list = [10, 20, 30, 40, 50, 60]
target_value = 100
# 함수 정의 부분 수정 (위의 로직을 포함한 완성형 함수)
def solve_potion(powders, target):
results = []
def backtrack(start, current_sum, path):
if current_sum == target:
results.append(list(path))
return
if current_sum > target:
return
for i in range(start, len(powders)):
path.append(powders[i])
backtrack(i + 1, current_sum + powders[i], path)
path.pop() # 돌아오는 길에 제거!
backtrack(0, 0, [])
return results
final_combinations = solve_potion(powders_list, target_value)
print(f"목표 수치 {target_value}를 만드는 조합: {final_combinations}")
코드 설명:
path.append()$\rightarrow$backtrack()$\rightarrow$path.pop()과정이 바로 백트래킹의 정석입니다.- “일단 가보고, 아니면 돌아와서 다시 다른 길로 가보자!”라는 전략이죠.
current_sum > target조건문은 목표치를 넘는 순간 더 이상 계산할 필요가 없으므로 즉시 종료시키는 ‘가지치기’ 역할을 합니다.
마무리하며: 백트래킹을 정복하는 팁
백트래킹은 쉽게 말해 ‘모든 가능성을 탐색하되, 가망 없는 길은 빠르게 포기하는 것’입니다.
- 상태 공간 트리를 머릿속으로 그려보세요. (어떤 선택을 하고, 어떤 선택을 버리는지)
- 종료 조건을 명확히 하세요. (언제 성공이고, 언제 실패인가)
- 원상복구를 잊지 마세요. (
pop()이나 상태 되돌리기)
이 개념만 잡으시면 N-Queen 문제나 스도쿠 풀이 같은 어려운 알고리즘 문제들도 충분히 해결하실 수 있을 겁니다!
<hr>