복습 정리 노트

제곱근 분할법 알고리즘(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번 : 선 긋기 만약 위의..

이 포스트에서는 Problem Solving에서 가끔 등장하는 인터랙티브 문제에 대해 설명하고 푸는 방법을 간단하게 정리해보겠습니다. 인터랙티브(Interactive) 문제란 제출 코드에 따라 입력 데이터가 결정되는 문제입니다. 이름 그대로 채점 프로그램과의 상호 소통하는 방식을 통해 풀이해야 하는 문제 유형이라고 할 수 있습니다. 예를 들어 여러분이 다른 사람과 스무고개를 한다고 가정하면 상대방은 여러분이 어떤 질문을 하느냐에 따라 다른 답을 할 것이고, 그렇게 되면 얻은 답을 기반으로 내용을 유추하여 최종 답을 찾아야 합니다. 이러한 방식으로 문제를 풀이하는 것이 인터랙티브 문제라고 보시면 됩니다. 설명만으로는 이해하기 부족하기 때문에 인터랙티브 문제를 하나 풀이해보겠습니다. 적절한 난이도로 백준 O..

최근에 머리도 식힐 겸 백준에서 쉬운 문제들 풀면서 랭킹을 올리고 있어서 포스트가 자주 있지는 못했는데 간단한 내용으로 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][..

개요알고리즘 사이트 백준(BOJ, Baekjoon Online Judge)에서 약 5100문제 이상을 풀이하며 자주 사용되는 알고리즘들을 모두 정형화된 코드로 정리하였습니다.(최종 업데이트 날짜: 2024년 4월 29일) 각 알고리즘은 BOJ의 문제 난이도 투표 사이트인 Solved.ac의 티어(난이도) 오름차순으로 정리하였습니다.<p data-ke-size=..

C 언어나 C++로 BOJ와 같은 Online Judge 사이트의 문제를 풀다보면 가끔 int 범위를 초과하는 입력 데이터 때문에 틀리는 경우가 있다. 이런 경우 int를 모두 long long으로 바꿔주는 것도 귀찮고 문제 풀 때마다 int 범위를 초과하는지 일일이 신경쓰는 시간이 아깝다. 그렇다고 항상 long long을 사용하자니 코드가 너무 더러워지고 typedef로 ll과 같은 자료형을 사용하자니 가독성이 떨어진다. 따라서 여기서는 평소와 같이 int로 코드를 작성하면서도 long long 범위로 정수 변수를 사용하는 방법을 소개하고자 한다. ** 참고로 내가 떠올린 방법이고, 최소한 BOJ에서는 제대로 동작하는 것을 확인했다. int를 long long처럼 사용하는 방법 #include #de..

백준 BOJ 2098번 : 외판원 순회 Solved.ac 난이도 : Gold I 알고리즘 분류 : 비트필드를 이용한 다이나믹 프로그래밍 외판원 문제란, 도시의 수 N(≤ 16)에 대해 도시에서 도시로 가는 비용들이 주어질 때, 모든 도시를 순회하고 돌아오는데 필요한 최소 비용을 구하는 문제입니다. dp를 이용하여 이 문제를 해결하기 위해서는, 각 도시에 대한 방문 여부를 저장해야 합니다. 따라서 메모리를 효율적으로 사용하기 위해 비트필드를 사용한 다이나믹 프로그래밍으로 문제를 해결해야 합니다. dp[i][j]를 현재 도시가 i이고 j의 방문 상태를 가질 때, 최소 비용으로 정의합니다. 이 때 방문 상태 j란 각 비트에 대해 해당 비트가 1이라면 해당 번호의 도시를 방문한 것이고 0이라면 방문하지 않은 것..

코드포스의 모든 Contest에는 에디토리얼이 따로 존재하지만 제가 공부하기 위해서 문제를 풀어보거나 에디토리얼을 번역하면서 이해하고, 그 내용을 정리해서 올립니다. 1671A. String Building 주어진 문자열을 aa, aaa, bb, bbb만으로 조합하여 만들 수 있는지의 여부를 구하는 문제입니다. 동일한 문자가 2개 이상 반복되는 경우 2와 3의 조합으로 언제나 만들 수 있기 때문에, 조합이 불가능한 경우는 하나의 "독립된" 문자가 존재하는 경우뿐입니다. (ex : aaaaa"b"aaaa) 따라서 고립된 하나의 단일 문자가 존재하는지를 검사하여 그러한 문자가 없다면 YES, 아니면 NO를 출력해주면 됩니다. #include using namespace std; int main() { ios..

백준 BOJ 1963번 : 소수 경로 Solved.ac 난이도 : Gold IV 알고리즘 분류 : 에라토스테네스의 체, BFS 주어진 네 자리 소수 A를 다른 소수 B로 바꿀 때, 한 자리씩 바꾸는 동시에 소수임을 유지하면서 B로 바꾸기 위해서는 최소 몇 번의 자리 교체가 이루어져야 하는지를 구하는 문제입니다. 네 자리 수의 개수는 9000개 정도 밖에 되지 않으므로, 당연히 완전 탐색이 가능한 문제입니다. 다만 "최소" 교체 수를 구하기 위해서 BFS를 이용하여 구현을 해주면 됩니다. 소수 판별을 여러 번 해야하기 때문에 에라토스테네스의 체를 활용하여 소수를 미리 구해놓으면 편합니다. 또한 string과 int 사이의 변환이나 맨 앞 자리 수가 0이 나와서 세 자리 수가 되지 않는지 체크를 해주면서 코..

백준 BOJ 13701번 : 중복 제거 Solved.ac 난이도 : Gold III 알고리즘 분류 : 비트마스킹, 비트 집합 이 문제는 조건이 중요하기 때문에 정확히 적어두겠습니다. (비트마스킹을 반드시 이용해야만 풀 수 있는 문제이기 때문) N개의 정수가 순서대로 입력될 때, 중복되어 나오는 수를 제외하고 출력하는 문제입니다. 이 때 N ≤ 500만이며, 입력되는 각 정수 A_i < 2^25입니다. 그리고 가장 강력한 조건은 메모리 제한인데, 이 문제에서는 메모리 제한이 8MB밖에 되지 않습니다. 따라서 저장 공간을 최대한으로 아끼기 위해 비트를 이용해 데이터를 저장하는 방식을 사용합니다. 각 A_i는 2^25 미만의 크기를 가지지만 용량을 위와 같이 계산해보면 int 배열은 최대 2^21칸 미만으로 ..