본문 바로가기

알고리즘/기타

알고리즘/기타 2021. 10. 23. Mo's 모스 알고리즘(Mo's Algorithm)은 업데이트가 없는 복잡한 구간 쿼리를 처리하는 알고리즘입니다. 시작하기 전, 선행지식으로 sqrt Decomposition과 오프라인 쿼리에 대해 알고 있어야 합니다. sqrt Decomposition은 이에 대해 설명한 제 글이 있습니다. https://anz1217.tistory.com/127 MITM, sqrt Decomposition Meet in the middle (MITM)에 대해 알아봅시다. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘.. anz1217.tistory.com 오프라..
알고리즘/기타 2021. 7. 1. 스위핑 스위핑에 대해 알아봅시다. 스위핑은 특정한 기준으로 자료들을 정렬하고, 이를 순서대로 탐색하며 문제를 해결하는 방식을 말합니다. 기법 자체는 매우 간단하지만, 특성상 다양한 자료구조와 결합해서 많이 쓰게 됩니다. https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 가장 간단한 스위핑의 예시문제입니다. 수평선 위에 선분이 여러개 있는데, 선이 여러개 겹친 곳을 한 번씩만 계산했을 때 총 선의 길이의 합을 알아내야 합니다...
알고리즘/기타 2021. 6. 30. MITM, sqrt Decomposition Meet in the middle (MITM)에 대해 알아봅시다. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 길이가 최대 40인 수열이 주어지고, 이 수열의 부분수열 중 원소의 합이 \(S\)인 것의 개수를 구해야 합니다. 이를 나이브하게 브루트 포스로 구하려면 \(O(2^n)\)의 시간복잡도를 가지게 되고, 이는 \(n\)이 최대 40이므로 너무 느립니다. 하지만, 수열을 반으로 나눠서 생각해 보면..
알고리즘/기타 2021. 6. 29. 투 포인터 투 포인터에 대해 알아봅시다. 투 포인터는 말 그대로 두 개의 포인터를 조작하면서 두 포인터가 가리키는 값이 특정한 조건을 만족하도록, 또는 두 포인터 사이의 구간이 조건을 만족하도록 하여 문제를 푸는 방식입니다. https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net \(n\)개의 서로 다른 양의 정수로 이루어진 수열 \(a\)가 주어졌을 때, \(a_i + a_j = x\)를 만족하는 \((i..

티스토리툴바