본문 바로가기
알고리즘/백준

1495번 - dp, Queue, TreeSet

by HWK 2024. 8. 11.

문제:

이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

 

풀이:

bfs와 비슷한 방식으로 풀면 된다고 생각한다.

결국 마지막곡의 볼륨까지 측정해보지 않으면, 아무것도 알 수 없기 때문이다.

총 3가지 방법으로 풀었고 각각 자료구조형이 다를 뿐 비슷한 방법이다.

  1. TreeSet
    TreeSet은 중복을 허용하지 않으며, 자동적으로 정렬까지 해준다.
    고로 메모리가 초과될 일이 없고, 마지막곡에서 가장 큰 볼륨을 측정하기도 쉽다.
    하지만, TreeSet은 자동 정렬이라는 문제 때문에 각 곡의 순서마다 새로운 TreeSet을 마련해 주어야 했다.
    고로 메모리 사용량이 가장 크고, 시간도 가장 오래걸렸다.
    TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(S);

for (int i = 0; i < N; i++) {
    int num = sc.nextInt();
    TreeSet<Integer> nextSet = new TreeSet<>();

    while (!treeSet.isEmpty()){
        int temp = treeSet.pollFirst();
        if (temp + num <= M) {
            nextSet.add(temp + num);
        }
        if (temp - num >= 0) {
            nextSet.add(temp - num);
        }
    }

    treeSet = nextSet;

    if (treeSet.isEmpty()) {
        treeSet.add(-1);
        break;
    }
}
System.out.println(treeSet.last());
  2. dp
    이차원 배열을 이용해주는 방식을 이용했다.
    dp = new boolean[N+1][M+1];
dp[0][S] = true;

for (int i = 0; i < N; i++) {
    int num = sc.nextInt();

    for (int j = 0; j <= M; j++) {
        if (dp[i][j]) {
            if (j + num <= M) {
                dp[i+1][j + num] = true;
            }
            if (j - num >= 0) {
                dp[i+1][j - num] = true;
            }
        }
    }
}

int answer = -1;
for (int i = M; i >= 0; i--) {
    if (dp[N][i]) {
        answer = i;
        break;
    }
}

System.out.println(answer);
     각 순서에 중복이 되지 않도록, 다음 순서의 볼륨을 기록해 놓은 다음,
    다음 차례에서 각 볼륨을 0~M까지 순회하며, 다다음 볼륨을 기록한다.
    이를 반복하면 N번째 볼륨이 기록이 되고, 기록된 볼륨 중 가장 큰 볼륨을 출력한다. 

    M이 커지면 비효율 적일 것이라 생각했지만, 의외로 가장 빠른 풀이법이다.
    메모리 요구량 또한 가장 적다.
  3. queue
    bfs를 푼 방식과 거의 유사하게 풀었고, visited[][]배열을 활용한다.
    queue = new LinkedList<>();
visited = new boolean[N+1][M+1];

queue.add(S);
visited[0][S] = true;


for (int i = 0; i < N; i++) {
    int num = sc.nextInt();
    int size = queue.size();

    if (size == 0) {
        System.out.println(-1);
        System.exit(0);
    }

    for (int j = 0; j < size; j++) {
        int temp = queue.poll();
        if (temp + num <= M && !visited[i+1][temp+num]) {
            visited[i+1][temp+num] = true;
            queue.add(temp + num);
        }
        if (temp - num >= 0 && !visited[i+1][temp-num]) {
            visited[i+1][temp-num] = true;
            queue.add(temp - num);
        }
    }
}

int max = -1;
for (int i = M; i >= 0; i--) {
    if (visited[N][i]) {
        max = i;
        break;
    }
}
System.out.println(max);
     queue의 size를 미리 기록해놓고 그만큼 꺼내서 다음곡의 볼륨을 만들어주는 방법이다.
    가장 빨리 풀릴줄 알았으나, 시간과 메모리 둘다 두번째이다.

전체코드:

  1. TreeSet
    import java.util.*;

public class 기타리스트_1495번_treeSet {
    static int N, S, M;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt(); // 초기값
        M = sc.nextInt(); // 최댓값

        TreeSet<Integer> treeSet = new TreeSet<>();
        treeSet.add(S);

        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            TreeSet<Integer> nextSet = new TreeSet<>();

            while (!treeSet.isEmpty()){
                int temp = treeSet.pollFirst();
                if (temp + num <= M) {
                    nextSet.add(temp + num);
                }
                if (temp - num >= 0) {
                    nextSet.add(temp - num);
                }
            }

            treeSet = nextSet;

            if (treeSet.isEmpty()) {
                treeSet.add(-1);
                break;
            }
        }
        System.out.println(treeSet.last());
    }
}
  2. dp
    import java.util.*;

public class 기타리스트_1495번_dp {
    static int N, S, M;
    static boolean[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt(); // 초기값
        M = sc.nextInt(); // 최댓값

        dp = new boolean[N+1][M+1];
        dp[0][S] = true;

        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();

            for (int j = 0; j <= M; j++) {
                if (dp[i][j]) {
                    if (j + num <= M) {
                        dp[i+1][j + num] = true;
                    }
                    if (j - num >= 0) {
                        dp[i+1][j - num] = true;
                    }
                }
            }
        }

        int answer = -1;
        for (int i = M; i >= 0; i--) {
            if (dp[N][i]) {
                answer = i;
                break;
            }
        }

        System.out.println(answer);
    }
}
  3. Queue
    import java.util.*;

public class 기타리스트_1495번_queue {
    static int N, S, M;
    static Queue<Integer> queue;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt(); // 초기값
        M = sc.nextInt(); // 최댓값

        queue = new LinkedList<>();
        visited = new boolean[N+1][M+1];

        queue.add(S);
        visited[0][S] = true;


        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            int size = queue.size();

            if (size == 0) {
                System.out.println(-1);
                System.exit(0);
            }

            for (int j = 0; j < size; j++) {
                int temp = queue.poll();
                if (temp + num <= M && !visited[i+1][temp+num]) {
                    visited[i+1][temp+num] = true;
                    queue.add(temp + num);
                }
                if (temp - num >= 0 && !visited[i+1][temp-num]) {
                    visited[i+1][temp-num] = true;
                    queue.add(temp - num);
                }
            }
        }

        int max = -1;
        for (int i = M; i >= 0; i--) {
            if (visited[N][i]) {
                max = i;
                break;
            }
        }
        System.out.println(max);

    }
}

시행착오:

dp, Queue, TreeSet의 시간 차이가 나는 이유는 다음과 같다.

 

1. TreeSet 방식:

  • 원리: 이 방법에서는 각 단계에서 가능한 볼륨을 TreeSet에 저장하고, 이를 기반으로 다음 단계에서 가능한 볼륨을 계산한다. TreeSet은 이진 트리 기반의 자료구조로, 요소를 추가하고 삭제하는 데 O(log n)의 시간이 소요됩니다.
  • 비교: TreeSet을 사용하여 모든 가능한 볼륨을 추적하지만, 각 단계에서 요소를 pollFirst하면서 새로운 TreeSet에 요소를 추가하고 삭제하는 작업이 빈번하게 발생합니다. 이 과정에서 트리의 균형을 유지해야 하므로 추가적인 시간 복잡도가 발생한다.
  • 결과: 불필요한 요소 삽입 및 삭제로 인해 시간 소요가 커질 수 있으며, 특히 입력이 커질수록 성능이 급격히 저하될 수 있다.

2. DP 방식:

  • 원리: DP 방식은 각 단계에서 가능한 볼륨을 2차원 배열에 직접 기록한다. 이 배열은 특정 시점에서 가능한 볼륨을 기록하며, 중복된 계산을 피하기 위해 이전 단계의 계산 결과를 그대로 사용한다.
  • 비교: DP 방식은 단순히 배열의 인덱스를 통해 가능한 볼륨을 관리하므로, 요소를 추가하거나 삭제하는 데 추가적인 시간이 소요되지 않는다. 또한, 메모리 접근과 계산이 단순하고 반복적으로 이루어지므로 캐시 효율성도 높다.
  • 결과: 이 방법은 다른 두 방식에 비해 불필요한 연산이 없고, 각 단계에서 가능한 모든 경우를 효율적으로 처리할 수 있으므로 시간 복잡도가 낮아 가장 빠르게 동작한다.
    간단한 메모리 접근을 통해 모든 경우의 수를 체계적으로 계산하기 때문에 실질적인 연산 시간에서 더욱 효율적이다.

3. Queue 방식:

  • 원리: Queue를 사용하여 BFS(너비 우선 탐색) 방식으로 접근한다. 각 단계에서 가능한 볼륨을 큐에 저장하고, 그 다음 단계로 넘어가면서 가능한 볼륨을 추적한다. 또한, visited 배열을 사용하여 중복된 계산을 피한다.
    일반적인 LinkedList 기반의 Queue에서 요소를 추가(add)하거나 제거(poll)하는 작업은 O(1)의 시간 복잡도를 가진다.
  • 비교: 이 방법은 TreeSet 방식보다 효율적이지만, 여전히 큐에 요소를 추가하고 제거하는 작업이 빈번하게 발생한다. 큐의 크기 자체가 문제의 규모에 따라 커질 수 있고, 특히 중복된 요소를 관리하기 위해 방문 여부를 체크하는 visited 배열의 사용으로 인해 시간이 소요될 수 있다.
  • 결과: TreeSet 방식보다는 빠를 수 있지만, 여전히 큐의 크기 및 탐색 범위에 따라 성능이 저하될 가능성이 있다.
    큐를 사용한 BFS 방식은 시간 복잡도 측면에서 나쁘지 않지만, 실질적으로 많은 요소를 처리하고 관리하는 데서 오버헤드가 발생한다.

즉, 큐에 요소를 추가하고 제거하는 방법보다, for문을 통한 단순한 배열 인덱스를 이용하는게 더 빠르다는 말이다.

'알고리즘 > 백준' 카테고리의 다른 글

12026번 - BOJ 거리(DP)  (0) 2024.08.13
11058번 - dp, 규칙찾기  (0) 2024.08.11
15989번 - dp, 규칙찾기  (0) 2024.08.08
15486 - 퇴사2(dp)  (0) 2024.08.07
16930번 - 달리기(BFS)  (0) 2024.08.06

관련글

티스토리툴바