[코드트리] 백트래킹 알고리즘 쉽게 이해하기

1. 백트래킹이란?

백트래킹(Backtracking)은 모든 경우를 탐색하되, 불필요한 경우는 중간에 제거하는 알고리즘 기법이다.

• 가능한 모든 경우를 탐색(완전탐색)
• 조건을 만족하지 않으면 즉시 중단(가지치기)

이 과정을 통해 탐색 시간을 크게 줄일 수 있다.

 

2. 문제 소개: 가능한 수열 중 최솟값 구하기

👉 문제 링크
https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-find-min-of-possible-series/description

길이가 N인 수열을 {4, 5, 6}으로 구성할 때,
인접한 두 부분 수열이 동일하면 안 된다.

예를 들어

• 4545 → "45" + "45" (반복 발생)
• 4646 → "46" + "46"

이런 경우는 불가능한 수열이다.

3. 문제 접근 방식

이 문제는 전형적인 백트래킹 문제다.

Step 1. 수열을 하나씩 만들어간다 (DFS)

• depth를 증가시키면서 숫자를 하나씩 채운다.

Step 2. 매 순간 "유효한지 검사"

• 인접 부분 수열이 같은지 체크
• 같으면 더 탐색할 필요 없음 -> 가지치기

Step 3. 가장 먼저 완성된 수열이 정답

• 4 ->  5  ->  6 순서로 탐색하면
• 자동으로 사전순 최소 보장

---

4. 내가 구현한 코드 

전체 구조

static void dfs(int depth) {
    if (flag) return;

    if (!isPossible(depth)) return;

    if (depth == N) {
        결과 저장
        return;
    }

    for (int num = 4; num <= 6; num++) {
        arr[depth] = num;
        dfs(depth + 1);
    }
}

---

사전순 최소 보장

for (int num = 4; num <= 6; num++)

이 순서로 탐색하면 가장 먼저 완성되는 수열이 곧 정답이다.

그래서 flag를 사용해 한 번 찾으면 즉시 종료한다.

가지치기

이 문제의 핵심은 여기다.

for (int size = 1; size <= depth / 2; size++) {
    boolean same = true;

    for (int i = 0; i < size; i++) {
        if (arr[depth - 1 - i] != arr[depth - 1 - size - i]) {
            same = false;
            break;
        }
    }

    if (same) return false;
}

현재까지 만든 수열의 끝부분에서 길이가 size인 두 부분 수열을 비교한다 !

5. 자주 하는 실수

가지치기 조건을 잘못 설정하면 정답이 되는 경우까지 제거하거나, 불필요한 탐색을 줄이지 못하는 문제가 발생한다. 따라서 조건을 구현할 때는 문제의 제한사항을 정확히 반영하고, 부분 수열 비교와 같은 핵심 로직이 올바르게 동작하는지 반드시 확인해야 한다.

이 문제를 통해 백트래킹의 핵심은 단순 DFS가 아니라 가지치기 조건 설계라는 점을 명확히 이해할 수 있었다. 특히 부분 수열 비교를 통해 탐색을 조기에 중단하는 방식이 시간 복잡도에 큰 영향을 준다는 점이 인상적이었다.

또한 사전순 최소를 만족시키기 위해 탐색 순서를 설계하는 부분도 중요한 포인트였다. 단순히 모든 경우를 찾는 것이 아니라, "가장 먼저 찾은 정답이 최적"이 되도록 설계하는 것이 백트래킹 문제에서 자주 활용된다는 것을 알게 되었다.

앞으로는 DFS를 사용할 때 단순 구현에 그치지 않고, 어떤 조건으로 탐색을 줄일 수 있을지를 먼저 고민하는 방식으로 접근할 계획이다.