[알고 스터디] 4. 그래프(Graph)와 탐색(Search) - 타겟넘버

프로그래머스 Lv.2 - 타겟넘버

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

프로그래머스

---

[1] 풀이 및 생각

 

1-1) 처음 접할때 생각

문제가 분명 dfs/bfs인데 사실 어떤 방식으로 bfs/dfs를 적용해야 할지 파악을 못함.

트리로 생각을 해보자니 그럼 또 결국 더하기/빼기를 정해야하고...

만약 리스트 안에 [원래 값들, -붙인 값들] 이렇게 해서 뭐 그래프 내에서 탐색을 하자니 그것도 이상한거 같고ㅠ

생각하기가 너무 어려웠다.

 

1-2) 스터디 후 생각

이번 스터디 하면서 많이 배웠던게, 재귀를 사용하는 법이다.

나의 이번 선택이 다음 선택에 영향을 줄때, 시행했을때/안했을때를 경우의 수로 재귀로 표현할 수 잇다니 신기했다@!!!!

그래서 넘버들에서 더했는지 뺐는지 선택했다 ㅎㅎ

 

[2] 코드

def solution(numbers, target):
    answer = 0
    i = 0
    
    def bfs(cur:int, total:int):
        nonlocal answer
        if cur == len(numbers):
            if total == target:
                answer += 1
            return
    
        bfs(cur + 1, total + numbers[cur])
        bfs(cur + 1, total - numbers[cur])

    
    bfs(0, 0)
    return answer

코드는 간단하다.

사실 이건 함수이름 잘못지음,, dfs입니다,,,원래 bfs로 풀려다 보니까 dfs네

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

0,0 부터 시작해서 더하거나 빼는 경우의 수를 모두 계산한다.

 

[3] 시간복잡도 계산

이건 거의 브루트포스식 계산이라  O(2^N)이다 ㅜㅠ

DP같은걸로 푸면 더 나을수 있다,,