복습 정리 노트

2022년 7월 12일 화요일 푼 문제들과 사용되는 개념들을 정리한다. 백준 BOJ 1615번 : 교차 개수 세기 문제 난이도 : Gold I 알고리즘 분류 : 세그먼트 트리 N개의 점들의 쌍에 대해 M개의 선분이 주어질 때 교차 개수를 세는 문제이다. 세그먼트 트리의 가장 대표적인 문제들 중 하나인 Inversion Counting Problem인데 왜 그동안 못 풀고 있었나 봤더니 점들의 위치가 중복되어 주어진다는 점 때문이었다. 생각해보니 기존의 Inversion Counting Problem에서 같은 점이 주어져도 update 함수에서 tree[node] = 1로 설정해주었는데, 해당 노드에 점이 하나 추가되는 것이므로 간단히 tree[node]++와 같이 값을 갱신해주기만 하면 되는 문제였다. ..

2차원 배열에서 특정 직사각형 구간을 잡아 얻을 수 있는 구간의 최대 합을 가장 빠른 시간에 구할 수 있는 알고리즘은 무엇일까요? 특정한 점화식을 사용하는 세그먼트 트리를 이용하면 2차원 공간에서의 최대 구간합을 O(N^2 log N)에 구할 수 있다는 것이 잘 알려져 있으며, 이 알고리즘을 사용하는 문제가 정보 올림피아드에 '금광'이라는 이름의 문제로 출제되어 많은 사람들이 이를 금광 세그라고 부릅니다. 이 포스트에서는 금광 세그에 대해 공부한 것을 간단하게 설명해보고, 이를 구현해볼 것입니다. 백준 BOJ 10167번 : 금광 N개의 점이 주어지고, 각 점에 대해 x, y 좌표와 가중치 w가 주어질 때, 특정 직사각형 형태의 구간을 잡아 얻을 수 있는 최대 구간 합을 구하는 문제입니다. 풀이 코드가 ..

알고리즘에 대한 글을 작성하면 일반적으로 하나의 주제를 잡고 정리해야 하는데, 글 하나에 정리할 정도로 내용이 많지 않은 작은 테크닉이나 단일 문제들의 경우 포스트 하나마다 따로 작성하기가 용이하지 않기 때문에, 이 카테고리에 큰 형식의 틀 없이 모아서 작성해보려고 한다. 백준 BOJ 10986번 : 나머지 합 N개의 수로 이루어진 수열에 대해 연속된 구간의 합이 M으로 나누어 떨어지는 구간의 수를 구하는 문제이다. (1 ≤ N ≤ 10^6) 가장 먼저 떠오르는 풀이는 누적 합을 이용해서 O(N^2)에 푸는 건데, 그렇게 할 경우 당연히 시간 초과이다. i ~ j번째 구간의 합이 M으로 나눈 나머지가 0이라는 것과 동치는 무엇일까? 누적 합을 이용하여 생각해보면, 1 ~ j번째 구간 합에서 1 ~ (i-..

vector, string 내에서 인접한 값끼리 비교할 때 for(int i=1; i

고속 푸리에 변환(FFT, Fast Fourier Transform)은 이산 합성곱을 O(N log N) 시간에 계산할 수 있는 알고리즘입니다. 쉽게 말해 두 N차 (또는 그 이하) 다항식의 곱의 계수들을 O(N log N) 시간에 계산할 수 있는 알고리즘이라고 생각하면 됩니다. 개요 N차 실수 벡터에 이산 푸리에 변환(DFT, Discrete Fourier Transform)이라는 조작 과정을 거쳐 특정한 N차 복소수 벡터의 형태로 만들면, 단순 내적 곱으로도 두 식을 곱한 후 DFT한 값과 같은 값이 얻어지게 됩니다. 따라서 O(N) 시간에 두 식을 곱하고, 다시 역 이산 푸리에 변환(IDFT, Inverse Discrete Fourier Transform)의 조작 과정을 거쳐 실수 N차 벡터로 재변..

우리는 세그먼트 트리를 이용하여 다음과 같은 쿼리 문제를 풀이할 수 있었습니다. → 하나의 데이터 갱신과 구간의 대푯값 구하기 (반대로 구간의 데이터 갱신과 점의 대푯값 구하기도 가능합니다.) 그렇다면 구간의 데이터 갱신과 구간의 대푯값을 구하는 쿼리들을 기존의 세그먼트 트리를 사용해도 O(Q log N) 시간에 해결할 수 있을까요? 답은 불가능하다입니다. (자세한 이유는 아래의 접은 글↓에 정리되어 있습니다.) 더보기 예를 들어 백준(BOJ)의 10999번 문제 '구간 합 구하기 2' 문제를 다음과 같이 세그먼트 트리로 구현했다고 가정합시다. #include #define int long long using namespace std; vector v, tree; int init(int n, int b,..

이 포스트에서는 세그먼트 트리를 다루며, 특히 백준 Online Judge(BOJ)의 세그먼트 트리에 관련된 문제들을 풀이해보도록 하겠습니다. 문제를 풀기 전에, 세그먼트 트리(Segment Tree)는 언제 사용하면 될까요? 세그먼트 트리는 값의 갱신과 구간의 대표값을 구하는 것을 O(log N)의 시간에 수행할 수 있습니다. (구간의 합, 곱, 최댓값, 최솟값, 특정 값보다 큰 값의 개수 등) 따라서 구간의 어떤 값을 여러 번 구해야하는 경우에 유용하게 사용할 수 있습니다. (특히 쿼리 문제) 이제 문제들을 풀어봅시다. 각 문제의 풀이 코드는 접은 글 안에 정리되어 있습니다. 백준 BOJ 2042번 : 구간 합 구하기 수열에서 값의 갱신과 구간 합의 계산을 여러 번 수행해야 하는 문제입니다. 세그먼트..

제곱근 분할법 알고리즘(Square-root Decomposition)이란 구간을 원소의 제곱근의 수로 나눠서 특정 구간의 데이터를 다루거나 연산, 탐색하는 방법의 알고리즘입니다. sqrt(N)개의 연속한 원소를 가지는 bucket 여러 개를 가지고 쿼리들을 처리해주는 것입니다. 예를 들어 원소의 수가 16개일 때, 하나의 bucket의 크기를 sqrt(16) = 4로 잡으면 1~4, 5~8, 9~12, 13~16 구간의 원소를 가지는 4개의 bucket을 잡을 수 있습니다. 만약 구간 합을 구하는 구하는 문제를 푼다고 생각해보면, 각 bucket이 가지는 값은 그 bucket이 가지는 원소들의 합으로 둘 수 있습니다. 예를 들어 arr[i] = i (1 N >> M >> K; M += K; v.resi..

스위핑 알고리즘은 이름 그대로 한 쪽 방향으로 쓸고 가면서 데이터를 처리하는 기법입니다. 정렬된 데이터들에 대해 주로 단일 방향으로 스캔해가면서 계산을 처리해주는 방식으로 문제를 풉니다. 어려운 문제들을 보면 2차원 평면에서 스위핑 알고리즘이 구현되기도 하는데, 이 경우 데이터 수가 많기 때문에 세그먼트 트리와 같은 자료구조를 병합하여 사용하는 것 같습니다. (이 포스트는 제가 정리해놓고 나중에 다시 보려고 쓰는 거라 고차원 스위핑 문제에 대해서는 풀이를 해보고 나서 다시 정리하겠습니다.) 백준(BOJ)에는 스위핑 알고리즘으로 분류된 문제가 300문제 정도가 있는데 이것으로 미루어보아 엄청 빈출되는 유형은 아니지만 은근히 자주 사용되는 알고리즘으로 보입니다. 백준 BOJ 2170번 : 선 긋기 만약 위의..

최근에 머리도 식힐 겸 백준에서 쉬운 문제들 풀면서 랭킹을 올리고 있어서 포스트가 자주 있지는 못했는데 간단한 내용으로 C++에서 2차원 가변 크기 배열(벡터) 선언하는 법을 정리하고 가려고 합니다. 2차원 벡터를 정확히 N*N 크기만큼만 배열을 할당하고 이를 사용하기 위해서는 다음과 같이 코드를 작성해주면 됩니다. N*N 크기의 배열을 입력받고 그대로 출력하는 코드입니다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int N; cin >> N; vector v(N, vector(N)); for(int i=0; i v[i][..