9 / 16강

가능성 없는 길에서 돌아오기

모든 조합을 만든 뒤 검사하면 이미 틀린 선택을 한 뒤에도 계속 시간을 씁니다. 백트래킹은 답의 일부를 만들다가 조건을 어기면 바로 그 자리에서 돌아옵니다.

양수의 합을 맞춰 봅시다

서로 다른 양수 [2, 4, 5] 중 일부를 한 번씩 골라 합 6을 만들겠습니다. 고르거나 건너뛰는 두 갈래로 나눕니다. 합이 6을 넘으면 남은 양수를 더해도 줄어들지 않으므로 멈출 수 있습니다.

numbers, target = [2, 4, 5], 6
answers = []

def search(index, total, path):
    if total == target:
        answers.append(path.copy())
        return
    if total > target or index == len(numbers):
        return
    path.append(numbers[index])
    search(index + 1, total + numbers[index], path)
    path.pop()
    search(index + 1, total, path)

search(0, 0, [])
print(answers)

출력은 [[2, 4]]입니다. append로 선택을 기록하고, 그 갈래를 모두 본 뒤 pop으로 되돌립니다. 그래야 ‘고르지 않는 갈래’가 앞의 선택에 오염되지 않습니다. 정답을 저장할 때 copy()를 쓰는 이유도 이후 변경의 영향을 피하기 위해서입니다.

가지치기의 근거가 필요합니다

위 코드는 양수라는 조건을 사용했습니다. 음수가 있다면 합이 목표를 넘었어도 나중에 다시 줄어들 수 있습니다. 그때 같은 가지치기를 쓰면 정답을 놓칩니다.

퀸 배치 문제에서는 이미 놓은 퀸과 같은 열이나 대각선이면 그 후보를 버립니다. 탐색 순서를 정하는 DFS와, 조건을 이용해 후보를 버리는 백트래킹은 역할이 다릅니다. DFS 방식으로 백트래킹을 구현할 수 있습니다.

가지치기는 방문 수를 줄여도 최악의 경우 모든 부분집합에 가까이 접근할 수 있습니다. 탐색 노드 수는 O(2^n)이고, 답을 복사하고 저장하는 비용은 별도입니다. 재귀 경로 자체의 공간은 O(n)입니다.

확인 문제

입력에 -3이 포함될 수 있는데 현재 합이 8, 목표가 5라면 바로 돌아가도 될까요?