[프로그래머스] 타겟 넘버

주어진 리스트 값을 하나씩 접근하며 -, +부호를 달아주는 문제이다.

DFS/BFS를 활용한 문제라고 한다. 이 문제를 풀면서 DFS/BFS와 완전탐색의 차이가 무엇인지 궁금해졌다. 

* 완전탐색을 베이스로 한 그래프 탐색 기법이다..! 

 

[1,1,1] 리스트와 [+, -]를 사용해 숫자 1을 만들 수 있는 경우의 수를 구하려면, 모든 방법을 확인해보아야 한다.

 

 1. list의 idx 0의 값에 - 또는 + 부호를 할당하고, 합계를 나타내는 sum에 저장한다.

 2. -1 / +1 을 각각 저장한 sum이 2개가 된다.  * 이게 cache에 저장한다고 하는건가?

 3. 두 sum에 각각 idx 1의 값에 -또는 + 부호를 할당 한 값을 저장한다. 따라서 sum이 4개가 된다.

 4. 이를 idx가 끝에 도달할 때까지 반복한다.

 

하나의 노드에서 여러 가지로 뻗어나가는 트리를 생각하면 이해가 쉽다!!

 

이것을 일반화해서 코드로 표현하면 아래와 같다!

function solution(numbers, target) {
    var answer = 0;
    function getValue(sum, idx){
        if(idx === numbers.length){
            if(sum ===target){
                answer+=1
            }
        }
        else{
        getValue( sum + numbers[idx], idx+1)
        getValue( sum - numbers[idx], idx+1)
        }
    }
    getValue(0, 0)
    return answer;
}

 

이 방법은 DFS를 사용한 것이다.

DFS는 Depth First Search로 깊이 우선 탐색 방법이다.

코드의 재귀 부분에서 +연산이 -연산 보다 위에 있다.

따라서, 아래와 같은 방식으로 실행된다.

 

1. idx 0까지 +연산, idx 1에서 +연산
   
   1. idx 1까지 +연산, idx 2에서 +연산
   2. idx 1까지 +연산, idx 2에서 -연산
2. idx 0까지 +연산, idx 1에서 -연산
   1. idx 1까지 -연산, idx 2에서 +연산
   2. idx 1까지 -연산, idx 2에서 -연산

... 

 

그림을 보면 명확히 DFS라는 것이 이해될 것이다!