[99클럽 코테 스터디 11일차 TIL] DFS

📒 DFS

 

 

✏️  오늘의 문제 : 타겟 넘버

 

📌 주안점

• numbers 배열의 값을 모두 더하거나 빼서, target 숫자를 만드는 방법의 수를 기록한다
  • number 배열을 모두 순회(끝까지 가서), target 숫자를 만들어야 한다.
  • 배열 모두 순회하는 경우의 수 -> 경로의 특징마다 구분되어야 한다.
• 끝까지 가서의 총합을 알아야 하기에, DFS를 사용한다. 주어지는 숫자의 개수는 2개 이상, 20개 이하이므로 재귀를 이용한 DFS를 고려해도 충분한 시간이다.

 

📌 해결 방법

1. numbers[20] 배열을 top index로 순회한다.
2. currentsum += numbers[top]*operator 로 현재까지의 합을 저장한다.
   1. top index가 배열의 끝이라면, currentsum이 target과 같은지 비교한다.
      1. 같다면, 1가지 경우가 늘어나므로 1을 리턴한다.
      2. 다르다면, 아닌 경우이므로 0을 리턴한다.
   2. 배열의 끝이 아니라면, top+1 인덱스에 대해 *1 or *-1 operator를 수행한 값을 더하는 재귀함수를 반복한다.

 

 

 

📌 더 공부할 점

• python에서 global 변수 사용시의 주의점
• dfs시 top index를 더해주는 시점과, dfs 비교를 위한 연산 수행 시점에 대한 고민