세상의 변화에 대해 관심이 많은 이들의 Tech Blog search

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

|

참조

분류 URL
문제 BOJ 13277: 큰 수 곱셈
참조 라이브러리 fft.h, conversion_library.h
이 글에서 설명하는 코드 13277_큰 수 곱셈

개요

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

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

  • N은 두 수의 길이 중 max값이다.

문제 풀이

풀이 자체는 어렵지 않다. 빠른 곱셈을 위해, FFT 를 쓰면 된다. 그게 이 문제의 풀이의 전부이다.

문제 자체가 데이터에 대한 전처리는 다음과 같은 것을 해주면 된다.

  1. reverse를 시켜준다. 큰 수 처리는 가장 낮은 자리수를 맨 앞에 두므로, reverse를 해야 한다.
  2. 곱셈을 할 경우 자리수가 최대 두 배 정도까지 늘어나므로 자리수를 두 배만큼 늘려 준다.
  3. 다시 reverse를 한다. 이 때 앞쪽의 0들은 출력하지 않도록 한다.
  4. 곱셈 결과가 0인 경우 따로 0을 출력하도록 예외처리를 해 준다.

위의 사항만 주의하면, 입력받고, FFT를 적용하고, 출력하는 것이 끝이다.

구현

입출력이 조금 많으므로, string과 cin을 사용할 것이라면

ios::sync_with_stdio(false);
cin.tie(NULL);

를 해주자.

#include "../library/conversion_library.h"
#include "../library/fft.h"

int main_13277() {
    ios::sync_with_stdio(false);    cin.tie(NULL);
    string a, b;
    cin >> a >> b;
    vector<int> A = string_to_vi(a);
    vector<int> B = string_to_vi(b);
    reverse(A.begin(), A.end());	reverse(B.begin(), B.end());

    vector<int> ret = multiply(A, B);

    int i = 0;
    while (i < ret.size()) {
        if (ret[i] >= 10) {
            if (i == ret.size() - 1)
                ret.push_back(ret[i] / 10);
            else
                ret[i + 1] += ret[i] / 10;
            ret[i] %= 10;
        }
        ++i;
    }

    reverse(ret.begin(), ret.end());

    bool start = false;
    for (auto elem : ret) {
        if (elem)start = true;
        if (start)cout << elem;
    }
    if (!start)cout << '0';

    return 0;
}

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

Comment  Read more

BOJ 10828(스택) 문제 풀이

|

참조

분류 URL
문제 스택
이 글에서 설명하는 코드 10828_스택

개요

시간복잡도: $ 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;
}

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

Comment  Read more

BOJ 09012(괄호) 문제 풀이

|

참조

분류 URL
문제 괄호
이 글에서 설명하는 코드 09012_괄호

개요

시간복잡도: $ 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;
}

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

Comment  Read more

greeksharifa's Library

|

sharifa_header.h

코드

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

예를 들면, lllong long이다.

bit_library.h

코드

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

conversion_library.h

코드

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

Comment  Read more

고속 푸리에 변환(Fast Fourier Theorem, FFT). 큰 수의 곱셈

|

참조

분류 URL
문제 큰 수 곱셈
응용 문제 koosaga BOJ FFT 문제집
참조 라이브러리 sharifa_header.h, bit_library.h
이 글에서 설명하는 라이브러리 fft.h

개요

시간복잡도: $ 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(큰 수 곱셈) 문제 풀이

Comment  Read more