
백트래킹(Backtracking) 알고리즘이란 ❓
백트래킹(Backtracking)은 문제 해결을 위한 탐색 기법 중 하나로, 재귀적 탐색과 되돌리기(backtrack)를 활용하여 최적의 해를 찾는 방법입니다.
많은 최적화 문제, 조합 문제, 순열 문제 등에서 널리 사용되며, 가능한 해를 하나씩 시도하면서 해가 될 것 같지 않으면 더 이상 탐색하지 않고 되돌아갑니다.
여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 합니다.
백트래킹(Backtracking)의 기본 개념
백트래킹은 탐색 트리에서 깊이 우선 탐색(DFS) 방식으로 진행되며, 각 노드에서 가능한 모든 선택을 해본 후, 그 선택이 잘못된 경로일 경우에는 다시 되돌아가서 다른 선택을 시도하는 방식입니다.
이러한 방식은 문제의 해결 공간이 매우 크고, 모든 가능한 해를 확인해야 할 때 매우 유용합니다.
결정 공간 (Decision Space)

백트래킹에서 중요한 개념 중 하나는 결정 공간(Decision Space)입니다.
이는 문제 해결을 위해 선택할 수 있는 모든 가능한 경로 또는 선택지들의 집합을 말합니다. 이 결정 공간을 Decision Tree라고도 부르며, 트리 형태로 그릴 수 있습니다.
백트래킹 알고리즘은 이 결정 트리를 탐색하면서 유망한 경로만을 따라가고, 유망하지 않다고 판단되면 더 이상 진행하지 않고 되돌아가는 방식으로 최적의 해를 찾습니다.
결정 공간을 어떻게 구성하느냐에 따라 백트래킹 알고리즘의 성능과 효율성이 달라지므로, 이 공간을 효율적으로 탐색하는 전략이 중요합니다.
백트래킹(Backtracking)의 기본 흐름
1. 유망성 검사(Promising Check)
- 현재 경로가 해결책이 될 수 있는지 판단합니다.
- 경로가 유망하지 않으면 (해가 될 것 같지 않으면)그
경로는 더 이상 탐색하지 않습니다.
2. 재귀적 탐색 (Recursive Exploration)
- 현재 상태에서 선택할 수 있는 모든 옵션을 하나씩 시도합니다.
- 하나의 선택을 했을 때 그 선택이 유망하다면, 다음 단계로 재귀적으로 진행합니다.
3. 백트래킹 (Backtracking)
- 어떤 선택이 잘못된 경로로 이어졌다면, 그 경로를 되돌려서 다른 선택을 시도합니다.
백트래킹(Backtracking)의 문제
조합 문제
1, 2, 3, 4, 5에서 2개의 숫자를 뽑아 합이 6이 되는 조합을 찾는 문제
public class CombinationExample {
static int[] nums = {1, 2, 3, 4, 5};
static int target = 6;
public static void main(String[] args) {
findCombinations(0, 0, new StringBuilder());
}
public static void findCombinations(int start, int sum, StringBuilder path) {
if (sum == target) {
System.out.println(path.toString());
return;
}
for (int i = start; i < nums.length; i++) {
if (sum + nums[i] > target) continue; // 초과하면 더 이상 탐색하지 않음
path.append(nums[i]).append(" ");
findCombinations(i + 1, sum + nums[i], path); // 재귀 호출
path.delete(path.length() - 2, path.length()); // 상태 복원
}
}
}
이 문제는 주어진 숫자들에서 합이 목표값인 6이 되는 조합을 찾아야 하는 문제로, 결정 공간에서 가능한 모든 선택을 시도하고, 그 중 잘못된 선택은 되돌려 가며 해결합니다.
백준 - N 과 M (1)
[백준, 15649번] N과 M(1) (백트래킹, Java)
문제설명입력 & 출력나의 풀이이번 "백준 - N과 M (1)" 문제는 1부터 N까지의 자연수 중에서 길이 M인 순열을 모두 구하는 문제입니다. 문제 접근 방식1. 순열 생성길이 M의 순열을 구성해야 하므로
pixx.tistory.com
백트래킹(Backtracking)의 장점과 단점
장점
- 효율적인 탐색
- 백트래킹은 불필요한 탐색을 중지시키고, 해를 찾기 위한 공간을 효과적으로 줄여줍니다. 결정 공간을 잘 구성하면 탐색 시간을 크게 단축할 수 있습니다.
- 최적화 문제 해결 가능
- 최적화 문제에서 유망한 경로만 탐색하므로 최적해를 빠르게 찾을 수 있습니다.
- 유연성
- 문제의 규칙에 맞춰 깊이 우선 탐색과 상태 복원을 통해 다양한 문제를 해결할 수 있습니다.
단점
- 시간 복잡도
- 최악의 경우 탐색 공간이 매우 커질 수 있어, 최악의 시간 복잡도는 지수적일 수 있습니다. 따라서 탐색 공간을 잘 축소할 수 있는 문제가 아니면 비효율적일 수 있습니다.
- 메모리 사용
- 재귀적 호출을 사용하기 때문에 많은 양의 메모리를 사용할 수 있습니다.
백트래킹(Backtracking) Tip
1. 입력 크기를 먼저 확인하라
- 백트래킹은 탐색 공간이 크면 비효율적일 수 있으므로, N이 작거나 탐색 공간이 제한적인 경우에 적합합니다.
- N이 10~15 이하인 경우 백트래킹으로 해결 가능한 경우가 많습니다.
2. 가지치기(Pruning)를 최대한 활용하라
- 불필요한 탐색을 줄이는 가지치기는 백트래킹의 핵심입니다.
유망하지 않은 경로는 즉시 탐색을 중단합니다.- 문제의 제약 조건을 빠르게 확인하고, 조건을 만족하지 않으면 탐색을 종료합니다.
3. 재귀 호출 전에 상태를 변경하고, 호출 후에는 복원하라
- 백트래킹은 상태를 변경하며 진행되기 때문에, 재귀 호출 후 상태 복원이 필수입니다.
- 호출 전 visited 배열이나 path를 변경하고, 호출이 끝나면 이전 상태로 되돌립니다.
- DFS를 사용하는 경우 visited[i]를 true로 설정하고, 재귀 호출 후 false로 복원합니다.
'Algorithm' 카테고리의 다른 글
[Algorithm] LIS : 가장 긴 증가하는 부분 수열 알고리즘 알아보기 (1) | 2024.12.18 |
---|---|
[Algorithm] 파스칼의 삼각형 알고리즘 구현하기 (Java) (1) | 2024.12.03 |
[Algorithm] 효율적인 소수 판별: 기본 방법부터 에라토스테네스의 체까지 (0) | 2024.11.26 |
[Algorithm] KMP(Knuth-Morris-Pratt) 알고리즘이란 무엇일까❓ (문자열 비교) (2) | 2024.11.14 |
[Algorithm] 이진 탐색 알고리즘 : 데이터 정렬과 검색 최적화 (Binary Search, Java) (0) | 2024.07.09 |

백트래킹(Backtracking) 알고리즘이란 ❓
백트래킹(Backtracking)은 문제 해결을 위한 탐색 기법 중 하나로, 재귀적 탐색과 되돌리기(backtrack)를 활용하여 최적의 해를 찾는 방법입니다.
많은 최적화 문제, 조합 문제, 순열 문제 등에서 널리 사용되며, 가능한 해를 하나씩 시도하면서 해가 될 것 같지 않으면 더 이상 탐색하지 않고 되돌아갑니다.
여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 합니다.
백트래킹(Backtracking)의 기본 개념
백트래킹은 탐색 트리에서 깊이 우선 탐색(DFS) 방식으로 진행되며, 각 노드에서 가능한 모든 선택을 해본 후, 그 선택이 잘못된 경로일 경우에는 다시 되돌아가서 다른 선택을 시도하는 방식입니다.
이러한 방식은 문제의 해결 공간이 매우 크고, 모든 가능한 해를 확인해야 할 때 매우 유용합니다.
결정 공간 (Decision Space)

백트래킹에서 중요한 개념 중 하나는 결정 공간(Decision Space)입니다.
이는 문제 해결을 위해 선택할 수 있는 모든 가능한 경로 또는 선택지들의 집합을 말합니다. 이 결정 공간을 Decision Tree라고도 부르며, 트리 형태로 그릴 수 있습니다.
백트래킹 알고리즘은 이 결정 트리를 탐색하면서 유망한 경로만을 따라가고, 유망하지 않다고 판단되면 더 이상 진행하지 않고 되돌아가는 방식으로 최적의 해를 찾습니다.
결정 공간을 어떻게 구성하느냐에 따라 백트래킹 알고리즘의 성능과 효율성이 달라지므로, 이 공간을 효율적으로 탐색하는 전략이 중요합니다.
백트래킹(Backtracking)의 기본 흐름
1. 유망성 검사(Promising Check)
- 현재 경로가 해결책이 될 수 있는지 판단합니다.
- 경로가 유망하지 않으면 (해가 될 것 같지 않으면)그
경로는 더 이상 탐색하지 않습니다.
2. 재귀적 탐색 (Recursive Exploration)
- 현재 상태에서 선택할 수 있는 모든 옵션을 하나씩 시도합니다.
- 하나의 선택을 했을 때 그 선택이 유망하다면, 다음 단계로 재귀적으로 진행합니다.
3. 백트래킹 (Backtracking)
- 어떤 선택이 잘못된 경로로 이어졌다면, 그 경로를 되돌려서 다른 선택을 시도합니다.
백트래킹(Backtracking)의 문제
조합 문제
1, 2, 3, 4, 5에서 2개의 숫자를 뽑아 합이 6이 되는 조합을 찾는 문제
public class CombinationExample {
static int[] nums = {1, 2, 3, 4, 5};
static int target = 6;
public static void main(String[] args) {
findCombinations(0, 0, new StringBuilder());
}
public static void findCombinations(int start, int sum, StringBuilder path) {
if (sum == target) {
System.out.println(path.toString());
return;
}
for (int i = start; i < nums.length; i++) {
if (sum + nums[i] > target) continue; // 초과하면 더 이상 탐색하지 않음
path.append(nums[i]).append(" ");
findCombinations(i + 1, sum + nums[i], path); // 재귀 호출
path.delete(path.length() - 2, path.length()); // 상태 복원
}
}
}
이 문제는 주어진 숫자들에서 합이 목표값인 6이 되는 조합을 찾아야 하는 문제로, 결정 공간에서 가능한 모든 선택을 시도하고, 그 중 잘못된 선택은 되돌려 가며 해결합니다.
백준 - N 과 M (1)
[백준, 15649번] N과 M(1) (백트래킹, Java)
문제설명입력 & 출력나의 풀이이번 "백준 - N과 M (1)" 문제는 1부터 N까지의 자연수 중에서 길이 M인 순열을 모두 구하는 문제입니다. 문제 접근 방식1. 순열 생성길이 M의 순열을 구성해야 하므로
pixx.tistory.com
백트래킹(Backtracking)의 장점과 단점
장점
- 효율적인 탐색
- 백트래킹은 불필요한 탐색을 중지시키고, 해를 찾기 위한 공간을 효과적으로 줄여줍니다. 결정 공간을 잘 구성하면 탐색 시간을 크게 단축할 수 있습니다.
- 최적화 문제 해결 가능
- 최적화 문제에서 유망한 경로만 탐색하므로 최적해를 빠르게 찾을 수 있습니다.
- 유연성
- 문제의 규칙에 맞춰 깊이 우선 탐색과 상태 복원을 통해 다양한 문제를 해결할 수 있습니다.
단점
- 시간 복잡도
- 최악의 경우 탐색 공간이 매우 커질 수 있어, 최악의 시간 복잡도는 지수적일 수 있습니다. 따라서 탐색 공간을 잘 축소할 수 있는 문제가 아니면 비효율적일 수 있습니다.
- 메모리 사용
- 재귀적 호출을 사용하기 때문에 많은 양의 메모리를 사용할 수 있습니다.
백트래킹(Backtracking) Tip
1. 입력 크기를 먼저 확인하라
- 백트래킹은 탐색 공간이 크면 비효율적일 수 있으므로, N이 작거나 탐색 공간이 제한적인 경우에 적합합니다.
- N이 10~15 이하인 경우 백트래킹으로 해결 가능한 경우가 많습니다.
2. 가지치기(Pruning)를 최대한 활용하라
- 불필요한 탐색을 줄이는 가지치기는 백트래킹의 핵심입니다.
유망하지 않은 경로는 즉시 탐색을 중단합니다.- 문제의 제약 조건을 빠르게 확인하고, 조건을 만족하지 않으면 탐색을 종료합니다.
3. 재귀 호출 전에 상태를 변경하고, 호출 후에는 복원하라
- 백트래킹은 상태를 변경하며 진행되기 때문에, 재귀 호출 후 상태 복원이 필수입니다.
- 호출 전 visited 배열이나 path를 변경하고, 호출이 끝나면 이전 상태로 되돌립니다.
- DFS를 사용하는 경우 visited[i]를 true로 설정하고, 재귀 호출 후 false로 복원합니다.
'Algorithm' 카테고리의 다른 글
[Algorithm] LIS : 가장 긴 증가하는 부분 수열 알고리즘 알아보기 (1) | 2024.12.18 |
---|---|
[Algorithm] 파스칼의 삼각형 알고리즘 구현하기 (Java) (1) | 2024.12.03 |
[Algorithm] 효율적인 소수 판별: 기본 방법부터 에라토스테네스의 체까지 (0) | 2024.11.26 |
[Algorithm] KMP(Knuth-Morris-Pratt) 알고리즘이란 무엇일까❓ (문자열 비교) (2) | 2024.11.14 |
[Algorithm] 이진 탐색 알고리즘 : 데이터 정렬과 검색 최적화 (Binary Search, Java) (0) | 2024.07.09 |