[프로그래머스] 12984 지형 편집 (C/C++)

문제

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

풀이

전형적인 Parametric Search 문제이다. 주어진 조건을 만족하는 최적의 높이 값을 찾는 문제로, 이분 탐색이나 삼분 탐색을 통해 해결할 수 있다.

먼저, 직관적으로 총 비용 함수 그래프가 단조 감소 후 단조 증가하는 2차 곡선 형태(Convex)임을 인지했다. 극소값을 구하기 위한 방법으로 경사 하강법(Gradient Descent), 뉴턴-랩슨법(Newton-Raphson Method) 등도 떠올랐지만, 문제 특성상 이분 탐색(Binary Search)과 삼분 탐색(Ternary Search)이 가장 적합하다고 판단했다.

개인적으로, 이분 탐색은 다소 수학적인 접근, 삼분 탐색은 좀 더 논리적인 접근에 가깝다고 생각하는데 공부 겸 비교를 위해, 두 방법을 모두 직접 구현해봤다. 구현에 앞서, 총 비용 함수 $y$ 가 높이 $h$ 에 대해 단조 감소 후 단조 증가하는 형태임을 가볍게(=내 맘대로) 증명해보자.

수학적 증명 (내 맘대로)

한 칸의 땅에 대한 비용 함수를 정의해보자.

어떤 칸이 높이 $land_{ij}$ 를 가지고 있을 때, 해당 칸을 목표 높이 $h$ 로 맞추기 위한 비용 함수 $loss(h, land_{ij})$ 는 다음과 같이 정의할 수 있다.

loss(h, land_{ij}) = \begin{cases} (\,h - land_{ij}\,)\,\ast\,P, & land_{ij} < h,\\[4pt] (\,land_{ij} - h\,)\,\ast\,Q, & land_{ij} \ge h, \end{cases}

이제, $h$ 가 변할 때 이 함수가 어떻게 바뀌는지를 살펴보자.

$land_{ij} < h$ 인 경우: $loss(h, land_{ij}) = (h - land_{ij}) \,\ast\, P$ 이므로, $h$ 가 1 증가할 때마다 비용은 $P$ 만큼 증가한다.
$land_{ij} \ge h$ 인 경우: $loss(h, land_{ij}) = (land_{ij} - h) \,\ast\, Q$ 이므로, $h$ 가 1 증가할 때마다 비용은 $Q$ 만큼 감소한다.

즉, $h$ 가 낮을 때는 비용이 줄어들고, 일정 높이를 지나면 비용이 다시 증가하는 U자형(Convex) 형태를 띠게 된다.

위 식에 대해 조금 더 자세히 보면, $land_{ij} = h$ 에서 꺾이는 절대값 함수( $|land_{ij} - h|$ )와 유사한 선형 함수이고, 연속이지만 미분 불가능하며 좌우에서의 미분값이 각각 $-Q$ 와 $P$ 로 다르다는 점을 알 수 있다.

각 칸의 땅에 대한 비용 함수가 U자형 형태를 띠는 것은 이제 이해됐다. 이제 모든 칸의 땅에 대한 비용 함수를 합친 총 비용 함수 $cost(h)$ 도 같은 형태를 가지는지 직관적으로 생각해보자. 각 칸의 땅에 대한 비용 함수는 $y = x^2$ 그래프와 비슷한 모양을 가진다. 여러개의 2차 함수의 합의 결과는 2차 함수이다. 총 비용 함수는 모든 칸의 비용 함수의 합이다. 이러한 논리로 미루어보아, 총 비용 함수 $cost(h)$ 역시 단조 감소 후 단조 증가하는 U자형 형태를 갖는다고 볼 수 있다.

다음의 총 비용 함수 $cost(h)$ 는 U자형 형태를 가지며 결론적으로 이 함수의 극솟값을 구하는 것이 문제의 목표가 된다.

cost(h) = \sum_{i=0}^{N-1}\sum_{j=0}^{N-1} loss(h, land_{ij})

논리적 접근 (삼분 탐색)

극솟값을 찾는 여러 아이디어가 떠올랐지만, 수학적인 접근을 이산적인 환경에 바로 적용하는 방법은 직관적으로 떠오르지 않았다. 컴퓨터적 관점에서 아이디어를 떠올려보려고 했고 가장 먼저 경사 하강법(Gradient Descent)이 생각났다. 이를 알고리즘으로 표현할 수 있는 방법을 고민하던 중 경사 하강법과 유사한 특성을 가진 삼분 탐색(Ternary Search)이 떠올랐다. 삼분 탐색은 구간을 세 등분해 각 구간의 함수 값을 비교하며, 극솟값이 있을 법한 구간으로 범위를 점점 좁혀나간다. 그 과정은 경사 하강법처럼 낙엽이 천천히 떨어져 가장 낮은 곳에 닿는 모습과도 비슷하다. 아래 이미지는 경사 하강법과 삼분 탐색의 과정을 시각적으로 표현한 것이다.

수학적 접근 (차분 분석 이분 탐색)

이산 환경이기 때문에 완전히 수학적이라고는 할 수 없지만, 비교적 수학적인 접근의 이분 탐색으로도 문제를 해결할 수 있다. 핵심 아이디어는 차분 분석(Difference Analysis)을 통해 총 비용 함수 $cost(h)$ 의 변화량 $dt$ 를 구하고, 이 값을 기준으로 탐색 범위를 좁혀나가는 방식이다.

여기서,

$F(t)$ 는 높이 $t$ 에서의 총 비용 함수,
$S(t)$ 는 높이 $t$ 이하인 땅의 칸 수,
$N$ 은 정사각형의 한 변의 길이,
$P$ , $Q$ 는 각각 높이를 높이는 비용, 낮추는 비용

을 의미한다.

높이가 1씩 증가함에 따라 총 비용의 변화량 $dt$ 는 다음과 같이 정의할 수 있다.

\begin{aligned} dt &= F(t+1) - F(t) \\ &= P \,\ast\, S(t) - Q \,\ast\, (N \,\ast\, N - S(t)) \\ &= (P + Q) \,\ast\, S(t) - Q \,\ast\, N \,\ast\, N \end{aligned}

총 비용이 더 이상 감소하지 않는 시점( $dt \ge 0$ )이 최적 높이 후보가 되며, 이를 식으로 표현하면 다음과 같다.

0 \le dt \quad\Longleftrightarrow\quad \frac{Q \,\ast\, N \,\ast\, N}{P + Q} \le S(t)

해당 인덱스에 해당하는 칸의 값이 높이가 되고 좌, 우 값 일부를 후보 값으로 사용하여 최종 최소 비용을 도출할 수 있다.

+) 풀고나서 생각해보니 각 칸 자체가 어떤 의미를 갖고 있진 않아서 다 뭉뚱그린 누적합을 사용하는 방식으로도 충분히 해결할 수 있었을 것 같다.

소스 코드

차분 분석 이분 탐색 코드

C++17

#include <bits/stdc++.h>

std::vector<long long> flatten(const std::vector<std::vector<int>> &matrix) {
    std::vector<long long> ret;
    const size_t N = matrix.size();

    ret.reserve(N * N);
    for (const auto &vector: matrix) {
        ret.insert(ret.end(), vector.cbegin(), vector.cend());
    }

    std::sort(ret.begin(), ret.end());

    return ret;
}

long long solution(std::vector<std::vector<int>> land, int P, int Q) {
    const long long N = land.size();
    const auto vector = flatten(land);

    // dt = F(t + 1) - F(t)
    //    = P * S(t) - Q * (N * N - S(t))
    //    = (P + Q) * S(t) - Q * N * N

    // 0 <= dt
    // Q * N * N / (P + Q) <= S(t)
    const long long threshold = std::ceil(static_cast<double>(Q * N * N) / (P + Q));
    const long long candidate = (threshold < 1) ? vector.front() : vector[threshold - 1];

    auto loss = [&] (const long long height, const long long target) -> long long {
		return (height < target) ? (target - height) * P : (height - target) * Q;
	};
	auto cost = [&] (const long long target) -> long long {
        auto op = [&] (const long long acc, const long long height) -> long long {
            return acc + loss(height, target);
        };
        return std::accumulate(vector.cbegin(), vector.cend(), 0LL, op);
    };

    const std::vector<long long> candidates = {
        candidate - 2, candidate - 1, candidate, candidate + 1, candidate + 2
    };

    return std::accumulate(
        candidates.cbegin(), candidates.cend(), LLONG_MAX,
        [&] (long long answer, long long target) {
            return (0 <= target) ? std::min(answer, cost(target)) : answer;
        }
    );
}

삼분 탐색 코드