참조

개요

시간복잡도: $ O(N) $

공간복잡도: $ O(N) $

• N은 명령의 수이다.

문제 풀이

이 문제는 말 그대로 스택 그 자체이다. 여기 에서 설명한 5가지 연산만 수행하면 끝이다.

구현

특히나 이 문제는 코딩의 순서를 문제에서 주어진 5가지 명령에 쓰인 그대로 코딩하면 되는 문제이니, 자세한 설명은 생략하겠다.

#include <stack>
#include <string>
#include <iostream>

using namespace std;

int main_10828() {
    freopen("input.txt", "r", stdin); // 문제의 입력을 일일이 치기 귀찮을 때 쓰는 방법이다.
    ios::sync_with_stdio(false);    cin.tie(NULL);

    int n;
    stack<int> st;

    cin >> n;

    while (n--) {
        string order;
        cin >> order;
        if (order == "push") {            // push 명령 처리
            int e;
            cin >> e;
            st.push(e);
        }
        else if (order == "pop") {        // pop 명령 처리
            if (st.empty())
                cout << -1 << '\n';
            else {
                cout << st.top() << '\n';
                st.pop();
            }
        }
        else if (order == "size") {       // size 명령 처리
            cout << st.size() << '\n';
        }
        else if (order == "empty") {      // empty 명령 처리
            cout << int(st.empty()) << '\n';
        }
        else {                            // top 명령 처리
            if (st.empty())
                cout << -1 << '\n';
            else
                cout << st.top() << '\n';
        }
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 틀린다. 그대로 제출하지 말라는 뜻이다. 무언가를 바꿔 주어야 한다.

참조

개요

시간복잡도: $ O(TC \cdot L) $

공간복잡도: $ O(L) $

• TC는 테스트 케이스의 수, L은 문자열의 길이이다.

문제 풀이

괄호 짝 맞추기는 스택 문제의 단골손님이다.
이 문제의 핵심 아이디어는 다음과 같다.

• 문자열을 하나씩 읽는다.
  • 여는 괄호 ( 가 나오면 스택에 집어넣는다.
  • 닫는 괄호 ) 가 나오면 괄호 하나를 빼낸다.
    • 이때 스택이 비어 있으면 잘못된 것이다. NO를 출력한다.
• 문자열을 다 읽고 나서 스택이 비어 있어야만 제대로 된 Parenthesis String이다. YES를 출력한다.
  • 스택에 뭔가 들어 있으면 NO를 출력한다. 이 부분이 실수가 가장 많이 나오는 부분이다.
• 각 테스트 케이스마다 스택을 clear시켜줘야 한다. 안 그러면 wrong answer를 받을 것이다.

구현

이 문제에는 적용 가능한 트릭이 몇 가지 있다. 코딩을 간단하게 만들 수 있다.

• 이 문제는 스택에 집어넣는 것이 오직 여는 괄호 ( 하나 뿐이다. 그럼 굳이 스택을 쓸 것도 없이, 쌓인 여는 괄호의 수를 세어 줄 변수 n 하나만 있으면 된다.
• 각 문자마다 검사할 때, 닫는 괄호 ) 가 나오면 일단 n을 감소시킨다. 그리고 n이 0보다 작아지면, 바로 중단한다.
  • 그러면 마지막에서 n이 0인지만 보면 YES / NO 를 판별할 수 있다.

#include <string>
#include <iostream>

using namespace std;

int main_09012() {
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);    cin.tie(NULL);

    int TC;

    cin >> TC;
    while (TC--) {
        int n = 0;
        string str;
        cin >> str;
        for (auto s : str) {
            if (s == '(')
                ++n;
            else 
                --n;
            if (n < 0)break;
        }
        cout << (n ? "NO" : "YES") << '\n';
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 틀린다. 그대로 제출하지 말라는 뜻이다. 무언가를 바꿔 주어야 한다.

sharifa_header.h

코드

필자가 만든 라이브러리…라고 하기는 좀 그렇고, 그냥 헤더 파일이랑 #define 약간을 모아 놓은 헤더 파일이다.
필자의 코드에서 처음 보는 토큰들이 좀 있을 텐데, 잘 모르겠다면 위의 링크를 참조하면 된다.

예를 들면, ll은 long long이다.

bit_library.h

코드

비트 관련 사용자 정의 함수를 모아 놓은 헤더 파일이다.
bit 연산을 안다면 코드를 보고 이해할 수 있으므로 따로 설명하지는 않겠다.

conversion_library.h

코드

어떤 데이터 타입 변수를 다른 데이터 타입 변수로 바꾸는 함수들을 모아 놓았다.
예를 들어 string_to_vi 함수는 “1236”과 같은 string을 vector<int>로 변환한다.

참조

개요

시간복잡도: $ O(N log N) $

공간복잡도: $ O(N) $

• N은 두 수열의 길이의 max값이다.
• FFT는 convolution을 빠르게 해 주는 것이지만, PS에서는 거의 대부분 곱셈을 빠르게 하기 위해 쓰인다.

이 글에서는 FFT(고속 푸리에 변환)을 설명한다.
이론적인 부분에 대한 자세한 설명은 topology-blog에 잘 되어 있으므로 생략한다.

알고리즘

큰 수의 곱셈을 수행할 때 FFT의 개략적인 설명은 다음과 같이 적어 두었다.

1. 각 수열을 먼저 reverse시킨다. $ O(N) $
2. 각 수열에 푸리에 변환을 적용한다. $ O(N log N) $
3. 푸리에 변환을 적용하면 convolution을 단순 곱셈으로 변환시킬 수 있으므로, 2의 결과물을 element-wise 곱셈을 시킨다. $ O(N) $
4. 3의 결과물을 푸리에 역변환을 시킨다. $ O(N log N) $
5. 1에서 reverse를 시켰으므로, 다시 reverse를 시켜준다. $ O(N) $

FFT의 핵심 부분은 2~4번 부분이다. 1번과 5번은 우리가 수를 쓸 때 앞부분에 큰 자리 수를 적기 때문에 필요하다.

구현

다음과 같다. FFT 구현과 출력 함수만 정의되어 있으므로, 따로 설명하진 않겠다.

다만 주의할 점이 하나 있는데, 출력 함수에서 곱하는 두 수가 0인 경우 예외 처리를 해주어야 한다.

/*
fft 함수는 http://topology-blog.tistory.com/6 블로그를 참조한 것입니다.
*/

#pragma once

#include "sharifa_header.h"
#include "bit_library.h"

typedef complex<double> base;

void fft(vector<base> &a, bool inv) {
    int n = (int)a.size();
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        while (!((j ^= bit) & bit)) bit >>= 1;
        if (i < j) swap(a[i], a[j]);
    }
    for (int i = 1; i < n; i <<= 1) {
        double x = (inv ? 1 : -1) * M_PI / i;
        base w = { cos(x), sin(x) };
        for (int j = 0; j < n; j += i << 1) {
            base th(1);
            for (int k = 0; k < i; k++) {
                base tmp = a[i + j + k] * th;
                a[i + j + k] = a[j + k] - tmp;
                a[j + k] += tmp;
                th *= w;
            }
        }
    }
    if (inv) {
        for (int i = 0; i < n; i++) a[i] /= n;
    }
}

vector<int> multiply(vector<int> &A, vector<int> &B) {
    vector<base> a(A.begin(), A.end());
    vector<base> b(B.begin(), B.end());
    int n = power_of_2_ge_than(max(a.size(), b.size())) * 2;

    a.resize(n);	b.resize(n);
    fft(a, false);	fft(b, false);

    for (int i = 0; i < n; i++)
        a[i] *= b[i];
    fft(a, true);

    vector<int> ret(n);
    for (int i = 0; i < n; i++)
        ret[i] = (int)round(a[i].real());
    return ret;
}

BOJ 13277(큰 수 곱셈) 문제 풀이

문제: BOJ 13277(큰 수 곱셈)

풀이: BOJ 13277(큰 수 곱셈) 문제 풀이

참조

개요

시간복잡도: $ O(TC \cdot N) $

공간복잡도: $ O(N) $

• N은 직사각형의 수, TC는 테스트 케이스의 수이다. 즉 사실상 $ O(N) $이다.

이 글에서는 히스토그램에서 가장 큰 직사각형의 가장 빠른 풀이인 스택을 활용한 풀이를 설명한다.
이 문제는 BOJ 사이트 맨 아래에 적혀 있는 대로 세그먼트 트리($O(N log N)$), 분할 정복($O(N log N)$) 등으로도 풀 수 있다.

문제 풀이

개인적으로 스택 활용 문제 중 가장 멋있는 문제라고 생각…

이 문제는 처음 봤을 때는 스택이라는 것을 떠올리기가 굉장히 까다롭다. 하지만 가장 멋있는 풀이 방법이니 꼭 익혀두도록 하자.

우선 $O(N^2)$ 풀이부터 생각해 보자.

$O(N^2)$ 풀이: 그냥 풀기

사실 이 풀이는 별 것 없다. N개의 직사각형이 있으니, [0, N) 구간이라고 생각하고, 모든 구간의 넓이를 다 구해보는 것이다. 그리고 최댓값을 찾는다.

1. [0, 1) 부터 [0, 2), [0, 3), …, [0, N) 구간을 검사한다. 각 구간 최댓값을 유지하면서 차례로 검사한다.
2. [1, 2) 부터 [1, 3), [1, 4), …, [1, N) 구간을 검사한다. 각 구간 최댓값을 유지하면서 차례로 검사한다.
3. …
4. [N-1, N) 구간을 검사한다. 각 구간 최댓값을 유지하면서 차례로 검사한다(하나뿐이지만).
5. 이 중 최댓값을 찾는다.

당연히 $O(N^2)$ 풀이는 시간 초과를 얻는다. 이를 $O(N)$으로 줄이기 위해서는, 한 칸씩 검사할 때마다 $O(N)$에 해당하는 구간을 검사해야 한다.
그리고 이를 가능하게 해 주는 것이 스택이다.

$O(N)$ 풀이: 스택

이 풀이를 어떻게 생각해냈을까라는 생각은 잠시 접어두고, 우선 풀이를 보자.

1. 스택을 하나 생성하고, 답(ans)은 0으로 초기화해 둔다.
2. 0번째 직사각형을 처리한다. (첫 번째 직사각형이지만, 0으로 시작하는 것이 편하다)
   1. 0번째는 우선 스택에 집어넣어 둔다. 이 때 pair<int, int>를 사용하여, (위치, 직사각형의 높이)를 같이 저장한다.
3. i번째 직사각형을 처리한다.
   1. 이때 스택에는 몇 개인지는 모르지만 (위치, 직사각형의 높이) 쌍이 몇 개 들어 있을 것이다.
   2. 스택의 top element의 높이와 i번째 직사각형의 높이를 비교한다. top element를 (top_index, top_height), i번째 직사각형을 (i_index, i_height)라고 하자.
   3. top_height <= i_height이면(혹은 3.iv.b에서 다 제거해버려서 스택이 비었으면) (최소 위치, 직사각형의 높이) 쌍을 스택에 집어넣고 (i+1)번째 직사각형으로 넘어간다.
      1. top_height == i_height이면 집어넣지 않아도 상관없지만, 코드가 복잡해지므로 그냥 한 번에 처리한다.
      2. 최소 높이란, min(i_height, 마지막으로 제거한 top_height)를 의미한다. 제거한 적이 없으면 그냥 i_height이다.
   4. top_height > i_height이면, 다음을 수행한다.
      1. (i_index - top_index) * top_height와 ans의 max값을 ans에 넣는다.
      2. top element를 제거한다. 이때 top_height는 임시저장한다.
   5. 모든 직사각형을 처리했으면, 남은 스택의 top element에 대해서 iv의 동작을 반복한다.
      1. 이때 i_index 대신 n을 사용한다.

이것이 알고리즘의 전부이다.
BOJ의 예시(2 1 4 5 1 3 3)를 적용해 보자. 아래 그림은 BOJ에서 가져온 것이다.

1. 스택을 하나 생성하고, ans 변수는 0으로 초기화해 둔다.
2. 0번째 직사각형을 처리한다.
   1. (0,2)를 저장한다.
3. 1번째 직사각형을 처리한다.
   1. (0,2)가 스택에 있다.
   2. (0,2)와 (1,1)을 비교한다. 1번째 직사각형이 top element보다 더 작다.
      1. (i_index - top_index) * top_height = (1-0)*2 = 2를 ans에 저장한다.
         • 이것은 0번째 직사각형만을 사용하여 잘라낸 직사각형을 의미한다. 너비 1, 높이 2짜리 직사각형이다.
      2. (0,2)를 스택에서 제거한다. 이때 최소 위치는 0이 된다.
   3. 스택이 비었으므로 (0,1)을 집어넣고((1,1)이 아니다!) 다음으로 넘어간다.
      • 이것의 의미는 다음과 같다. 위치는 0, 높이는 1을 집어넣었다. 이는 1번째 직사각형을 포함하는(높이 1 이상) 잘라낸 직사각형의 왼쪽 끝은 0이 된다는 뜻이다.
      • 그림을 보면 이해가 될 것이다. 0,1번째 직사각형 모두에서 잘라낼 때 최대 높이는 1이다.
4. 2번째 직사각형을 처리한다.
   1. (0,1)이 스택이 있다.
   2. (0,1)과 (2,4)를 비교한다. 2번째 직사각형이 top element보다 더 크다.
   3. (2,4)를 스택에 넣고 다음으로 넘어간다.
5. 3번째 직사각형을 처리한다.
   1. (0,1)과 (2,4)가 스택에 있다.
   2. (2,4)와 (3,5)를 비교한다. (3,5)를 스택에 넣고 다음으로 넘어간다.
6. 4번째 직사각형을 처리한다.
   1. (0,1), (2,4), (3,5)가 스택에 있다.
   2. (3,5)와 (4,1)을 비교한다. 4번째 직사각형이 더 작다.
      1. (4-3)*5 = 5를 ans에 저장한다.
         • 3번째 직사각형만을 사용하여 잘라낸 것을 의미한다.
      2. (3,5)를 스택에서 제거한다. 최소 위치를 3으로 업데이트한다.
   3. (2,4)와 (4,1)을 비교한다. 이번에도 4번째 직사각형이 더 작다.
      1. (4-2)4 = 8을 ans에 저장한다(이것이 이 예시의 정답이다*).
         • 2,3번째 직사각형을 사용하여 잘라낸 것을 의미한다.
      2. (2,4)를 스택에서 제거한다. 최소 위치를 2로 업데이트한다.
   4. (0,1)과 (4,1)을 비교한다. 높이가 같으므로 (2,1)((4,1)이 아니다!)을 스택에 집어넣고(넣지 않아도 된다) 다음으로 넘어간다.
7. 5번째 직사각형을 처리한다.
   1. (0,1), (2,1)이 스택에 있다.
   2. (5,3)은 (2,1)보다 높이가 높기 때문에 스택에 그대로 집어넣고 다음으로 넘어간다.
8. 6번째 직사각형을 처리한다.
   1. (0,1), (2,1), (5,3)이 스택에 있다.
   2. (6,3)은 (5,3)과 높이가 같기 때문에 스택에 그대로 집어넣고 다음으로 넘어간다.
9. 이제 모든 직사각형을 처리했으니, 스택을 비워가면서 처리를 하면 된다.
   1. (0,1), (2,1), (5,3), (6,3)이 스택에 있다.
   2. (6,3): (7-6)*3 = 3은 ans보다 작다. 6번째 직사각형만을 사용하여 잘라낸 것(너비 1, 높이 3)이다.
   3. (5,3): (7-5)*3 = 6은 ans보다 작다. 5,6번째 직사각형을 사용하여 잘라낸 것(너비 2, 높이 3)이다.
   4. (2,1): (7-2)*1 = 5은 ans보다 작다. 4,5,6번째 직사각형을 사용하여 잘라낸 것(너비 5, 높이 1)이다.
   5. (0,1): (7-0)*1 = 7은 ans보다 작다. 0~6번째 직사각형을 모두 사용하여 잘라낸 것(너비 7, 높이 1)이다.

같은 방법으로
1,2,3,2,1(정답은 1~3번째 직사각형을 사용한 6)과
3,2,1,2,3(정답은 0~4번째 직사각형을 모두 사용한 5)
에 대해서도 생각해 보라.

이 알고리즘에 왜 동작하는지를 살펴보면 다음과 같다.

1. 스택에는 항상 위치와 직사각형의 높이 모두 오름차순으로 정렬되어 쌓여 있다. top element가 더 높으면 항상 제거하기 때문에 이렇게 된다.
2. i번째 직사각형을 처리할 때, 1에 의해 놓치는 잘라낸 직사각형이 없게 된다.
   1. 즉, (i-1)번째 직사각형이 잘라낸 직사각형의 오른쪽 끝이 되는 모든 경우를 처리하는 것이다.
3. 최소 높이를 사용하는 이유는, 3,2,1,2,3과 같은 경우를 처리하기 위함이다.
   1. 만약에 3번째 직사각형을 처리할 때 (2,1)로 그대로 집어넣어 버리면, 0~4번째 직사각형을 모두 포함한 넓이 5짜리 직사각형을 놓치게 된다.
   2. 1에 의해 i번째 직사각형보다 낮은 top element를 처음 만나기 전까지는 모두 top element가 i번째 직사각형보다 높으므로, 높이 걱정을 할 필요가 없어진다.

이해가 안 된다면, 예시를 몇 개 더 생각해 보면서 해야 한다. 추천하는 예시는 1,2,5,2,2,1,6이다.

다음은 자주 하는 실수를 정리한 것이다.

1. 마지막에 스택을 비우는 작업을 안 하는 경우. 이것은 마지막 직사각형이 잘라낸 직사각형의 오른쪽 끝이 되는 경우를 놓친 것이다.
2. 높이 10억 * 너비 10만은 int의 범위를 한참 넘는다. ans는 long long으로 선언할 것.

구현

이 문제에 적용 가능한 트릭이 몇 가지 있다.

1. 높이가 같은 경우 스택에 넣어도 되고 안 넣어도 된다. 직관을 위해서라면 넣지 말고, 코딩의 편의성을 위해서라면 따로 처리할 필요 없다.
2. 스택을 비우는 작업을 따로 처리하는 대신, 높이 -1짜리 가상의 n번째 직사각형을 생각하자. 그러면 모든 직사각형은 이 n번째 직사각형보다 높기 때문에 스택에서 모두 제거되게 된다.

최소 위치는 left이다. 설명이 복잡한 것 치고는 간결한 코드이지 않은가?

#include "../library/sharifa_header.h"

int main_06549() {
    int n;
    while (true) {
        scanf("%d", &n);
        if (!n)break;
        stack<pair<int,int> > st;
        ll ans = 0;
        for (int i_index = 0; i_index <= n; i_index++) {
            int i_height;
            if (i_index < n)
                scanf("%d", &i_height);
            else
                i_height = -1;
            int left = i_index;
            // top_index: st.top().first, top_height: st.top().second
            while (!st.empty() && st.top().second > i_height) {
                ans = max(ans, ((ll)i_index - st.top().first)*st.top().second);
                left = st.top().first;
                st.pop();
            }
            st.push(make_pair(left, i_height));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?