[dfs] dfs(recursion) vs permutations : 시간복잡도의 관점에서 무엇을 선택 할 것인가

https://school.programmers.co.kr/learn/courses/30/lessons/43165

 

나의 첫 코드는 다음과 같다.

from itertools import permutations

def solution(numbers, target):
    length = len(numbers)
    operators = ["+", "-"]*length
    cases =  set(permutations(operators, length))
    print(len(cases))
    get_target = 0
    for case in cases:
        print(case)
        operating = 0
        for i in range(length):
            if case[i] == "+":
                operating += numbers[i]
            elif case[i] == "-":
                operating += -numbers[i]
        if operating == target:
            get_target += 1

    return get_target

permutations 함수로 numbers에 해당하는 모든 operators 순서쌍을 찾고, ex) [1, 2]라면 {("+", "+"), ("+", "-"), ("-", "+"), ("-", "-")}

for문으로 모든 순서쌍에 대해 숫자연산 해서 target과 같으면 count를 하는 코드인데, (get_target)

 

시간초과

간단한 테스트케이스에서는 작동하였으나, 시간초과가 발생했다.

 

사실 시간초과를 예상하긴했다. 

https://leerosepark.tistory.com/21

[완전탐색] 문제에서 '완전탐색일 수 밖에 없는 이유' 찾기

이전의 공부를 통해, permutations를 효율적으로 쓸수 있는 element의 수는 7~8인데, 이 문제의 경우 maximum이 20이다.

추후에 연산하는 iteration도 사용해야되는데, permutations에서만 20! 의 연산을 하는 것은 불가능하다.

 

그렇기때문에 순서쌍을 찾는데에 있어서, permutations( O(n!) ) 대신에 재귀를 이용한 dfs ( O(2^n) )을 사용하기로 했다.

 

실제로 maximum numbers가 20일때, O(2^20) = (2^10 )^ 2 ~= 10e3 ^ 2 = 10e6으로 시간복잡도가 훨씬 줄어든다.

 

게다가 아래 코드를 짜다보니, 연산의경우계산과 연산이 한 번에 가능하게 되어, 전체 solution의 시간복잡도는 결국 10e6이다.

 

def recur(i, operating, numbers, target):
    if i == len(numbers):
        return 1 if operating == target else 0
    return recur(i + 1, operating + numbers[i], numbers, target) + dfs(i + 1, operating- numbers[i], numbers, target)

def solution(numbers, target):
    return recur(0, 0, numbers, target)

 

operating : 이전까지의 연산값

 

graph의 관점에서 생각했을때, 이 문제의 graph구조는 완전이진트리와 같은 형태를 지닌다.

하나의 node의 child_node는 2개인데, 다음값을 더할 node, 그리고 다음값을 뺄 node이다.

이런 생각이 드는 순간, recur함수의 구조가 머리속에 그려지게 되었다.

 

(추후 dfs를 위해 recursion을 써야한다면, 그래프의 구조를 머리속에 그려보는게 함수 구조를 짜는데에 빠르게 다가올 것 같다.)