[Algorithm] DFS (프로그래머스 타겟넘버 문제를 통한 이해)

이 그림 좀 그만 보고 싶다.

오늘은 진짜 지금껏 나를 괴롭혀온 DFS / BFS 이해가 조금이나마 된 것 같아서 다른 사람은 나같은 개삽질하지말라고 한번 써본다. (요근래 개발관련 업로드가 별로 없었던게, 코테 준비때문에 안그래도 나쁜 머리 싸매고 살아서 기술 공부할 시간이 없었다..)

내가 구글링을 못하는건지 대부분의 구글링 결과가 Graph를 통한 구현 사례만 계속 보여줘서 전혀 이해를 못했고,  코테 예제를 본다고 해도 생각보다 많은 사람들이 제대로 설명해주는 글이 없고 풀이한 답안만 보여주는게 많았기 때문에 상당히 힘들었는데, 오늘에서야 진짜 어느정도 이해가 된다. 시점까지 와서 글을 작성할 수 있게 되었다. 

솔직히 말해서 이정도 알기 시작하면 궤도에 올랐다. 코딩테스트에 응시해도 제대로 코딩테스트가 진행이 된다고 할 수 있을 것 같은데, 그 이유가 오늘 예제로 들게 진짜 간단한 DFS 구현임에도 불구하고 프로그래머스 lv2에 올라가 있다. 탑티어 기업들 제외하고 일반적인 코딩테스트가 lv2,3 정도 수준에 그친다고 하니, 이제 조금만 더 노력한다면 코딩테스트를 큰 걱정없이 응시하고 통과할 수 있다는 의미가 된다.

 

 

1. Node는 도대체 뭘 말하는 걸까?

기본적으로 노드는 트리 구조를 가진 그래프를 보고 있을 때, 각 분기점이 되는 점을 일컫는 말이다. 

허나, 코딩테스트 풀이를 볼 때 정말 많이 마주하게 되는 혼란스러운 요소가 '노드(Node)' 에 대한 이야기인데 난 내가 받은 배열은 분명 1차원 배열 단 하나 뿐인데, 어떻게 그렇게나 많은 노드가 쏟아질 수 있는 걸까? 라는 의문에서 정말 오래 막혀있었다. (물론 당연히 전체 노드를 그냥 주는 케이스도 있다. 근데 1차원배열만 띡 주는 경우에 그냥 난 접근도 못했음) 하지만 이런 의문과 고민이 정말 허무하게도 실 데이터를 기준으로 노드를 생각하는게 아니라 경우의 수를 뽑아내는거라고 보면 될 것 같다.  프로그래머스 타겟넘버 문제를 통해 설명해보겠다.  문제는 링크 달아두겠음

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

프로그래머스

 

문제를 보면 numbers 라는 1차원 배열, 그리고 target이라는 만들어야하는 숫자가 주어지는데 배열의 각 요소를 적절히 더하거나 빼서 target에 해당하는 값에 도달할 수 있는 방법의 갯수를 찾아라는 문제다. 일단 Node에 대한 이야기니 numbers에 주목하겠다.  [1,1,1,1,1] 이런 배열이 있다고 예를 들면, 이 모든 배열의 요소들은 +1 이 될 수도 있고, -1이 될 수도 있다. 그러면 인덱스 순서대로 반복을 한다고 했을 때 첫번째 요소가 1 이었다면 두번째 1은 +1이 될 수도 있고, -1 이 될 수도 있다고 가정을 하고 재귀함수를 돌리는거임. 그래서 그 모든 경우의 수들이 Node가 되는거였다. 

여기서 내가 혼란스러울 수 밖에 없었던 이유는 내 업무 때문이라는 생각이 들었다. 항상 실제로 존재하고, 추상적으로 생각할 필요가 없는 데이터만 가지고 개발하는 업을 하고 있다보니, 경우의 수라는 걸 Node로 구성할 생각 조차도 못했고,  그러다보니 "도대체 노드로 삼을 만한게 없는데 뭘 자꾸 자식노드부터 우선탐색을 하래!" 
같은 소릴 하게 되었던거였다.

 

2.  그래서 DFS는 어떨 때 적용하는 걸까?

이것도 환장할 문젠데, 앞서 말한 노드의 의미를 안다고 해도, 기본적으로 학원 발 비전공 개발자인 내가 적재적소에 사용하는 법 같은걸 배운 적이 없고, 생각해본적도 없으니 이 문제가 DFS를 요구하는건지 BFS를 요구하는건지 어떤 알고리즘을 쓰길 바라는건지 분간이 안간다. 일단 다른 알고리즘은 들여다봐야 알겠지만, 어찌됐든 DFS 정도는 분간이 가능할 것으로 보여서 한 번 이야기 해보고자 한다. 

 

기본적으로 DFS는 깊이 우선 탐색을 한다. 그러니까 최초 노드에서부터 그 자식 노드 중 가장 바닥에 있는 노드까지 쭉 살펴본다는 얘긴데, 앞서 언급했던 타겟넘버라는 문제를 기준으로 생각했을 때 가장 마지막 노드로 보이는건 배열의 가장 마지막 인덱스에 들어있는 1 (이 1의 경우의 수인 +1, -1 )일거다. 그러니까 이 마지막 노드의 경우의 수 +1, -1을 바꿔가며 계산하는게 가장 우선이라는 뜻이 된다. 

자 그럼 여기서 우리가 생각해야할 것은 뭐냐면, "배열의 전체 요소를 다 사용하느냐 마느냐" 라는 문제가 "DFS를 사용할건가 말건가"를 결정짓는 문제라는 거다.  마지막 요소까지 타고타고 들어간다는 얘기는 앞의 요소들을 모두 사용하고 있다는 의미가 되고, 이런 문제에서 DFS가 가장 적합할지는 알 수 없지만 그래도 적합한 알고리즘의 후보에 올라갈 수 있다는 의미가 된다. 

 

이해가 안되는 사람들을 위해 예를 한번 들어보겠다. 

특정 배열이 주어지고  "배열 안의 요소를 모두 이러이러하게 조합하여, 이런 값을 도출할 수 있는 경우의 수를 찾아라." 같은 뉘앙스를 풍기는 문제가 DFS의 대표적인 문제라는 뜻이다.  (모두 라는 느낌이 중요한거임.)

당연히 문제에 따라 따지고보면 중복인 경우는 제하고 뭐 이런 조건이 들어갈 순 있을거다.

 

3. 하고 싶은 이야기

코테를 준비하면서 느낀 점은 생각보다 많은 설명들이 불친절하다는거다. 당연하다고 해야할지.. 개발자들의 문화란게 레퍼런스를 제공해주는거까진 많지만, 그게 왜 그렇게 되는지를 설명해주는 사람들은 많지 않고, 스스로 깨달아라는 풍조가 강하기 때문에 자연스레 이런 방향으로 온 것 같다고 생각한다. 

나는 비록 삽질을 했지만 다른 신입개발자들은 기왕이면 조금 더 빠른 길을 걸을 수 있길 바라며, 작성해봤는데 도움이 되었으면 좋겠다.