프로그래머스 - 타겟넘버 (java)

문제 😵‍💫

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

프로그래머스

 

내 풀🦷

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    private int dfs(int[] numbers, int target, int index, int sum) {
        // 모든 숫자를 다 사용했을 떄
        if(index == numbers.length) {
            // 목표 숫자와 합이 같으면 경우의 수 1 증가
            return sum == target ? 1 : 0;
        }
        // 현재 숫자를 더하는 경우와 빼는 경우로 재귀 호충..
        return dfs(numbers, target, index + 1, sum + numbers[index]) + dfs(numbers, target, index + 1, sum - numbers[index]);
    }
}

 

이미 한번 풀었던 dfs 문제!!

모든 가능한 경로를 다 탐색하여 특정 조건을 찾아야하는 문제이므로 dfs를 사용하였다

if문을 쓰는것까지는 쉬운데 마지막에 재귀를 어떻게 시켜야하는지는 항상 고민되는 부분인거 같다..

하지만 이번문제는 수월하게 통과~~

 

참고하면 좋을 개념들 ✍️

 

 DFS를 사용했을 때 효과적인 문제 유형

1. 모든 경로를 탐색하여 특정 조건을 찾는 경우 : 주어진 숫자 배열을 더하고 빼서 특정 값을 만드는 문제
2. 해다 존재하는지 확인하는 경우 : 미로에서 출구까지 가는 경로가 있는지 확인할 때
3. 조합과 순열을 생성하는 문제 : 특정 길이의 조합을 생성하거나, 순열을 만드는 문제
4. 백트래킹과 함께 사용할 때 : N-Queens 문제처럼 제한 조건을 만족하는 경우의 수를 찾을 때

 

DFS 사용 시 주의사항

- 무한 루프 주의 : 재귀 호출에서 종료 조건을 명확히 설정해야 합니다

- 메모리 사용량 : 깊이가 깊어질 경우 메모리 사용량이 커질 수 있으므로, 너무 깊은 재귀 호출이 필요한 문제에서는 스택 오버플로우에 주의해야 합니다

- 탐색 최적화 : 백트래킹을 사용하여 불필요한 경로는 조기에 중단하여 효율성을 높일 수 있습니다