99클럽 코테 스터디 11일차 TIL - LV2. 타겟 넘버

 

오늘의 학습 키워드

• 깊이우선탐색(DFS)

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

class Solution {
    int answer = 0;

    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, target, 0);

        return answer;
    }

    // 깊이 우선 탐색
    public void dfs(int[] numbers, int depth, int target, int sum){
        if(depth == numbers.length){ // 마지막 노드 까지 탐색한 경우
            if(target == sum) answer++;
        } else {
            dfs(numbers, depth + 1, target, sum + numbers[depth]); // 해당 노드의 값을 더하고 다음 깊이 탐색
            dfs(numbers, depth + 1, target, sum - numbers[depth]); // 해당 노드의 값을 빼고 다음 깊이 탐색
        }
    }
}

 

• 모든 경우의 수를 다 체크해봐야 하는 dfs 로 풀면되는 문제이다.
• if문에서는 길이만큼 끝까지 sum 시키고 target 과 같은지 체크해서 answer +1 한다.
• else문에서는 다시 dfs 재귀 호출한다. 여기서 포인트는, 해당 구간에서 재귀를 2번 시켜서 sum 을 넘길 때 sum에 numbers[depth] 을 + 하거나 - 해서 sum으로 넘기는 것
  • 내가 생각해내지 못한 부분이다. 예를들어 숫자배열 4,1,2,1 이 주어지면 4,-4,1,-1,2,-1,1,-1 이렇게 다시 나열한다음에 풀어야하나? 했는데 오히려 간단한거였음.. 재귀를 +,- 붙여서 두번시키면 되는 거였네!

3. 피드백

• dfs 는 어제 처음 접한거라 아직 코드가 손에 안익어서 이번에도 서칭해서 코드를 확인 했다.ㅠㅠ 조금 익숙해지면 감 잡히겠지!

참고

• [프로그래머스] 타겟 넘버 - Java
• [알고리즘] 너비 우선 탐색(BFS)이란 (BFS 참고 학습용)