개요
아래의 내용은 java_grammer 레파지토리 C02MethodClass 디렉터리에 저장되어있는 내용을 정리함
대표적으로 백트래킹(Backtracking), DFS, 분할 정복(Divide & Conquer) 알고리즘이 모두 재귀 구조 위에서 동작한다
- 백트래킹 문제 모음: 백준 알고리즘 분류 링크
- DFS 문제 모음: DFS 알고리즘 링크
- 분할정복 문제 모음: Divide & Conquer 링크
백트래킹이란
- 완전탐색에서 불필요한 가지를 잘라내며(optimize) 탐색하는 방식임.
- 재귀 구조를 이용해 모든 경우의 수를 탐색하면서 제약조건을 만족하는 경우만 기록함.
- 조합, 순열, N과 M(백준 15649), 로또(6603) 같은 문제 전형적임.
기본 패턴 – 재귀로 for문 제어
for문의 반복 횟수가 정적이라면, 재귀로 깊이를 제어해야 함.
아래 예제는 일반적인 중첩 for문을 재귀로 바꾼 구조임.
public static void recurForLoop(int nowDepth, int targetDepth) {
if (nowDepth == targetDepth) {
return; // 끝자리에서 종결
}
for (int i = 0; i < 3; i++) {
recurForLoop(nowDepth + 1, targetDepth);
}
}실행 구조 (targetDepth=3):
for(i=0;i<3;i++){
for(j=0;j<3;j++){
for(k=0;k<3;k++){
...
}
}
}즉, recurForLoop(0,3)은 3중 for문처럼 동작함.
스택이 깊이가 되어 for 반복의 중첩 구조를 대체하는 셈임.
조합 (Combination) – 순서 상관 없음
예시: 1,2,3,4에서 2개 뽑기.
결과: [1,2], [1,3], [1,4], [2,3], [2,4], [3,4]
문제점 있는 for문 코드
List<List<Integer>> doubleList = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < myList.size(); i++) {
temp.add(myList.get(i));
for (int j = i + 1; j < myList.size(); j++) {
temp.add(myList.get(j));
doubleList.add(temp); // 같은 리스트 주소 공유 -> 잘못된 결과
}
}이 코드의 문제는 temp의 주소가 계속 같음.
즉, 모든 add() 결과가 누적된 동일 리스트가 반복해서 들어감.
개선 코드
List<List<Integer>> doubleList1 = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < myList.size(); i++) {
temp.add(myList.get(i));
for (int j = i + 1; j < myList.size(); j++) {
temp.add(myList.get(j));
doubleList1.add(new ArrayList<>(temp)); // 복제
temp.remove(temp.size() - 1); // j루프 끝나면 제거
}
temp.remove(temp.size() - 1); // i루프 끝나면 제거
}
System.out.println(doubleList1);결과: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
재귀로 조합 만들기
public static void recurForComb(List<Integer> temp, int start, List<Integer> myList, int n, List<List<Integer>> doubleList) {
if (temp.size() == n) {
doubleList.add(new ArrayList<>(temp));
return;
}
for (int i = start; i < myList.size(); i++) {
temp.add(myList.get(i));
recurForComb(temp, i + 1, myList, n, doubleList);
temp.remove(temp.size() - 1);
}
}호출 예시:
recurForComb(new ArrayList<>(), 0, myList, 2, combDoubleList);핵심
start인덱스로 다음 루프가 이전 인덱스를 다시 방문하지 않도록 관리temp는 현재 조합 상태를 저장- 한 번 내려갈 때마다 하나씩 쌓고, 복귀 시 제거
출력 결과:
[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]순열 (Permutation) – 순서 고려함
예시: 1,2,3,4에서 2자리 순열
결과: [1,2], [1,3], [1,4], [2,1], [2,3], [2,4], ...]
재귀 없이 for문으로 구현
List<List<Integer>> permuDoubleList1 = new ArrayList<>();
List<Integer> permuTemp = new ArrayList<>();
boolean[] visited = new boolean[myList.size()];
for (int i = 0; i < myList.size(); i++) {
permuTemp.add(myList.get(i));
visited[i] = true;
for (int j = 0; j < myList.size(); j++) {
if (visited[j]) continue;
permuTemp.add(myList.get(j));
visited[j] = true;
permuDoubleList1.add(new ArrayList<>(permuTemp));
permuTemp.remove(permuTemp.size() - 1);
visited[j] = false;
}
permuTemp.remove(permuTemp.size() - 1);
visited[i] = false;
}
System.out.println(permuDoubleList1);이중 for문으로 순열 2자리까진 가능하지만, 자리 수 늘어나면 복잡도 급상승함.
이걸 재귀로 바꾸면 훨씬 깔끔함.
재귀로 순열 만들기
public static void recurForPermu(boolean[] visited, List<Integer> temp, List<Integer> myList, int n, List<List<Integer>> doubleList) {
if (temp.size() == n) {
doubleList.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < myList.size(); i++) {
if (visited[i]) continue;
temp.add(myList.get(i));
visited[i] = true;
recurForPermu(visited, temp, myList, n, doubleList);
temp.remove(temp.size() - 1);
visited[i] = false;
}
}호출 예시:
recurForPermu(new boolean[myList.size()], new ArrayList<>(), myList, 2, permuDoubleList);작동 구조
1. 방문한 원소 표시 (visited)
2. 현재 값 추가하고 재귀 호출
3. 복귀 시 backtrack (temp와 visited 되돌림)
결과:
[[1,2], [1,3], [1,4], [2,1], [2,3], [2,4], [3,1], [3,2], [3,4], [4,1], [4,2], [4,3]]핵심 정리
- for문 → 재귀로 치환할 때, 루프 깊이를 매개변수(nowDepth, targetDepth)로 관리
- 조합: 방문한 인덱스 이후만 탐색 (
start=i+1) - 순열: 방문 배열로 중복 방지 (
visited[i]) - 백트래킹 핵심:
- 내려가기 전(add) → 호출 → 복귀 시(remove)
- 상태 복구 필수 (그래야 다른 조합 탐색 가능)
참고 문제
- 백준 15649: N과 M (순열)
- 백준 6603: 로또 (조합)
Eazy하게