구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다.
📕 목차

1. 도입
2. 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)
3. 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)
4. 팬미팅 (문제 ID: FANMEETING, 난이도: 상)

1. 도입

 

📌 분할 정복(Devide & Conquer)

  • 쉽게 말해, 각개 격파 전략이다.
  • 주어진 문제를 둘 이상의 부분 문제로 나누고, 각 부분 문제의 답으로 전체 문제의 답을 계산해낸다.
  • 부분 문제를 나눌 때는 거의 같은 크기로 나눈다.
  • 일반적으로 3가지 과정으로 구성된다.
    1. 문제를 더 작은 문제로 분할하는 과정(devide)
    2. 각 문제에 대해 구한 답을 원래 문제의 답으로 병합하는 과정(merge)
    3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)
  • 분할 정복을 적용하기 위한 필요 조건
    • 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
    • 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 필요하다.

 

📌 예제: 수열의 빠른 합과 행렬의 빠른 제곱
// 코드 6.1 1부터 n까지의 합을 계산하는 재귀 함수

// 필수 조건: n >= 1
// 결과: 1부터 n까지의 합을 반환한다.
int recursiveSum(int n) {
    if (n == 1) return 1; // 기저 사례: n = 1일 때
    return n + recursiveSum(n - 1);
}

위 문제를 분할 정복을 이용해 fastSum() 함수로 만들어보자.

 

1부터 n까지의 합을 n개의 조각으로 나눈 뒤, 반으로 나누어 n/2개의 조각들로 만들어진 부분 문제 두 개를 만들 수 있다.

$$ \begin{align} fastSum() &= 1+2+\cdots+n \\&= (1+2+\cdots+\frac{n}{2})+((\frac{n}{2}+1)+\cdots+n) \end{align} $$

(n은 짝수)

첫 번째 부분 문제는 fastSum(n/2)로 표현할 수 있지만, 두 번째 부분 문제는 fastSum(x)를 포함하는 형태로 바꿔야 한다.

$$ \begin{align} \frac{n}{2}+1)+\cdots+n &= (\frac{n}{2} + 1) + (\frac{n}{2} + 2) + \cdots + (\frac{n}{2} + \frac{n}{2}) \\&= \frac{n}{2}*\frac{n}{2}+(1+2+\cdots+\frac{n}{2}) \\&= \frac{n}{2}*\frac{n}{2}+fastSum(\frac{n}{2}) \end{align} $$

$$ \begin{align} \therefore fastSum(n) = 2*fastSum(\frac{n}{2})+\frac{n^{2}}{4} (단, n은 짝수) \end{align}$$

n이 홀수인 경우를 처리하기 위해서는 짝수인 n-1까지의 합을 재귀 호출하고 n을 더하면 된다.

 

// 코드 7.1 1부터 n까지의 합을 구하는 분할 정복 알고리즘

// 필수 조건: n은 자연수
// 1부터 n까지의 합을 반환한다
int fastSum(int n) {
    // 기저 사례
    if (n == 1) return 1;
    return (n % 2 == 1) ? fastSum(n - 1) + n
                        : 2 * fastSum(n / 2) + (n / 2) * (n / 2);
}

 

⏲️ 시간 복잡도 분석

  • recursiveSum()의 경우보다 함수 호출 횟수가 절반으로 줄어든다.
  • 책에서는 n을 2진수 표기법을 사용하여 상한이 lg(n)임을 보이고 있다.
    • \( fastSum(1011_{2} = fastSum(1010_{2}) + 11) \)
    • \( fastSum(1010_{2} = fastSum(101_{2})*2 + 25) \)
    • \( fastSum(101_{2} = fastSum(100_{2}) + 5) \)
    • \( fastSum(100_{2} = fastSum(10_{2})*2 + 4) \)
    • \( fastSum(10_{2} = fastSum(1_{2})*2 + 1) \)
    • \( fastSum(1_{2} = 1) \) 
    • 따라서 fastSum() 총 호출 횟수는 n의 이진수 표현 자릿수 + 첫자리를 제외하고 나타나는 1의 개수가 된다.

작년 초에 끄적이던 거

  • 그림으로 파악하면 훨씬 간단하다.
    • 이진 트리 구조 상, 언제나 깊이는 lg(n)으로 제한된다.

 

📌 행렬의 거듭제곱
  • 가장 단순한 행렬의 거듭제곱 A^m (A는 n*n 크기 행렬)
    • 가장 단순한 행렬의 곱셈 알고리즘은 O(N^3)의 시간이 든다.
    • 거듭제곱 A^(m)을 구하기 위해서는 O(N^3 * m)의 시간이 걸린다.
  • 분할 정복 알고리즘
    • A^(m/2) + A^(m/2)

 

// 코드 7.2 행렬의 거듭제곱을 구하는 분할 정복 알고리즘

// 정방행렬을 표현하는 SquareMatrix 클래스
class SquareMatrix;

// n*n 크기의 항등 행렬(identity matrix)을 반환하는 함수
SquareMatrix identity(int n);

// A^m을 반환한다
SquareMatrix pow(const SquareMatrix& A, int m) {
    // 기저 사례: A^0 = I
    if (m == 0) return identity(A.size());
    if (m % 2 > 0) return pow(A, m - 1) * A;
    SquareMatrix half = pow(A, m / 2);
    // A^m = (A^(m/2))^2
    return half * half;
}

기저 사례를 항등 행렬(단위 행렬)로 잡으면 마찬가지로 쉽게 해결할 수 있다.

 

📌 나누어 떨어지지 않을 때의 분할과 시간 복잡도

  • 분할 정복 알고리즘은 가능한 한 절반에 가깝게 문제를 나누려고 한다.
  • 그러나 case에 따라서는 A*A^(m-1)로 나누는 것이 A^(3)*A^(4)처럼 나누는 것보다 효율적일 수 있다.
    • 행렬 거듭제곱에서 m이 홀수일 때 절반으로 바로 나누는 방식이 알고리즘을 더 느리게 만든다.
    • A^(m)을 찾기 위해서 계산해야 할 부분 문제의 수가 늘어나기 때문이다. (중복)

 

📌 예제: 병합 정렬(Merge sort)과 퀵 정렬(Quick sort)

(좌) 병합 정렬 / (우) 퀵 정렬

  • 두 알고리즘 모두 분할 정복 패러다임을 기반해서 만들어졌다.
  • 시간이 많이 걸리는 작업을 분할 단계에서 하느냐, 병합 단계에서 하느냐의 차이가 존재한다.
    • 병합 정렬은 분할에서 O(1)만에 수행 가능하지만, 병합 과정에서 O(N)이 소요된다.
    • 퀵 정렬은 분할에서 O(N)이 걸리고 선택한 기준에 따라 비효율적인 분할을 불러올 수는 있지만, 별도의 병합 작업이 필요없다.

 

⏲️ 시간 복잡도 분석

병합 정렬 수열의 각 항의 길이가 1이 될 때까지 나누는 분할 과정 O(lgn)과 병합 과정 O(n)이 항상 일정하다.
따라서 시간 복잡도는 O(nlgn)이 된다.
퀵 정렬 대부분 부분 문제로 나누는 파티션 과정에서 시간이 소요된다.
파티션에는 주어진 수열의 길이에 비례하는 시간이 걸리므로, 병합 정렬의 병합 과정 O(n)과 같다.
문제는 기준 값인 Pivot에 의해 분할도니 부분 문제가 비슷한 크기로 나누어진다는 보장이 불가능하다.
따라서 퀵 정렬의 최악의 경우는 O(n^2)이고, 평균적으로 부분 문제가 절반에 가깝게 나누어지면 O(nlgn)만큼의 시간이 소요된다.

 

📌 예제: 카라츠바(Karatsuba)의 빠른 곱셈 알고리즘
  • 수백, 수만 자리의 큰 숫자를 표현하는 배열의 곱셈에서 사용한다.

 

🟡 두 정수의 곱을 구하는 로직 : O(N^2)

(좌) 기존 방식 / (우) 순서 

// 코드 7.3 두 큰 수를 곱하는 O(n^2) 시간 알고리즘

// num[]의 자릿수 올림을 처리한다
void normalize(vector<int>& num) {
    num.push_back(0);

    // 자릿수 올림을 처리한다
    for (int i = 0; i < num.size(); i++) {
        if (num[i] < 0) {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i + 1] -= borrow;
            num[i] += borrow * 10;
        } else {
            num[i + 1] += num[i] / 10;
            num[i] %= 10;
        }
    }

    while (num.size() > 1 && num.back() == 0) num.pop_back();
}

// 두 긴 자연수의 곱을 반환한다
// 각 배열에는 각 수의 자릿수가 1의 자리에서부터 시작해 저장되어 있다
// 예 : multiply({3, 2, 1}, {6, 5, 4}) = 123 * 456 = 56088 = {8, 8, 0, 6, 5}
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() + 1, 0);
    for (int i = 0; i < a.size(); i++) 
        for (int j = 0; j < b.size(); j++) 
            c[i + j] += a[i] * b[j];
    normalize(c);
    return c;
}
  • 정수 배열을 뒤집으면 입출력할 때는 불편하지만, 자릿수 표현과 연산이 쉬워진다.
  • 위 알고리즘의 시간 복잡도는 두 정수 길이가 모두 n일 때, O(n^2)가 된다. (2중 반복만 봐도 자명한 사실)

normalize() 함수에서 '음수인 경우를 처리하는 게 대체 왜 필요하지?'라는 의문이 계속 떠올랐는데, 카라츠바 알고리즘 전체를 보고 나면 이해할 수 있다.

 

🟡 카라츠바 알고리즘 : O(N^(lg3))

// 코드 7.4 카라츠바의 빠른 정수 곱셈 알고리즘

// a += b * (10^k)를 구현한다
void addTo(vector<int>& a, const vector<int>& b, int k) {
    int length = b.size();
    a.resize(max(a.size() + 1, b.size() + k));
    for (int i = 0; i < length; i++) 
        a[i + k] += b[i];
    normalize(a); // 정규화
}

// a -= b; 를 구현한다. a >= b를 가정한다
void subFrom(vector<int>& a, const vector<int>& b) {
    int length = b.size();
    a.resize(max(a.size() + 1, b.size()) + 1);
    for (int i = 0; i < length; i++) 
        a[i] -= b[i];
    normalize(a); // normalize()가 음수를 처리하는 이유
}

// 두 긴 정수의 곱을 반환한다
vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
    int an = a.size(), bn = b.size();

    // a가 b보다 짧을 경우 둘을 바꾼다
    if (an < bn) return karatsuba(b, a);
    // 기저 사례: a나 b가 비어 있는 경우
    if (an == 0 || bn == 0) return vector<int>();
    // 기저 사례: a가 비교적 짧은 경우 O(n^2) 곱셈으로 변경한다
    if (an <= 50) return multiply(a, b);

    int half = an / 2;
    // a와 b를 밑에서 half 자리와 나머지로 분리한다
    vector<int> a0(a.begin(), a.begin() + half);
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
    vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

    // z2 = a1 * b1
    vector<int> z2 = karatsuba(a1, b1);
    // z0 = a0 * b0
    vector<int> z0 = karatsuba(a0, b0);
    // a0 = a0 + a1; b0 = b0 + b1
    addTo(a0, a1, 0); addTo(b0, b1, 0);
    // z1 = (a0 * b0) - z0 - z2;
    vector<int> z1 = karatsuba(a0, b0);
    subFrom(z1, z0);
    subFrom(z1, z2);
    // ret = z0 + z1 * 10^half + z2 * 10^(half*2)
    vector<int> ret;
    addTo(ret, z0, 0); addTo(ret, z1, half); addTo(ret, z2, half + half);
    return ret;
}

1. 두 수 a, b를 절반으로 쪼갠다.

예를 들어, a와 b가 각각 256자리 수라면 a1, b1는 첫 128자리, a0, b0는 그 다음 128자리를 저장한다. 

$$ \begin{align} a = a_{1}*10^{128} + a_{0} \end{align} $$

$$ \begin{align} b = b_{1}*10^{128} + b_{0} \end{align} $$

 

2. a*b를 네 개의 조각을 이용해 표현한다.

$$ \begin{align} a*b &= (a_{1}*10^{128}+a_{0})*(b_{1}*10^{128}+b_{0}) \\&= a_{1}*b_{1}*10^{256}+(a_{1}*b_{0}+a_{0}*b_{1})*10^{128} + a_{0}*b_{0} \end{align} $$

여기서 10의 거듭제곱과 곱셈 과정은 0을 붙이는 Shift 연산으로 구현하면 되니 곱셈으로 치지 않는다.

  • 길이 n인 두 정수를 곱하는데 드는 시간(덧셈과 시프트 연산) : O(n)
  • n/2 길이 조각 곱셈 네 번

문제는 길이 n인 두 정수를 곱하는데 드는 시간이 \(T(n) = O(n) + 4*T(\frac{n}{2})\)이므로, 

전체 시간 복잡도는 O(n^2)이 된다.

 

3. 네 개의 조각을 세 번의 곱셈으로 계산할 수 있다!

$$ \begin{align} a*b=\underset{z_{2}}{\underbrace{a_{1}*b_{1}}}*10^{256}+ \underset{z^{1}}{\underbrace{a_{1}*b_{0}+a_{0}*b_{1}}}*10^{128}+\underset{z^{0}}{\underbrace{a_{0}*b_{0}}} \end{align} $$

  • 조각들의 곱을 각각 z_2, z_1, z_0라고 정의한다.
  • 우선 z_0와 z_2를 각각 한 번의 곱셈으로 구한다.

 

$$ \begin{align} (a_{0}+a_{1})+(b_{0}+b_{1}) &= \underset{z_{0}}{\underbrace{a_{0}*b_{0}}} + \underset{z^{1}}{\underbrace{a_{1}*b_{0}+a_{0}*b_{1}}}*10^{128}+\underset{z^{2}}{\underbrace{a_{1}*b_{1}}} \\&= z_{0}+z_{1}+z_{2} \end{align} $$

  • 중간의 두 번의 곱셈을 z_0와 z_2를 빼서 한 번의 곱셈으로 줄일 수 있다.
z2 = a1 * b1;
z0 = a0 * b0;
z1 = (a0 + a1) * (b0 + b1) - z0 - z2;

위의 세 결과를 적절히 조합하면 두 수의 답을 구해낼 수 있으며 최종 구현은 위의 코드와 같다.

 

천재다 천재..

다른 예로는 스트라센(Strassen)의 행렬 곱셈 알고리즘이 있는데, 기회가 되면 분석해봐야겠다.

 

⏲️ 시간 복잡도 분석

  • 두 개의 입력을 절반씩 쪼갠 뒤, 세 번의 재귀 호출을 하고 있다.
  • 병합 단계
    • addTo()와 subFrom() 수행 시간에 지배된다.
    • 둘 다 숫자의 길이에 비례하는 시간만이 걸리도록 구현할 수 있다.
  • 기저 사례
    1. multiply() 수행 시간에 지배된다.
    2. (기저 사례를 한 자리수로 가정하면)자릿수 n이 2의 거듭제곱 2^k일 때, 재귀 호출 깊이는 k가 된다.
      • 입력의 크기가 2^k보다 작아도 2^k가 될 때까지 앞쪽에 0을 덧대면 되므로 시간 복잡도 분석은 유효하다.
      • k = lg(n)
    3. 한 번 쪼갤 때마다 곱셈의 수가 세 배씩 늘어나므로 마지막 단계에는 3^k개의 부분 문제가 있다.
    4. 마지막 단계에서는 두 수 모두 한 자리이므로 곱셈 한 번으로 해결할 수 있다.
    5. 따라서 곱셈의 수는 O(3^k)가 된다. ⇒ O(3^lg(n)) = O(n^(lg3))
    6. lg3 ≅ 1.585 이므로, n이 10만일 때 O(N^2)과 100배 차이가 난다.
  • 결론
    • 단계가 내려갈 수록 숫자의 길이는 1/2, 부분 문제의 개수는 세 배가 되므로, i번째 단계에서 연산의 수는 \((\frac{3}{2})^{i}*n\)이 된다.
    • 모든 단계에서 필요한 전체 연산의 수 : \(n*\sum_{lgn}^{i=0}(\frac{3}{2})^{i} \) → n^(lg3)에 비례하다.
    • 곱셈이 시간복잡도를 지배하며, 최종 시간 복잡도는 \(O(n^{lg3})\)가 된다.

단, 입력의 크기가 작을 때는 O(N^2)보다 느린 경우가 많다는 데 주의해야 한다.

 

2. 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)

 

📌 문제
 

algospot.com :: QUADTREE

쿼드 트리 뒤집기 문제 정보 문제 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적

algospot.com

  • 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 기법 중 하나
  • 주어진 공간을 항상 4개로 분할해 재귀적으로 표현한다.

 

📌 풀이

1️⃣ 접근 방법

무식하게 해결하기엔 원본 그림 크기 최대 경우으 2^20 * 2^20 이므로 엄두도 낼 수 없다.

이럴 땐 대개 둘 중 하나를 택한다.

  1. 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
  2. 작은 입력에 대해서만 동작하는 알고리즘부터 최적화해 나가기

둘 중 무엇이 더 낫다고 결코 이야기할 수 없지만, (2)번의 접근 방법이 더 쉽긴 하다.

(1)번의 접근 방식을 함부로 택했다간 생각의 우주에 갇히게 된다...

 

2️⃣ 쿼드 트리 압축 풀기

char decompressed[MAX_SIZE][MAX_SIZE];
void decompress(string::iterator& it, int y, int x, int size);

만약 압축을 전부 풀어서 원본을 얻는 (무식한) 방법을 구현한다고 가정해보자.

기저 사례는 문자열 s 시작이 w나 b인 경우고, x라면 decompress()로 재귀 호출을 통해 넷으로 쪼갠다.

→ 문자열 길이가 제각각인데 어떻게 쪼갤 것인가?

 

3️⃣ 압축 문자열 분할하기

// 코드 7.5 쿼드 트리 압축을 해제하는 재귀 호출 알고리즘

char decompressed[MAX_SIZE][MAX_SIZE];
void decompress(string::iterator& it, int y, int x, int size) {
    // 한 글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다
    char head = *(it++);
    // 기저 사례: 첫 글자가 b 또는 w인 경우
    if (head == 'b' || head == 'w') {
        for (int dy = 0; dy < size; dy++) 
            for (int dx = 0; dx < size; dx++) 
                decompressed[y + dy][x + dx] = head;
    } else {
        int half = size / 2;
        // 네 부분을 각각 순서대로 압축 해제한다
        decompress(it, y, x, half);
        decompress(it, y, x + half, half);
        decompress(it, y + half, x, half);
        decompress(it, y + half, x + half, half);
    }
}

iterator을 참조자 형태로 넘김으로써 필요한 만큼 문자열을 읽어 반복자를 옮겼다면, 다음 재귀 호출에서도 반복자는 항상 다음 부분의 시작 위치를 가리키게 된다.

문제는 이걸 곧이 곧대로 다 풀고 있기엔 크기가 너무 크다는 점이다.

 

4️⃣ 압축 다 풀지 않고 뒤집기

// 코드 7.6 쿼드 트리 뒤집기 문제를 해결하는 분할 정복 알고리즘

string reverse(string::iterator& it) {
    char head = *(it++);
    if (head == 'b' || head == 'w') return string(1, head);
    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);
    // 각각의 네 부분을 반대로 잘 합친다
    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

다행히 위에서 내가 떠올린 로직이랑 똑같다. :)

 

재귀를 통해 쪼개지지 않은 경우를 굳이 뒤집을 이유는 없다.

따라서 가장 아래 단계의 4분할 된 시점부터 차례차례 상하를 반전시켜 올라오면, 최종적으로 압축된 상태에서 이미지를 반전시킬 수 있게 된다!

 

⏲️ 시간 복잡도 분석

  • reverse()가 한 번 호출될 때마다 주어진 문자열의 한 글자씩을 사용한다.
  • 따라서 함수가 호출되는 횟수는 문자열의 길이에 비례하므로 O(n)이 된다.

 

3. 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중)

 

📌 문제 
 

algospot.com :: FENCE

울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체

algospot.com

이 문제 너무 많이 봐서 문제를 외워버렸다.

내가 코딩 시작하고 처음 봤던 알고리즘이 백 트래킹을 적용한 DFS 였고,

두 번째가 울타리 잘라내기를 푸는 4가지 방법.

브루트 포스, 재귀 호출, 다이나믹 프로그래밍, 스택을 이용한 선형 시간 알고리즘이었다.

 

C언어도 미숙하던 그때의 나에게 이 알고리즘들을 설명하던 친구의 심정을 아직도 나는 헤아릴 수가 없다...

 

📌 풀이

1️⃣ 접근 방법 - 무식하게 풀 수 있을까?

// 코드 7.7 울타리 잘라내기 문제를 해결하는 O(n^2) 알고리즘

// 판자의 높이를 담은 배열 h[]가 주어질 때 사각형의 최대 너비를 반환한다
int bruteForce(const vector<int>& h) {
    int ret = 0;
    int N = h.size();
    // 가능한 모든 left, right 조합을 순회한다
    for (int 수비 = 0; 수비 < N; 수비++) {
        int minHeight = h[수비];
        for (int 희진 = 수비; 희진 < N; 희진++) {
            minHeight = min(minHeight, h[희진]);
            ret = max(ret, (희진 - 수비 + 1) * minHeight);
        }
    }
    return ret;
}

울타리 하나씩 붙잡고 옆으로 늘려보면서 최대의 경우를 찾아보면 된다.

이중 반복이 나오는 것만으로 O(n^2)의 시간이 걸릴 것임을 예측할 수 있다.

 

2️⃣ 분할 정복 알고리즘의 설계

어떻게 분할할지를 먼저 결정해야 한다.

  • 가장 큰 직사각형을 왼쪽 부분 문제에서만 잘라낸다.
  • 가장 큰 직사각형을 오른쪽 부분 문제에서만 잘라낸다.
  • 가장 큰 직사각형은 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있다.

왼쪽과 오른쪽은 재귀로 해결할 수 있으니, 걸친 부분만 해결할 수 있다면 분할 정복 알고리즘은 완성된다.

 

3️⃣ 양쪽 부분 문제에 걸친 경우의 답

// 코드 7.8 울타리 잘라내기 문제를 해결하는 분할 정복 알고리즘

// 각 판자의 높이를 저장하는 배열
vector<int> h;
// h[left..right] 구간에서 찾아낼 수 있는 가장 큰 사각형의 넓이를 반환한다
int solve(int left, int right) {
    // 기저 사례: 판자가 하나밖에 없는 경우
    if (left == right) return h[left];
    // [left, mid], [mid + 1, right]의 두 구간으로 문제를 분할한다
    int mid = (left + right) / 2;
    // 분할한 문제를 각개격파
    int ret = max(solve(left, mid), solve(mid + 1, right));
    // 부분 문제 3: 두 부분에 모두 걸치는 사각형 중 가장 큰 것을 찾는다
    int lo = mid, hi = mid + 1;
    int height = min(h[lo], h[hi]);
    // [mid, mid + 1]만 포함하는 너비 2인 사각형을 고려한다
    ret = max(ret, height * 2);
    // 사각형이 입력 전체를 덮을 때까지 확장해 나간다
    while (left < lo || hi < right) {
        // 항상 높이가 더 높은 쪽으로 확장한다
        if (hi < right && (lo == left || h[lo - 1] < h[hi + 1])) {
            ++hi;
            height = min(height, h[hi]);
        } else {
            --lo;
            height = min(height, h[lo]);
        }
        // 확장한 후 사각형의 넓이
        ret = max(ret, height * (hi - lo + 1));
    }
    return ret;
}

max(부분문제1(), 부분문제2())로 재귀를 호출하여 문제를 해결하고, 최종적으로 두 부분 모두 걸치는 직사각형을 탐색하면 된다.

mid, mid+1 중에 높이가 낮은 판자를 기준으로 좌우로 확장하는데, 더 높은 판자를 포함하도록 확장시켜보면 된다.

 

 

4️⃣ 정당성 증명

양쪽 부분 문제에 걸쳐 있는 직사각형을 찾을 때, 각 단계마다 더 높은 판자를 택하는 것이 항상 옳은가?

귀류법을 통해 증명할 수 있다.

  1. 어떤 사각형 R이 이 과정을 통해 찾은 최대 직사각형보다 더 크다고 가정한다.
  2. 너비가 2인 사각형에서 시작하여 한 칸씩 사각형의 너비를 늘려가면, 기존의 가정으로 구한 사각형들 중 R과 너비가 같은 사각형 R'이 반드시 존재한다. (두 사각형은 항상 겹치는 부분이 존재한다.)
  3. 너비가 같으므로 R이 더 넓음을 보이려면 R'보다 반드시 높아야 한다.
    • 즉, R의 모든 울타리 높이는 R'의 높이를 결정짓는 A보다 높아야 한다.
  4. R'이 A를 택하는 경우는 A보다 낮거나 높이가 같은 판자가 왼쪽에 있는 경우다.
    • 만약, R이 존재할 수 있었다면 R'은 A를 고르지 않고 왼쪽으로 확장했을 것이다.
  5. 따라서 R이 존재할 수 있다는 가정은 모순이다.

 

⏲️ 시간 복잡도 분석

문제를 2개로 나누고, 너비가 2인 사각형에서 너비가 n인 사각형까지를 하나씩 검사하므로 분할 ln(n)과 탐색 n의 시간을 곱하면 최종 시간복잡도는 \( O(nlgn) \)이다.

 

📌 선형 시간 알고리즘
 

알고리즘 문제를 풀면서 생각해보아야 할 것들

이제 1년하고 1달 조금 넘게 코딩을 하면서, 알고리즘이라고는 실버 2주, 골드 1달, 플래티넘 1달 정도밖에 풀어보지 않은 짬밥에 뭘 얼마나 유용한 걸 설명할 수 있을 지는 모르겠지만 그래도 내

jaeseo0519.tistory.com

이 알고리즘을 다룰려면 한참 나중의 이야기겠지만, 이 문제는 스택을 이용한 선형 시간 알고리즘으로 해결할 수 있다.

 

4. 팬미팅 (문제 ID: FANMEETING, 난이도: 상)

 

📌 문제
 

algospot.com :: FANMEETING

팬미팅 문제 정보 문제 가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가

algospot.com

양쪽의 배열에서 남자 멤버와 남성팬이 만나는 경우만 걸러내면 된다.

 

📌 풀이

가장 무식한 방법은 그림에 나온대로 로직을 구현해버리면 된다.

팬의 수 N, 멤버 수 M이라고 할 때, 대략 O(NM-M^2)정도가 필요하다. (멤버와 팬이 전부 안 겹치는 경우가 M^2)

물론 이렇게 구현하면 바로 time out이 뜰 것이다.

 

1️⃣ 곱셈으로의 변형

  • 두 큰 수의 곱셈으로 해결하는 것이 가장 빠르다.
  • 남자는 1, 여자는 0으로 값을 치환한다.

 

$$ \begin{align} C_{i} = A_{0}*B_{i} + A_{1}*B_{i-1} + A_{2}*B_{i-2} \end{align} $$

그리고 연산을 위해 A의 원소를 뒤집을 필요가 있다.

$$ \begin{align} C_{i} = A_{2}*B_{i} + A_{1}*B_{i-1} + A_{0}*B_{i-2} \end{align} $$

이 부분이 처음에 이해가 잘 안 갔었는데, 너무 당연한 거였다.

 

여기서 "곱한다"라는 행위는 곧 "남자 멤버와 남자 팬이 만나는 경우"를 판단하기 위함이다. (유일하게 1이 나옴)

그런데 팬의 배열 MMMFFF를 그대로 111000상태로 두고 곱하면 멤버가 남성이 아닌 가장 뒤의 여성팬부터 만나게 되므로, 팬의 배열을 뒤집어줄 필요가 있다.

https://dontdiethere.tistory.com/80

혹여나 위 연산이 이해가 안 간다면 이렇게 생각하면 쉽다.

가장 처음의 가로줄 000111은 첫 번째 남성팬의 흔적이고, 다음의 가로줄 000111은 두 번째 남성팬의 흔적이다. (여성팬은 무조건 0밖에 없으므로 생략)

세로줄은 특정 순간(i)을 가리킨다.

즉, 세로줄의 합 C_i는 특정 순간에서 악수가 일어난 횟수(남자 멤버와 남자 팬이 만난 경우)와 같다.

 

2️⃣ 카라츠바 알고리즘을 이용한 구현

N, M이 최대 20만이므로 이전에 배웠던 카라츠바 알고리즘을 적용할 수 있다.

이 알고리즘의 수행 시간은 두 수의 곱셈에 좌우되므로 O(n^(ln3))이 된다.

// 카라츠바의 빠른 정수 곱셈 알고리즘을 이용해 팬미팅 문제를 해결하는 함수

vector<int> karatsuba(vector<int>& a, vector<int>& b);

int hugs(const string& members, const string& fans) {
    int N = members.size(), M = fans.size();
    vector<int> A(N), B(M);
    for (int i = 0; i < N; ++i) A[i] = (members[i] == 'M');
    for (int i = 0; i < M; ++i) B[M - i - 1] = (fans[i] == 'M');
    // 카라츠바 알고리즘에서 자리 올림은 생략한다
    vector<int> C = karatsuba(A, B);
    int allHugs = 0;
    for (int i = N - 1; i < M; ++i)
        if (C[i] == 0)
            ++allHugs;
    return allHugs;
}

 

저작자표시 비영리

티스토리툴바