백트래킹 알고리즘은 조합 최적화 문제를 해결하기 위한 방법입니다. 이 알고리즘은 가능한 모든 후보해를 조사하고, 문제의 조건을 만족하는 해를 찾는 방법입니다. 백트래킹은 깊이 우선 탐색(depth first search)의 기본 개념을 기반으로 하고 있습니다.

백트래킹 알고리즘은 일반적으로 재귀함수로 구현됩니다. 재귀함수를 호출하고 나서, 해당 상태에서 가능한 모든 다음 상태를 생성하여 조건을 확인합니다. 조건을 만족하지 않는 경우, 다시 이전 상태로 돌아와 다른 후보해를 선택합니다. 이렇게 반복하여 조건을 만족하는 모든 해를 찾아냅니다.

백트래킹 알고리즘의 동작 과정

1. 문제의 조건을 만족하는 해를 찾기 위해 재귀함수를 호출합니다.
2. 현재 상태에서 가능한 모든 다음 상태를 생성합니다.
3. 생성한 다음 상태에 대해 조건을 확인합니다.
4. 조건을 만족하면, 해당 상태를 유망한 상태로 판단하고 재귀함수를 호출합니다.
5. 조건을 만족하지 않으면, 해당 상태를 폐기하고 이전 상태로 돌아갑니다.
6. 모든 후보해를 조사한 후, 문제의 조건을 만족하는 해를 찾습니다.

백트래킹 알고리즘 예제

이제 백트래킹 알고리즘을 예제를 통해 이해해보겠습니다. 다음은 1부터 N까지의 자연수 중에서 중복 없이 M개를 선택하는 문제입니다.

def backtrack(nums, picked, to_pick):
    # 기저 사례: M개를 모두 선택한 경우, 선택한 수를 출력합니다.
    if to_pick == 0:
        print(picked)
        return
    
    # 다음 선택할 수의 범위를 설정합니다.
    if len(picked) == 0:
        next_num = 1
    else:
        next_num = picked[-1] + 1
    
    # 다음 선택할 수를 하나씩 선택하고 재귀함수를 호출합니다.
    for num in range(next_num, nums + 1):
        picked.append(num)
        backtrack(nums, picked, to_pick - 1)
        picked.pop()

N = 5  # 1부터 N까지의 자연수
M = 3  # 선택할 수의 개수
picked = []
backtrack(N, picked, M)

위 예제는 1부터 5까지의 자연수 중에서 중복 없이 3개를 선택하는 문제를 해결하는 백트래킹 알고리즘입니다.

이 알고리즘은 모든 가능한 경우의 수를 조사하면서 문제의 조건을 만족하는 해를 찾아냅니다.

참고 자료

• 백트래킹 알고리즘 - 위키백과
• 백트래킹 알고리즘 - 프로그래머스