[Algorithm] 백트래킹(Backtracking)과 힙(Heap)

알고리즘에서 자주 등장하는 백트래킹(Backtracking) 과 힙(Heap) 에 대해 학습했다. 특히 DFS와의 차이점, 백트래킹의 동작 방식, 힙의 구조와 특징을 중심으로 정리하였다.

---

1. Backtracking(백트래킹)

백트래킹이란?

백트래킹은 가능한 모든 경우를 탐색하되, 조건에 맞지 않는 경우는 더 이상 탐색하지 않고 이전 상태로 되돌아가는(Backtrack) 알고리즘이다.

즉,

DFS + 가지치기(Pruning) + 상태 복원

이라고 이해하면 쉽다.

---

DFS와의 차이점

DFS도 모든 노드를 탐색하지만, 백트래킹은 탐색 도중 더 이상 답이 될 가능성이 없는 경우 탐색을 중단한다.

DFS

모든 경우 탐색

Backtracking

가능성이 없는 경우

↓

즉시 return

↓

이전 상태로 복귀

↓

다른 경우 탐색

즉, 불필요한 탐색을 줄여 시간 복잡도를 크게 감소시킬 수 있다.

---

백트래킹의 기본 구조

백트래킹은 대부분 아래 형태를 따른다.

void backtracking(...) {

    // 종료 조건
    if (조건 만족) {
        return;
    }

    for (...) {

        // 상태 변경
        ...

        backtracking(...);

        // 상태 복원
        ...
    }
}

핵심은

• 종료 조건
• 상태 변경
• 재귀 호출
• 상태 복원

이 네 단계이다.

---

상태 복원(Backtracking)의 중요성

예를 들어

[1, 2, 3, 4]

에서 모든 조합을 만든다면

1

12

123

124

13

134

14

2

23

234

24

3

34

4

처럼 하나를 선택했다가

선택

↓

재귀

↓

선택 취소

↓

다음 원소 선택

순서로 진행된다.

따라서 재귀 호출 이후에는 반드시 선택했던 값을 원래대로 복원해야 한다.

예시

sum += number;

backtracking();

sum -= number;

또는

visited[i] = true;

backtracking();

visited[i] = false;

이처럼 상태를 복구하는 과정이 백트래킹의 핵심이다.

---

예시 문제

예를 들어

합이 50이 되는 경우의 수를 구하라.

라면

back(sum){

    if(sum == 50){
        answer++;
        return;
    }

    for(...){

        sum += number;

        back(sum);

        sum -= number;
    }

}

처럼 구현할 수 있다.

---

백트래킹을 사용하는 경우

대표적으로

• N-Queen
• 순열(Permutation)
• 조합(Combination)
• 부분집합(SubSet)
• 스도쿠
• DFS만으로는 탐색량이 너무 많은 경우

등에서 자주 사용된다.

---

2. Heap(힙)

힙이란?

힙은 완전 이진 트리(Complete Binary Tree) 형태를 가지는 자료구조이다.

주로

• 우선순위 큐(Priority Queue)
• 최대값
• 최소값

을 빠르게 찾기 위해 사용한다.

---

최대 힙(Max Heap)

부모 노드가 자식 노드보다 크거나 같다.

        16
      /    \
    14      10
   /  \    /  \
  8    7  9    3

항상 루트가 가장 큰 값을 가진다.

---

최소 힙(Min Heap)

부모 노드가 자식 노드보다 작거나 같다.

        1
      /   \
     3     5
    / \   / \
   8  10 7  12

항상 루트가 가장 작은 값을 가진다.

---

배열로 표현하기

힙은 배열로도 쉽게 표현할 수 있다.

Index

0 1 2 3 4 5 6 ...

Value

16 14 10 8 7 9 3 ...

부모와 자식의 인덱스 관계는 다음과 같다.

부모

(i - 1) / 2

왼쪽 자식

2 * i + 1

오른쪽 자식

2 * i + 2

이 규칙 덕분에 별도의 포인터 없이 배열만으로 트리를 표현할 수 있다.

---

Heap의 시간 복잡도

연산시간 복잡도

최댓값/최솟값 조회	O(1)
삽입	O(logN)
삭제	O(logN)
전체 탐색	O(N)

---

Java에서 Heap 사용

Java에서는 PriorityQueue를 이용하면 쉽게 구현할 수 있다.

최소 힙

PriorityQueue<Integer> pq = new PriorityQueue<>();

최대 힙

PriorityQueue<Integer> pq =
    new PriorityQueue<>(Collections.reverseOrder());

---

 

 

백트래킹은 단순히 DFS를 사용하는 것이 아니라 조건에 맞지 않는 경우를 빠르게 가지치기하고, 재귀 호출 후 상태를 복원하는 것이 핵심이라는 점, 또한 순열, 조합, 부분집합과 같이 모든 경우를 탐색해야 하는 문제에서 매우 자주 사용된다는 것을 알게 되었다.

힙은 완전 이진 트리 기반의 자료구조로, 최대값과 최소값을 효율적으로 관리할 수 있으며 PriorityQueue를 통해 Java에서 간단하게 사용할 수 있다는 점을 다시 정리할 수 있었다.