오늘 제코베에서 처음으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 무엇인지 배웠다. 그래서 프로그래머스에서도 DFS/BFS로 접근해야 하는 문제를 풀어보았다.

문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예

numbers	        target	return
[1, 1, 1, 1, 1]	  3       5
[4, 1, 2, 1]	  4    	  2

입출력 예 설명
입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

+4+1-2+1 = 4
+4-1+2-1 = 4
총 2가지 방법이 있으므로, 2를 return 합니다.

나의 코드

function solution(numbers, target) {
    numbers = numbers.reduce((acc, cur)=>{
       acc = acc.map((arr)=> [[...arr,cur], [...arr, cur * -1]]);
        return acc.flat();        
    },[[]]);
    
    let count = 0;
      numbers.forEach((arr)=> arr.reduce((s,v) => s+v, 0) === target ? count++ : count);
    return count;
}

이진 트리!! binary tree!!
CS에서 배웠던 자료구조를 이렇게 문제로 접해보니 참 좋다.
만약 numbers = [1, 2, 3]이고,
target = 0이라면

라고 나타내고 각 리프노드에 도달했을 때 경로에 있는 노드의 합이 target = 0인지 확인해보면 되겠다고 생각하고 풀어봤다.

numbers 배열에 reduce를 걸고, initial value로 [[]]를 주었다.
그리고 각 current value 마다 acc안의 기존 arr 원소를 map으로 순회하면서 arr 원소를 2개의 arr로 쪼개서 바꿔주었다. 하나는 current value의 양수 값이 push된 arr, 다른 하나는 current value의 음수값이 push된 arr.
이렇게 reduce로 순회를 마치면 모든 경우의 수가 담긴 배열이 반환된다. (flat을 한번 걸어주어야 깔끔하게 2차원 배열이 된다.)
모든 경우의 수 중에서 배열의 합이 target과 같은 것을 고르면 끝! (forEach 사용)

나는 깊이 우선 탐색(DFS)이 아닌 너비 우선 탐색(BFS)을 사용한 것이겠지?
매 step 마다 모든 배열의 원소에 가지를 쳤으니?
(만약 틀리다면 이 글을 보시는 누군가께서 알려주시면 감사하겠습니다. 이 글을 보게되는 누군가가 존재할지는 의문이지만 ㅋㅋㅋㅋㅋ)

못 풀던 걸 풀어낸 거에 의의를 두고 끝내기보다는 binary tree를 좀 더 정석으로(정석?인지 아닌지는 모르겠다만..) 구현한 코드를 한번 감상하고 가는게 더 좋을 것 같다.

다른 코드

function solution(numbers, target) {
    let answer = 0;
    getAnswer(0,0);
    function getAnswer(x,value) {
        if(x<numbers.length){
            getAnswer(x+1,value + numbers[x]);
            getAnswer(x+1,value - numbers[x]);
        } else{
            if(value === target){
                answer++
            }
        }
    }
    return answer;
}

x는 각 원소의 인덱스 번호이고, value에는 배열을 순회하면서 누적되는 값이다.
getAnswer라는 함수 안에 2개의 getAnswer 재귀를 각각 생성. 하나는 기존 누적값에 더하는 재귀, 하나는 기존 누적값에서 빼는 재귀.
이렇게도 이진 트리를 구현할 수 있군! value가 배열의 길이와 같아지는 순간 target과 누적된 값을 비교하여 같다면 answer를 ++해준다.

이 문제는 도대체 어떻게 접근해야 할지 감이 안왔었는데, DFS와 BFS가 무엇인지 알고나니 비로소 접근법이 떠올랐다. 알고리즘에서 자료 구조를 알고 있는게 얼마나 큰 힘이 되고 필수적인지 몸소 깨달았다.

쉬운 코딩이라는 유튜브를 최근에 알게 되었고, 시간복잡도 설명에 반해서 자료구조 영상들도 모두 한번씩 봐보려고 한다. 자료구조가 좀 더 머리에 자리잡으면 알고리즘 풀기도 더 수월해질테니 킵고잉해보자~~~ 화이팅!