[Java/백준] 1182번 : 부분수열의 합

 

👩‍🏫 문제

 

 

---

🚩 풀이 방법

애초에 Brute Force 문제를 찾아서 풀었기 때문에 모든 경우의 수를 탐색해야 한다는 전제 하에, 모든 경우의 수(부분 수열)를 탐색하기 위해 DFS를 사용했다.

 

 

 

1️⃣ 풀이 1. (Stack 사용)

처음에는 괜히 재귀를 안 쓰고 싶어서 Stack을 사용해 while문으로 구현을 했는데 메모리 사용량이 장난이 아니고 속도도 다른 사람들에 비해 매우 느렸다.

 

내 제출 (aka. 메모리 빌런)

 

다른 사람들거...

 

 

- 소스코드

private void getCases(int[] sequence, int N, int S) {
    Stack<int[]> stack = new Stack<>();
    int count = 0;

    stack.push(new int[]{0, -1});  // sum, index

    while(!stack.isEmpty()) {
        int[] tmp = stack.pop();
        int sum = tmp[0];
        int idx = tmp[1];

        if(sum == S) count++;

        for(int j = idx+1; j < N; j++) {
            stack.push(new int[]{sum + sequence[j], j});
        }
    }

    if(S == 0) count--;

    System.out.println(count);
}

 

 

 

2️⃣ 풀이2. (Deque 사용)

BFS 문제 풀 때 queue에 배열을 생성해서 넣는 방법을 자주 사용했는데, BFS는 대체로 최단거리 등 목표값을 찾으면 프로그램이 종료되기 때문에 그동안 이 방식의 문제점을 인지하지 못했던 것 같다.

 

그런데 DFS의 경우에는 모든 경우의 수를 탐색하다 보니 매번 배열 객체를 생성하는 비용이 매우 비싸다는 사실을 이 문제를 통해 깨닫게 되었다...

 

게다가 Stack 자체가 옛날 클래스고 특히 단일 스레드 환경에서는 불필요하게 성능이 저하되기 때문에 차라리 Deque를 사용하는 편이 훨씬 빠르다.

 

Stack -> Deque로 바꿨을 뿐인데 속도 면에서는 꽤나 개선됨

 

 

 

3️⃣ 풀이3. (재귀)

실제 서비스를 개발할 때 java로 재귀를 구현할 일은 거의 없겠지만, DFS 같은 알고리즘 문제 풀 때는 반복문보다 재귀를 사용하는 게 소스 가독성이나 성능 면에서 오히려 나은 것 같다.

 

정답이라고 알려진 재귀 소스 코드를 실행해보긴 했는데, 불필요한 메소드 호출이 조금 있는 것 같아서 개선할 부분이 있는 코드인 것 같다.

 

재귀 실행 결과

 

 

- 소스코드

private int[] sequence;
private int N;
private int S;
private int count = 0;

private void dfs(int sum, int depth) {
    if(depth == N) {
        if(sum == S) {
            count++;
        }
        return;
    }

    dfs(sum + sequence[depth], depth+1);
    dfs(sum, depth+1);
}

private void getCases() {
    dfs(0, 0);

    if(S == 0) count--;

    System.out.println(count);
}