99클럽 코테 스터디 14일차 TIL - Brute Force같은 DFS

문제 - 타겟 넘버 문제링크

문제 설명

이렇게 numbers와 target이 입력으로 주어지면, numbers의 모든 숫자들을 각각 더하든지 빼든지 해서 target값을 만들어내는 경우의 수를 구하는 문제입니다.

 

첫번째 예시 입력에 대해 다음과 같은 경우의 수들이 있습니다.

 

이런식으로 각 숫자 앞에 +를 붙일건지 -를 붙일건지 선택해서 다 계산한 결과가 target이면 됩니다.

 

풀이 과정

각 숫자에는 부호가 할당되어야 합니다. 그리고 각 숫자마다 붙는 부호는 다른 숫자들과 독립적입니다. 이러면 각 숫자마다 +-의 두가지 경우가 있습니다. 모든 숫자에 대해 +-를 붙이는 경우의 수를 구하는 데 좋은 알고리즘은 DFS가 있습니다.

"""
    각 숫자에 대해 -, + 할당
    dfs(order, val)
"""
def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    def dfs(order, val):
        nonlocal answer
        if order == n:
            if val == target:
                answer += 1
            return
        
        dfs(order + 1, val + numbers[order])
        dfs(order + 1, val - numbers[order])
    
    dfs(0, 0)
    return answer

이 경우에는 입력에 따라 가지수가 변하는 게 아니라 +- 총 두가지로 일정하기 때문에 DFS 함수 내부에서 명시적으로 두 번의 DFS 함수 호출을 연달아 진행합니다. 하지만 일반화하면 보통 가지수만큼 for문을 돌면서 DFS를 호출합니다.

한번의 DFS 호출은 두 번의 DFS 호출을 유발하므로, 호출 그림을 그려보면 완전이진트리와 같은 모양일 것입니다. 깊이 우선 탐색이기 때문에 모두 +만 선택된 상태일 때가 가장 먼저 처리되고 이후 마지막 숫자만 -인 상태가 처리되고, 이런식으로 모두 -인 상태인 경우까지 처리될 것입니다.

 

총평

제목을 Brute Force 같은 DFS로 지은 이유는 DFS도 결국 Brute Force처럼 모든 경우를 확인하기 때문입니다.

다만 DFS는 깊이 우선탐색이라는 점이 다른 것 같습니다.

결국, DFS도 모든 경우를 확인하는 방법중의 하나이고, 특별히 알고리즘 면에서 시간이 더 빠르다거나 하진 않다는 교훈을 얻었습니다.

deque을 사용해서 BFS로도 풀어본 결과 DFS보다 느렸습니다. 그 이유를 추측하건데 CPython 내의 deque 관련 메서드 자체의 오버헤드 때문이지 않을까 생각합니다. CPython deque 구현 코드