(코테) 백트레킹에서 순열, 조합 차이 그리고 해결 전략 ***

✅ 백트래킹 (Backtracking) 정의

백트래킹은 해를 찾는 도중에
이 경로로는 정답이 나올 수 없다는 판단이 들면,
되돌아가서 다른 경로를 시도하는 방식의 탐색 알고리즘입니다.

 

즉,  가능성이 없는 분기(branch)는 더 이상 탐색하지 않고 "되돌아가서(back)" 다른 선택지를 탐색한다는 의미입니다.

---

📦 쉽게 말하면

• 완전탐색을 하긴 하지만,
• 쓸데없는 탐색을 줄이기 위해
• 조건에 맞지 않으면 재귀를 끝내고 뒤로 돌아감

---

🔁 백트래킹의 핵심 요소

요소	설명
재귀(DFS)	모든 선택지를 탐색함
조건 체크	현재 경로가 유망하지 않으면 중단
원상복구	재귀 호출 후에는 상태를 되돌림 (백트래킹)
가지치기	더 이상 유효하지 않으면 탐색 종료 (Pruning)

 

---

🎯 언제 쓰는가?

상황	설명
모든 경우를 탐색하되, 조건이 있음	예: 합이 특정 값, 오름차순, 중복 없음 등
정해진 개수의 원소를 뽑아야 함	예: 로또 6개, 자리 배치 3개 등
중간에 불필요한 탐색을 생략하고 싶을 때	예: 부분 수열 중 합이 넘어가면 끝냄

 

---

📘 대표 문제 유형

 

문제 유형	백트래킹 활용
순열 / 조합	자리마다 넣어보면서 탐색
부분수열 / 부분집합	포함 / 비포함을 선택하며 DFS
N-Queen	놓을 수 없는 위치면 탐색 중단
숫자 맞추기	조건 넘으면 바로 종료

 

✅ 백트래킹 문제는 순열 / 조합 유형이 나뉩니다

 

유형	특징	예시
조합	순서 ❌ / 중복 ❌	로또, 팀 짜기, 부분집합
순열	순서 ✅ / 중복 ❌	숫자 자리 바꾸기, 비밀번호 만들기
중복조합 / 중복순열	조건 따라 다름	사탕 여러 개 선택, 중복 문자 순열

 

---

🎯 예시로 감 잡기

🔵 조합 (Combination)

• 49개 중에 6개를 선택 (순서 중요 X)
• 예: [3, 8, 12, 21, 33, 45]
• [8, 3, 12, 45, 21, 33] → 같은 조합

로또는 대표적인 조합 문제

---

🔴 순열 (Permutation)

• 예를 들어 1~6까지 숫자를 가지고 만들 수 있는 모든 순열:

1 2 3 4 5 6  
1 2 3 4 6 5  
...
6 5 4 3 2 1

 

총 6! = 720가지

자리별로 다른 값이 들어가는 모든 경우 = 순열

---

✅ 백트래킹에서 두 유형 차이 정리

항목	조합	순열
DFS 호출	dfs(startIndex, depth)	dfs(depth)
visited 배열	❌ 보통 안 씀	✅ 써야 중복 방지
예시 문제	백준 6603 (로또), 1182 (부분수열 합)	백준 10974 (모든 순열), N과 M (1)
순서 고려?	❌ (정렬 필요)	✅

 

---

📌 기억 꿀팁

질문	답
"순서 중요해?"	✅ → 순열
"몇 개만 뽑고 순서 상관없어?"	✅ → 조합
"같은 숫자 반복 가능?"	✅ → 중복조합 / 중복순열 문제로 확장