[프로그래머스] 43236 징검다리 (C/C++)

문제

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

풀이

문제를 처음 읽었을 때, 최적해를 반드시 보장하는 완전 탐색으로 접근하면 되겠다고 생각했다.

DFS로 모든 경우의 수를 탐색하는 경우에 대해 생각해보았고, 시간 복잡도가 대충

\binom{n}{n/2} = \frac{n!}{(n/2)! \cdot (n/2)!} = O\left(\frac{2^n}{\sqrt{n}}\right)

이고 n이 최대 50000이므로 이 방법은 절대 불가능하다고 판단했다.

이후 문제를 더 읽다가 문제 카테고리가 이분 탐색인 것을 보아버렸고, 스포일러 당했다는 생각에 기분이 썩 좋지 않아 이분 탐색 이외의 방법으로 접근하려고 했다. 고민하다 O(n log n)의 시간 복잡도를 가지는 우선순위 큐와 index 배열을 조합한 하이브리드 컨테이너를 사용하는 방식을 떠올렸다.

아래는 해당 로직이다.

초기화

우선순위 큐에는 현재 노드의 index와 다음 노드까지의 거리를 저장하는 구조체를 넣는다.
distances 배열에는 각 노드에서부터 다음 노드까지의 실제 거리를 저장한다.
indices 트리에는 현재 존재하는 노드의 index를 저장한다.

메인 로직 (n회 반복)

우선순위 큐에서 거리가 가장 짧은 노드를 뽑는다. 해당 노드가 이미 제거된 노드이거나 distances 배열과 값이 다를 경우 이후 노드를 뽑는다. (lazy deletion)
indices 트리에서 해당 노드의 이전 노드와 이후 노드를 찾는다. 이전 노드와 이후 노드가 없을 수도 있다. 즉, 현재 노드가 맨 앞이나 맨 뒤일 수 있다.
이전 노드와 이후 노드 모두 유효할 경우, 둘 중 짧은 노드와 현재 노드를 병합한 후, distances 배열과 우선순위 큐를 갱신한다.

C++17

std::priority_queue<Node> pq;
std::vector<int> distances;
std::set<int> indices;

auto push = [&] (int index, int distance) {
    pq.push({ index, distance });
    distances.push_back(distance);
    indices.insert(index);
};

// 초기화

while (n--) {
	// 노드 추출
	// 이전, 이후 노드 탐색
	// 노드 병합
	// 상태 갱신
}

하지만 이 로직이 일부 케이스에 대해 실패했다. 최소값을 계속 제거하다 보면 최소값이 최대가 될 것이라는 점에서 Greedy한 접근이 최적해를 보장할 것이라 생각했는데 도저히 틀린 이유를 찾을 수 없었다.

조금 더 고민해보다가 이러한 Greedy한 접근이 지역 최적해를 보장할 수 있지만 전역 최적해를 보장하지는 않는다는 것을 떠올리며 반례를 생각해보았다.

distance = 16이고 rocks = [ 4, 8, 11 ], n = 2인 경우를 생각해보자. 정답은 4와 11을 제거하여 0-8, 8-16 구간을 만들어 최소값이 8이 되게 하는 것이다.

하지만, Greedy하게 접근했을 때는 다음과 같이 된다.

최소 구간인 3(8-11)을 제거한다. 이전 노드, 이후 노드 중 짧은 구간인 4(4-8)와 병합하여 0-4, 4-11, 11-16의 세 구간으로 만든다.
다음 최소 구간인 4(0-4)를 제거한다. 이전 노드가 존재하지 않으므로 5(11-16)와 병합하여 0-11, 11-16의 두 구간이 된다.
최종적으로 5가 답이 된다.

억지로 정답이 되게 하려면 3을 제거한 후 4와 병합하는 것이 아니라 5와 병합했어야 했으나, 그 반대 경우와 다른 여러 가지의 경우도 충분히 발생할 수 있기에 Greedy한 접근이 전역 최적해를 보장하지 않는다는 것을 알 수 있었다.

후보를 구하는 방식, 동적 계획법, 최대-최소 경로, 등등의 여러가지 방법은 최소 $O(n^2)$ 이상의 시간 복잡도를 가지기에 모두 불가능하다고 판단했고, 목표 함수가 subset 선택 후 구간 최소 최대화인 전형적인 min-max 구조이므로 이분 탐색으로 접근하는 것이 맞다고 결론을 내렸다.

이분 탐색으로 접근할 때, 중간에 삭제된 노드로 인해 두 노드 사이의 거리가 변하는 것을 어떻게 처리할지 고민했다. prev 변수를 두어 노드를 삭제하지 않을 때 prev를 갱신하고, 삭제할 때는 prev를 갱신하지 않는 방식으로 해결했다.

프로그래머스에서 이분 탐색과 같이 카테고리가 보이는 것을 좋아하지 않는다. 하지만 덕분에 이분 탐색 이외의 여러 방법을 고민해볼 수 있었고, Greedy한 접근이 항상 최적해를 보장하지 않는다는 개념을 다시 한 번 되새길 수 있었다. 이론을 넘어 실제 반례도 찾아보면서 지역 최적해와 전역 최적해를 보장하지 않음을 증명할 수 있었고, 실제 비지니스 로직에서도 이러한 부분이 자주 사용되지 않을까 생각해보았다.

소스 코드

오답 코드(Greedy, $O(n \log n)$ )

C++17

#include <bits/stdc++.h>

struct Node {
    int index, distance;

    bool operator<(const Node &other) const {
        return this->distance > other.distance;
    }
};

int solution(int last, std::vector<int> rocks, int n) {
    std::sort(rocks.begin(), rocks.end());

    std::priority_queue<Node> pq;
    std::vector<int> distances;
    std::set<int> indices;

    auto push = [&] (int index, int distance) {
        pq.push({ index, distance });
        distances.push_back(distance);
        indices.insert(index);
    };

    push(0, rocks[0]);
    for (int i = 1; i < rocks.size(); i++) {
        push(i, rocks[i] - rocks[i - 1]);
    }
    push(rocks.size(), last - rocks.back());

    while (n--) {
        Node current;
        std::set<int>::iterator iter;

        do {
            current = pq.top(); pq.pop();
            iter = indices.find(current.index);
        } while (iter == indices.end() || current.distance != distances[current.index]);

        auto prev_iter = (iter == indices.begin()) ? indices.end() : std::prev(iter);
        auto next_iter = std::next(iter);
        bool has_prev = prev_iter != indices.end();
        bool has_next = next_iter != indices.end();

        int to_be_merged, to_erase;

        if (!has_prev || (has_next && distances[*next_iter] < distances[*prev_iter])) {
            to_be_merged = current.index;
            to_erase = *next_iter;
        } else {
            to_be_merged = *prev_iter;
            to_erase = current.index;
        }

        distances[to_be_merged] += distances[to_erase];
        distances[to_erase] = 0;
        indices.erase(to_erase);
        pq.push({ to_be_merged, distances[to_be_merged] });
    }

    int answer = last;

    for (const int index: indices) {
        answer = std::min(answer, distances[index]);
    }

    return answer;
}

정답 코드(이분 탐색, $O(n \log n)$ )

C++17

#include <bits/stdc++.h>

int solution(int distance, std::vector<int> rocks, int n) {
    std::sort(rocks.begin(), rocks.end());
    rocks.push_back(distance);

    int first = 0, last = 2 * distance;

    while (first < last) {
        int mid = (first + last + 1) / 2;
        int removed = 0;
        int prev = 0;

        for (const int rock: rocks) {
            if (mid <= rock - prev) {
                prev = rock;
            } else if (n < ++removed) {
                break;
            }
        }

        if (removed <= n) {
            first = mid;
        } else {
            last = mid - 1;
        }
    }

    return first;
}

[프로그래머스] 43236 징검다리 (C/C++)

문제

풀이

소스 코드

Share this post