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

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

프로그래머스

 

 

1. 문제 및 해석

 

n개의 정수로 순서대로 들어온 수가 있고, 그 순서를 바꾸지 않고 +,- 둘중 하나를 써서 타겟 넘버를 만들어라

 

들어온 수대로 dfs로 depth를 파고 계속 들어가면 될듯 ?

 

어떻게 완성된 지 판별할까 ? depth가 5까지 가면 ? 무조건 세지말고 더해진 값이 맞으면 ++

 

 

 

제한사항

 

 

 

주어지는 숫자의 개수는 2개 이상 20개 이하입니다.  ( 100만개 정도 들어온다)

각 숫자는 1 이상 50 이하인 자연수입니다.

타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

 

 

 

2. 풀이

 

 

public class 타겟넘버 {

    private static int count;


    private int numbers[];
    private int target;

    public static void main(String[] args) {

        int [] numbers = new int[]{1, 1, 1, 1, 1};
        int target = 5;




        타겟넘버 main = new 타겟넘버();
        System.out.println(main.solution(numbers, target));


    }


    private int solution(int[] numbers, int target) {

        this.numbers = numbers;
        this.target = target;
        count = 0;

        dfs(0, 0);
        return count;

    }

    private void dfs(int depth, int sum) {

        if (depth == numbers.length) { // 기저조건
            // 들어온 배열의 크기까지 가기만 하면 return 해주는데,
            // answer을 추가해주는 조건은 더해진 수가 target넘버가 되면 count
            if (sum == target) {
                count++;
            }
            return;

        }

        dfs(depth + 1, sum + numbers[depth]);
        dfs(depth + 1, sum - numbers[depth]);

    }
}

 

 

2-1 시간 복잡도

 

 

 

시간 복잡도는 2^20 이다.

 

나올 수 있는 경우의 수가 + or - 둘 중 하나라서 2에다가 최대 20개의 숫자가 들어올 수 있으니 2^n

대부분의 코딩테스트 1ms 500만개가 완전 탐색의 선이라고 생각한다면 충분히 재귀 완탐으로도 가능하다..

 

 

 

2-2 DFS

 

 

 

 

중요 조건인 기저 조건은 

 

depth라는 깊이를 정하고

깊이가 예로 들어 {1, 1, 1, 1, 1}의 numbers의 배열이라면 5만큼 들어가면 탈출하게 만드는데,

5만큼 가기만 하면 세어 주는 게 아니라 깊이가 맞더라도 합쳐진 수가 들어온 target에 맞으면 count를 세어주고 탈출 시켜준다.

 

 

그리고 실제 dfs 동작방법은

는 파라미터로 depth에 1을 더한 수와 그 numbers의 배열 index의 수 + 누적된 sum에 더해서 argument로 넘겨준다.

 

 

 

 

3.  마무리

 

 

 

 

1. 근데 이 문제는 depth를 먼저 잡지 말고 sum도 같이 검사해주면 좀 더 탐색이 줄어들지 않을까 ?

 

2. 사실 dfs와 bfs는 이해하기가 어렵지 풀이법 자체는 간단할 때가 너무 많다..

재귀나 dp도 이런 느낌인데 요새 dp를 하다보니, 점화식 찾는 게 어려워서ㅜㅜ

 

다시 dfs로 돌아와서 말하자면, 

기저조건을 잘 설정해주고, 어떤 argument를 넘겨줄지 잘 판단해서 정하면 실마리가 잘 잡힌다.

 

 

 

그리고 dfs와 bfs의 차이는 깊이와 넓이인데 완탐의 경우 차이가 없으나 둘 중 하나가 안될 때가 있어서

 

잘 구분하고 둘다 익숙해여야 할 것 같다..

dfs만 자주 써와서 ㅠㅠ