[프로그래머스] level.2 타켓 넘버 ( 이걸본다면 단숨에 이해 가능!!)

 

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

프로그래머스

 

 

dfs/bfs문제를 처음 접하는데  하루종일 풀었다.  

이건 혼자서 풀어볼려고 하는 것보다 dfs/bfs 개념을 충분히 숙지한 뒤 푸는 게 더 좋을 것 같다. 

처음에 이상한 풀이봐서 이해가 가지 않았는데 너무 친절하게 설명해주는 블로그 만나서 이해가 되었다. 

 

 

 

📒 풀이

 

function solution(numbers, target) {
    let answer = 0;
    dfs(0, 0);
    function dfs(index, sum) {
        if(index === numbers.length) {
            if (sum === target) answer++;
            return;
        }
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
    return answer;
}

 

 

📒  DFS (깊이우선탐색) 알고리즘 

 

DFS가 도대체 무엇인가?

source : https://www.crazyforcode.com/

그림으로 보면 가장 이해가 쉽다. 

말그대로 하나의 노드를 깊게 파고들며 순회하는 검색 알고리즘이다. 

여기서 포인트는  "깊게" , "순회" 이다. 

하나의 경우의 수를 끝까지 간뒤 상위 노드로 이동하고 방금 방문한 노드를 제외한 다른 노드를 간다.  

이런식으로 전부 순회하는 것이 DFS이다. 

 

위 그림을 보면 

0 1 3  끝까지 갔으니 다시 한 노드 올라가서  1 - 4 다시 1 - 5 왼쪽은 끝났으니 쭉 위로 올라가서 다시 0부터

0 2 6   끝!!

 

자 이걸 우리가 풀어야할 문제에 적용해보자.

1, 1, 1, 1, 1

이렇게 1이 다섯개이고 각 1은   +1  or -1  둘 중 하나만 가능하다 

그리고 그걸 아래 표로 표현해봤다.

 

 

처음이  "+" 일때 16개  "-" 일때 16개 해서 경우의 수는 총 32개이다. 

 

 

자 이상태로 코드를 실행해보자. 

일단은 정답을 찾기보다 DFS를 코드로 만드는 방법을 배워보자. 

 

function solution(numbers, target) {
    dfs(0, 0);
    function dfs(index, sum) {
        if(index === numbers.length) return;
        dfs(index + 1, sum + numbers[index]);
        dfs(index + 1, sum - numbers[index]);
    }
}

위 코드는 정답 코드에서 정답은 빼고 DFS만 하도록 고친 코드이다. 

즉 DFS를 통해 전체를 순회하도록 만든 코드이다. 

위 코드가 어떤 매커니즘으로 작동하는지 이해해보자. 

 

 

예제는 실제 문제처럼  

numbers = [ 1, 1, 1, 1, 1]

target = 3이다.  ( 지금은 정답을 구하는 게 아니라 target이 필요없다.)

처음에 dfs(0, 0) 으로 index  =  0   ,  sum = 0 이 할당된다. 

if( 0 === 5) 은 false이기에 pass

dfs( 0 + 1 ,  0 + numbers[0])      즉  dfs( 1, 1) 이 다시 호출된다.  

이런식으로 재귀함수가 쌓이게 된다. 

dfs(0,0) 을 시작으로

dfs(1,1)

dfs(2,2)

dfs(3,3)

dfs(4,4)

dfs(5,5)    그런데 여기서   index = 5이기에 if절이 true가 되어 return이 되어 끝이난다  

자 여기까지 이해가 안된다면 더 쉽게 그림으로 이해해보자

dfs(0,0), dfs(1,1), dfs(2,2), dfs(3,3), dfs(4,4), dfs(5,5) 전부 빨간색 함수만 호출했다. 

그리고 드디어 dfs(5,5)에서 빨간색 함수가 호출이 끝난다. 

그럼 바로밑에 파란색 dfs함수가 다시 호출된다. 

현재 index = 4이다 왜냐면 

 4+ 1 = 5  즉 dfs(5,1){빨간색 함수}가 if절이 true가 되어서 

index = 4인 상태에서 "파란색" 함수가 호출이된다. 즉   4 + 1 , 3 + number[4] 이기에 dfs(5, 3) {파란색 함수}이 호출 된다. 

dfs(5,3)도 if 절이 true이기에 return 이되어 함수가 끝난다. 

그런데 기억하자 지금 재귀가 쌓이고 있다. 

아직 dfs(0,0) , dfs(1,1), dfs(2,2) , dfs(3,3)이 return이 안되어서 마지막에 호출된 dfs(5,5)부터 리턴이 끝나서 순서가 오길 기다리고있는 중이다.  이제 dfs(5,5) 끝나고 dfs(5,3) 끝나서 dfs(4,4)이 if절이 trun는 아니지만 빨간함수 파란함수 전부 호출을 했기에 임무가 끝났다. 

이제 다음 순서를 기다린 dfs(3,3)을 마저 처리할때이다.  dfs(5,5)까지 호출했기에 빨간 함수는 끝까지 호출했기에 파란색만 호출하면  임무가 끝난다. 

그래서 dfs(3,3)이 파란함수를 호출해서 dfs(4,2)가 된다. (아래 그림)  

그리고 dfs(4,2)는  빨간색함수인 dfs(5,3)를 호출하고 index가 5이기에 return으로 종료되고 바로 파란색함수가 호출된다.  dfs(5,1)이 호출된다. (아래그림)

이러한 매커니즘으로 계속된다.  

즉 처음에 dfs(0.0)을 호출했을 때는 dfs(5,5)가 return 되기 전까지는 빨간색 함수만 호출했는데 그 빨간색 함수가 또 빨간색 함수를 호출하고 또 그 함수가 빨간색 함수를 호출하니까 파란색 함수를 호출 하지 못한 상태에서 계속 기다리는 것이다. 

비록 이게 컴퓨터 연산이라 1초도 안되는 시간에 일어나는 일이지만 초 울트라 슬로우 모션으로 보면 이렇게 계속 빨간색 함수만 호출하고 그게 다 끝나서 파란색 함수 호출하기를 기다리는 것이다. 

이걸 이해해야 dfs가 이해가간다.  즉 재귀함수의 특성을 사용해서 dfs를 구현한 것이다.

 

또 다른 자세한 설명은 여기 블로그를 참조하면 된다. 

필자도 이분꺼 보고 이해를 했다. 

https://jjnooys.medium.com/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%83%80%EA%B2%9F-%EB%84%98%EB%B2%84-javascript-1d7983d423b5

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

 

자 여기까지 이해했다면 풀이에 쓴 코드도 충분히 이해할 수 있을 겁니다. 

 

 

 

 

 

추가 +

 

BFS ( Breathed First Search)

 

너비우선탐색 알고리즘이다.

 

https://velog.io/@vagabondms/DFS-vs-BFS

 

이렇게 그림을 본다면 단 번에 이해가 갈 것이다. 

 

BFS는 시작점을 기준으로  인접한 곳을 우선적으로 방문한다.