Gorio Tech Blog
필자가 만든 라이브러리…라고 하기는 좀 그렇고, 그냥 헤더 파일이랑 #define 약간을 모아 놓은 헤더 파일이다.
필자의 코드에서 처음 보는 토큰들이 좀 있을 텐데, 잘 모르겠다면 위의 링크를 참조하면 된다.
예를 들면, ll은 long long이다.
비트 관련 사용자 정의 함수를 모아 놓은 헤더 파일이다.
bit 연산을 안다면 코드를 보고 이해할 수 있으므로 따로 설명하지는 않겠다.
어떤 데이터 타입 변수를 다른 데이터 타입 변수로 바꾸는 함수들을 모아 놓았다.
예를 들어 string_to_vi 함수는 “1236”과 같은 string을 vector<int>로 변환한다.
| 분류 | URL |
|---|---|
| 문제 | 큰 수 곱셈 |
| 응용 문제 | koosaga BOJ FFT 문제집 |
| 참조 라이브러리 | sharifa_header.h, bit_library.h |
| 이 글에서 설명하는 라이브러리 | fft.h |
이 글에서는 FFT(고속 푸리에 변환)을 설명한다.
이론적인 부분에 대한 자세한 설명은 topology-blog에 잘 되어 있으므로 생략한다.
큰 수의 곱셈을 수행할 때 FFT의 개략적인 설명은 다음과 같이 적어 두었다.
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;
}
| 분류 | URL |
|---|---|
| 문제 | 히스토그램에서 가장 큰 직사각형 |
| 이 글에서 설명하는 코드 | 06549_히스토그램에서 가장 큰 직사각형 |
이 글에서는 히스토그램에서 가장 큰 직사각형의 가장 빠른 풀이인 스택을 활용한 풀이를 설명한다.
이 문제는 BOJ 사이트 맨 아래에 적혀 있는 대로 세그먼트 트리($O(N log N)$), 분할 정복($O(N log N)$) 등으로도 풀 수 있다.
개인적으로 스택 활용 문제 중 가장 멋있는 문제라고 생각…
이 문제는 처음 봤을 때는 스택이라는 것을 떠올리기가 굉장히 까다롭다. 하지만 가장 멋있는 풀이 방법이니 꼭 익혀두도록 하자.
우선 $O(N^2)$ 풀이부터 생각해 보자.
사실 이 풀이는 별 것 없다. N개의 직사각형이 있으니, [0, N) 구간이라고 생각하고, 모든 구간의 넓이를 다 구해보는 것이다. 그리고 최댓값을 찾는다.
당연히 $O(N^2)$ 풀이는 시간 초과를 얻는다. 이를 $O(N)$으로 줄이기 위해서는, 한 칸씩 검사할 때마다 $O(N)$에 해당하는 구간을 검사해야 한다.
그리고 이를 가능하게 해 주는 것이 스택이다.
이 풀이를 어떻게 생각해냈을까라는 생각은 잠시 접어두고, 우선 풀이를 보자.
이것이 알고리즘의 전부이다.
BOJ의 예시(2 1 4 5 1 3 3)를 적용해 보자. 아래 그림은 BOJ에서 가져온 것이다.
같은 방법으로
1,2,3,2,1(정답은 1~3번째 직사각형을 사용한 6)과
3,2,1,2,3(정답은 0~4번째 직사각형을 모두 사용한 5)
에 대해서도 생각해 보라.
이 알고리즘에 왜 동작하는지를 살펴보면 다음과 같다.
잘라낸 직사각형이 없게 된다.
이해가 안 된다면, 예시를 몇 개 더 생각해 보면서 해야 한다. 추천하는 예시는 1,2,5,2,2,1,6이다.
다음은 자주 하는 실수를 정리한 것이다.
이 문제에 적용 가능한 트릭이 몇 가지 있다.
최소 위치는 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;
}
주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?
| 분류 | URL |
|---|---|
| 문제 | 행렬 제곱 |
| 응용 문제 | 스포일러 1 |
| 참조 라이브러리 | sharifa_header.h, bit_library.h |
| 이 글에서 설명하는 라이브러리 | matrix.h |
이 글에서는 행렬의 N 거듭제곱을 빠르게 구하는 방법을 설명한다.
사실 행렬의 N승은 정수의 N 거듭제곱 빠르게 구하기을 구하는 것과 근본적으로 동일하다.
다만 단순 정수의 곱이 아닌 행렬곱을 사용할 뿐이다.
먼저 예를 하나 들어보자. 행렬 $A$의 11승을 구하고 싶다고 하자. 어떻게 계산하는 것이 빠르겠는가?
단순무식한 방법을 적자면, $A^2$부터 구하면 된다. 그리고 $A^3$을 구한다. … 마지막으로 $A^{11}$을 구한다.
그러면 계산량은? 행렬곱 10번이다.
나쁘지 않은데? 라고 생각한다면, N이 크면 당연히 시간 초과임을 생각하라. N이 10억쯤 한다면? 10억 번을 1초 안에 계산할 수 있겠는가?
문제처럼 N(문제에서는 B이다.)이 $10^{11}$이나 한다면?
당연히 이 방법으로는 어림도 없다. 그럼 조금 더 좋은 방법을 생각해야 한다.
이제 $A^{11} = A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A \cdot A$를 조금 다르게 써 보자.
[A^{11} = (A^5)^2 \cdot A]
만약에 여러분이, $A^5$를 알고 있다고 하자. 그러면 계산을 몇 번이나 해야 할까?
행렬곱은 딱 두 번 뿐이다.
조금 전 단순무식하게 구할 때를 떠올려보자. $A^5$로부터 $A^{11}$을 구하는 것은 행렬곱 연산이 6번이나 필요했다.
그러나 지금은 단 두 번만에 해결이 된다.
이제 $A^5$를 구하는 방법을 생각해보자. 다음을 생각할 수 있을 것이다.
[A^5 = (A^2)^2 \cdot A]
[A^2 = (A)^2]
그러면 이것을 어떻게 코드로 옮길 것인가?
고려할 것이 몇 가지 있다. 하나씩 살펴보자.
bit_reverse 함수를 사용하는 이유이다.이제 $A^{11}$는 다음과 같은 순서로 구하면 된다는 것을 알 수 있을 것이다. 11=$1011_2$임을 기억하라.
물론 $A^0 = 1$이다.
| 이진수 | 식 |
|---|---|
| 1 | $ (A^0)^2 \cdot A = A^1 $ |
| 0 | $ (A^1)^2 = A^2 $ |
| 1 | $ (A^2)^2 \cdot A = A^5 $ |
| 1 | $ (A^5)^2 \cdot A = A^{11} $ |
조금 더 복잡한 예를 들어보겠다. 46=$101110_2$이다.
| 이진수 | 식 |
|---|---|
| 1 | $ (A^0)^2 \cdot A = A^1 $ |
| 0 | $ (A^1)^2 = A^2 $ |
| 1 | $ (A^2)^2 \cdot A = A^5 $ |
| 1 | $ (A^5)^2 \cdot A = A^{11} $ |
| 1 | $ (A^{11})^2 \cdot A = A^{23} $ |
| 0 | $ (A^{23})^2 = A^{46} $ |
이진수로 나타냈을 때 해당 자리가 1이면 제곱한 후 A를 추가로 곱하고, 0이면 그냥 제곱만 하면 된다.
행렬의 거듭제곱은 아주 복잡하지는 않다. 헷갈린다면 정수의 N 거듭제곱 빠르게 구하기을 참조하라.
거듭제곱이 구현된 행렬 클래스는 다음과 같다. 필자의 편의를 위해, re_define.h에 #define을 활용한 많은 단축 선언들을 사용했다.
#include "sharifa_header.h"
#include "bit_library.h"
vector<vector<int> > mat_mul(vector<vector<int> > matrix_A, vector<vector<int> > matrix_B, int mod) {
int m = matrix_A.size();
vector<vector<int> > ret(m, vector<int>(m));
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
ret[i][j] += ((ll)matrix_A[i][k] * matrix_B[k][j]) % mod;
ret[i][j] %= mod;
}
}
}
return ret;
}
vector<vector<int> > matrix_power_N(vector<vector<int> > matrix, int N, int mod, bool print) {
int m = matrix.size(), len = binary_len(N);
vector<vector<int> > original = matrix;
vector<vector<int> > ret = vector<vector<int> >(m, vector<int>(m));
for (int i = 0; i < m; i++)
ret[i][i] = 1;
N = bit_reverse(N);
while (len--) {
ret = mat_mul(ret, ret, mod);
if (N & 1) {
ret = mat_mul(ret, original, mod);
}
N >>= 1;
}
if (print) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++)
printf("%d ", ret[i][j]);
puts("");
}
}
return ret;
}
사용법은 어렵지 않다. 행렬을 2차원 벡터로 만든다.
그리고 행렬을 N승을 취한 후, print 인자를 true로 주어 matrix_power_N 함수를 호출하면 문제는 풀린다.
#include "../library/matrix.h"
#define mod 1000
int main_10830() {
int m, N;
scanf("%d%d", &m, &N);
vector<vector<int> > original = vector<vector<int> >(m, vector<int>(m));
for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
scanf("%d", &original[i][j]);
matrix_power_N(original, N, mod, true);
return 0;
}
주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 못 믿겠다면, 저런 헤더 파일이 채점 사이트에 있을 것이라 생각하는가?
마크다운을 쓸 때는 메모장으로도 되지만 JetBrains의 Webstorm에 Markdown support plugins을 설치하는 것이 도움이 된다.
Python Code:
# coding=utf-8
# 둥
import torch
from torch.utils.data import Dataset
MSCOCO_IMGFEAT_ROOT = 1048576
SPLIT2NAME = {
'train': 'train2014',
'valid': 'val2014',
}
class VQADataset:
"""
A VQA data example in json file:
"answer_type": "other",
"""
def __init__(self, splits: str):
self.name = splits
print('self.name = splits:', self.name, sep='\t')
self.splits = splits.split(',')
# Loading datasets
self.data = []
for split in self.splits:
self.data.extend(json.load(open("data/vqa/comn_sents_%s.json" % split)))
print("Load %d data from split(s) %s." % (len(self.data), self.name))
# Convert list to dict (for evaluation)
self.id2datum = {
datum['question_id']: datum
for datum in self.data
}
# Answers
self.ans2label = json.load(open("data/vqa/trainval_ans2label.json"))
self.label2ans = json.load(open("data/vqa/trainval_label2ans.json"))
assert len(self.ans2label) == len(self.label2ans)
@property
def num_answers(self):
return len(self.ans2label)
def __len__(self):
return len(self.data)
print('what?', end='\t')위의 글에 잘 설명되어 있지만, 복사해 놓고 쓰기 편하도록 본 글에 정리해 두었다.
참고로 넓은 개행을 하려면 한 줄을 띄우고 작성해야 한다.
좁은 개행은 문장 끝에 공백을 두 개 붙이면 된다.
그러나 여러 줄을 띄워도 효과는 똑같다. 공백 문자 (스페이스바) 도 마찬가지이다.
들여쓰기는 을 사용한다. 하나당 하나의 공백이다.
이 글은 보고 쓰기 위해 작성되었다.
[링크](https://google.com/)
[참조 링크][1]
[1]: https://greeksharifa.github.io/references/2018/06/29/markdown-usage/ "YW & YY's blog: markdown-usage"
빈 줄을 넣는 것을 추천한다.
url 링크: <https://google.com/>
url 링크: https://google.com/
어쩐지 처음으로 돌아가고 싶은가? 내부 링크는 이렇게 사용한다. [가장 큰 제목](#가장-큰-제목)
어쩐지 처음으로 돌아가고 싶은가? 내부 링크는 이렇게 사용한다. 가장 큰 제목
내부 링크의 #id 규칙은 다음과 같다.
-1 -2 -3 등을 붙인다.
> 인용하려면 이와 같이 한다.
>> 인용을 안에 또 하고 싶으면 이렇게 한다.
>>> 더 할 수 있다.
인용하려면 이와 같이 한다.
인용을 안에 또 하고 싶으면 이렇게 한다.
더 할 수 있다.
코드 블럭이다. ```을 써도 되고 ~~~을 써도 된다.
greetings = input()
print('Hello, Markdown!') # greetings는 안썼음
조그맣게 쓰고 싶다면 이렇게
*기울여 쓰기* _기울여 쓰기_
**Bold로 쓰기** __Bold로 쓰기__
***기울이고 Bold로 쓰기*** ___기울이고 Bold로 쓰기___
~~취소하기~~
기울여 쓰기 기울여 쓰기
Bold로 쓰기 Bold로 쓰기
기울이고 Bold로 쓰기 기울이고 Bold로 쓰기
취소하기
---
수평선. 앞뒤로 빈 줄을 하나씩 넣는 것이 좋다.
***
다시 수평선
___
-------------
* * *
수평선. 앞뒤로 빈 줄을 하나씩 넣는 것이 좋다.
다시 수평선
- [ ] 체크리스트
- [x] 완료 리스트
1. 순서 있는 리스트
2. 순서 있는 리스트
0. 사실 숫자는 순서가 없어도 된다.
-1232. 물론 음수는 안 된다.
11111111. 뭐 그래도 숫자는 맞춰 주는 것이 좋긴 하다.
* 순서를 없애고 싶으면 이렇게
* 탭을 누르고 치면 이렇게 보인다.
- 사실 *, -, + 를 섞어서 써도 잘 보인다.
+ 하지만 굳이 그렇게 할 필요는 없다.
* 탭은 적당히 쳐야 잘 보인다.
* 너무 많이 하면 효과가 없다.
- 이미 효과가 없다.
| Header 1 | Header 2 |
|---|---|
| Content 1 | —의 개수는 상관없음. |
| Content 2 | Content 4 |
| Header 1 | Header 2 | Header 3 | | :——– | :———-: | ——–: | | Left | Center | —의 개수가 달라도 됨. |
Header 1 | Header 2
------------------ | --------------------
Content 1 | ---의 개수는 상관없음.
Content 2 | Content 4
| Header 1 | Header 2 | Header 3 |
| :-------- | :----------: | --------: |
| Left | Center | ---의 개수가 달라도 됨. |
이미지는 이렇게(링크랑 비슷)
1: /test3.png
예시:
``` 이미지는 이렇게(링크랑 비슷)
1: /test3.png
예시:
편하게 하려면,
/public/img/으로 시작해야 한다.