백트래킹

백트래킹(Backtracking)은 문제를 해결하는 과정에서 가능한 모든 경우를 시도하는 방법입니다. 쉽게 말해, 여러 선택지를 하나씩 시도해보면서 조건을 만족하는 해를 찾는 과정입니다. 만약 어떤 선택이 조건을 어긴다면, 그 선택을 취소하고 다른 선택을 시도하는 방식으로 진행됩니다.

백트래킹의 기본 개념

상태(State): 현재 선택한 값이나 설정.
목표(Goal): 문제의 해결책.
유효성 검사: 현재 상태가 목표를 만족하는지 확인.
재귀 호출: 다음 상태로 넘어가는 과정.
되돌아가기(Backtrack): 더 이상 진행할 수 없는 경우 이전 상태로 돌아가는 과정.
예시: 부분집합 구하기
부분집합 문제는 주어진 집합의 모든 부분집합을 구하는 문제입니다. 예를 들어, 집합 {1, 2, 3}의 모든 부분집합을 찾아보겠습니다.

알고리즘 설명

현재 부분집합을 기록: 부분집합을 저장할 리스트를 만듭니다.
재귀적으로 숫자를 포함하거나 포함하지 않기: 각 숫자에 대해 두 가지 선택을 합니다.
기저 사례(Base Case): 모든 숫자를 처리했을 때 현재 부분집합을 결과에 추가합니다.

Java 코드 예시: 부분집합 구하기

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> subsets = generateSubsets(nums);
        System.out.println(subsets);
    }

    public static List<List<Integer>> generateSubsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, result);
        return result;
    }

    private static void backtrack(int start, List<Integer> path, int[] nums, List<List<Integer>> result) {
        // 현재 부분집합을 결과에 추가
        result.add(new ArrayList<>(path));

        // 숫자를 하나씩 포함하거나 포함하지 않기
        for (int i = start; i < nums.length; i++) {
            // 숫자 포함
            path.add(nums[i]);
            backtrack(i + 1, path, nums, result);
            // 숫자 제외 (되돌아가기)
            path.remove(path.size() - 1);
        }
    }
}

start: 현재 선택을 시작할 인덱스입니다.
path: 현재까지 선택된 숫자를 저장하는 리스트입니다.
result: 모든 부분집합을 저장하는 리스트입니다.
result.add(new ArrayList<>(path));: 현재 부분집합을 결과 리스트에 추가합니다.
for 루프를 통해 각 숫자를 포함하는 경우를 재귀적으로 처리합니다. 숫자를 포함한 후, 다시 호출하여 다음 숫자를 선택합니다.
path.remove(path.size() - 1);: 숫자를 제외하고 이전 상태로 되돌아갑니다.

결과

위 코드를 실행하면, 다음과 같은 출력이 생성됩니다:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

이 결과는 모든 부분집합을 나열한 것으로, 빈 집합부터 시작하여 각 숫자가 포함된 다양한 조합을 보여줍니다.

Tip

• 백트래킹 문제는 N이 작음
• 재귀함수를 사용할 때 종료시점 잊지 말기
• 코딩테스트 중 가장 중요하고 어려운 부분 중 하나이며 재귀함수를 잘 쓰는 연습이 많이 필요함