본문 바로가기

Algorithm20

[알고리즘] 모스 알고리즘 모스 알고리즘(Mo's algorithm)은 오프라인(쿼리의 순서가 상관 없는) 구간 쿼리를 처리할 때 유용한 알고리즘으로, 간단히 소개하면 길이 N인 구간을 √N개 구간으로 쪼개고, 미리 쿼리들을 정렬해서 O(n√n)의 시간복잡도로 쿼리를 처리하는 알고리즘입니다. 우선 길이 N인 구간을 각 √N개의 원소를 가진 버킷(bucket)으로 쪼갭니다. 각 쿼리들은 시작점이 더 앞쪽의 버킷에 속하고, 끝점이 더 앞쪽에 있는 쿼리부터 처리해주면 됩니다. 간단히 쿼리의 정렬 함수를 수도코드로 표기하면 이렇게 될 것입니다. bool cmp(query a, query b) { if (a.start/sqrt(n) < b.start/sqrt(n)) return true; else if (a.start/sqrt(n) == .. 2023. 5. 18.
[자료구조] 트라이(Trie) 트라이(Trie)는 문자열을 저장하고 빠르게 탐색하기 위해 사용되는 트리 형태의 자료구조입니다. 각 노드는 문자를 나타내며, 문자열의 접두사를 공통으로 가지는 경로를 형성합니다. 구현 저는 다음과 같이 구현하였습니다. #include using namespace std; typedef struct node { char c = '\0'; bool is_word; vector children; }; struct Trie { node root; node *_insert(node *rt, const char *s) { if (s[0] == '\0') { rt->is_word = true; return rt; } for (node *child : rt->children) { if (child->c == s[0]).. 2023. 5. 18.
[BOJ] 1629. 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 간단하게, A의 B제곱을 구하는 문제입니다. B의 값이 매우 클 수 있으므로, DP를 이용합니다. A의 n제곱을 모두 저장하여 사용하기에는, 계산값을 저장하는 배열의 크기가 2,147,483,647이 될 수는 없으므로 다른 방법을 생각해봅니다. B를 2진수로 바꾸어서, 예를 들어 29라면 11101(2)를 생각해봅니다. A29 = A16*A8*A4*A1로 표현할 수 있고, 이는 다시 A24*A23*A22*A20으로 생각할 수 있습니다. 함수 func(num)은 .. 2023. 4. 30.
[알고리즘] 허프만 코딩 허프만 코딩 원본 데이터에서 자주 출현하는 문자를 적은 비트, 출현 빈도가 낮은 문자를 많은 비트로 부호화해 데이터를 효과적으로 압축하는 방법입니다. $C$를 $n$개의 문자로 이루어진 집합으로 두고 $c\in C$, $c.freq=c$의 빈도 수라고 둡니다. $Q$라는 $freq$가 key인 최소 우선순위 큐도 둡니다. HUFFMAN(C) n = |C| // n은 C의 크기 Q = C // Q를 C에 대해 초기화 for i=1 to n-1 let z = new node; // 새로운 노드 z 할당 z.left = x = EXTRACT_MIN(Q) // Q에서 최소 노드를 뽑아 x, z.left에 할당 z.right = y = EXTRACT_MIN(Q) // Q에서 최소 노드를 뽑아 y, z.right에.. 2021. 12. 16.
[BOJ] 10167. 금광 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net 어떤 2차원 그래프에서, 가능한 직사각형 모양의 범위 내부에 있는 정점의 값의 합 중 최댓값을 구하는 문제입니다. 좌표 x, y의 범위는 (0 ≤ x,y ≤ 10^9)인데, 정점의 개수는 최대 3000개이므로 좌표 압축을 사용해 (0 ≤ x,y < 3000) 으로 만들어줍니다. 시간 제한은 3초이므로 O(N^2logN) 으로 해결하면 됩니다. 일반적으로 사각형을 선택하는 기준은 세로 선 두 개, 가로 선 두 개로 O(N^4)라고 생.. 2021. 2. 20.
[BOJ] 16287. Parcel 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 요약하자면, 주어진 배열 A 안의 임의의 4개의 원소들의 합이 W가 되는 경우가 있는지 여부를 출력하는 문제이다. 처음 생각났던 풀이는 앞의 세 원소는 하나씩 고르고 마지막 원소는 lower_bound로 찾기였다. 당연히 세 원소 고르는 것만 O(N^3)이고 N ≤ 5,000인데 될리가 없다. 시간복잡도 O(N^2) 안에 풀어야 하기 때문에 원소들을 두 개씩 묶는다는 아이디어까지는 쉽게 떠올릴 수 있었다. 원소 두 .. 2021. 1. 27.
[BOJ] 13334. 철로 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 처음 생각했던 풀이는 각 (집, 사무실) 쌍을 시작점 기준으로 정렬한 후 각 쌍을 순회하며 뒤쪽의 끝점들만 따로 정렬한 후 upper_bound로 계산하기...였다. 잘 안 풀리는데다 좋은 풀이도 아닌 것 같아서 매주 일요일마다 진행하는 알고리즘 스터디에 가져갔는데, 이거 우선순위 큐 문제라는 얘기를 듣고 바로 풀이가 생각나서 뚝딱뚝딱 풀었다. struct comp_second { bool operator()(p.. 2021. 1. 27.
[알고리즘] 좌표 압축 치토스 선배 강의 듣고 씀. 좌표 압축 좌표의 범위가 막 ≤ 1,000,000,000으로 큰 경우가 있다. 이런 경우에 arr[1000000000] 같은 배열을 선언하면 당연히 터져버린다. [BOJ] 가로 블록 쌓기 문제 같은 경우 0 ≤ Wi + Di ≤ 2,000,000,000로 좌표 자체의 범위는 크지만, 들어오는 블록의 개수는 100,000개다. 즉 좌표로서 들어오는 수의 종류는 최대 200,000개 라는 뜻이다. 200,000개는 배열로 만들 수 있다. 만약 들어오는 좌표의 종류가 {1, 23434, 9495444, 124, 8, 249833876, 23434}이라면 이를 순서대로 정렬하고 {1, 8, 124, 23434, 23434, 9495444, 249833876}, 중복을 제거해 {1, .. 2020. 10. 9.
[자료구조] sparse table 치토스 선배 강의 듣고 씀. 희소 테이블(sparse table) 희소 테이블(sparse table)은 배열 내 구간의 쿼리를 빠르게 수행할 수 있는 자료구조이다. 배열 arr[0, ..., N-1]이 아래와 같이 있다고 가정하고, i ~ j 구간에 대한 쿼리의 결과(예를 들어 구간 합)를 function(i, j)라고 두면 우선 sparse table 배열 d[i][0]에는 function(i, i) = arr[i]가 들어간다. 그 후 d[i][k]에는 function(i, i + 2^k - 1)이 들어간다. 이를 표로 그리면 아래처럼 된다. 즉 d[1][3]에는 1번 원소부터 시작해서 2^3 = 8개 원소의 합이 저장되어 있다. 만약 2~7 구간의 합을 구하고 싶다면, 이는 2~5 구간의 합 + 6.. 2020. 10. 9.
[알고리즘] Lazy Propagation 선배 강의 듣고 씀. 세그먼트 트리에서 업데이트는 O(logN)의 시간 복잡도를 가진다. 그런데 업데이트가 노드 하나하나가 아니라 구간으로 주어질 때, 그걸 일일이 업데이트를 해주면 느릴 수 있다. 그래서 구간 업데이트가 들어올 때마다 그걸 바로 적용해주지 않고, 업데이트가 있다는 내용을 따로 저장해놓고 나중에(lazy) 해당 노드를 방문할 때 처리한 후 자식 노드로 업데이트를 전파(propagation)해주는 방식이 lazy propagation이다. 이런 세그먼트 트리가 있을 때, 2~7 구간에 업데이트를 준다고 가정해보자. 일반적으로는 8, 9, 10, 23, 24, 12번 노드에 접근해서 위 부모 노드들까지 값을 업데이트시켜줄 것이다. 이런 식으로 하면 만약 업데이트되는 구간이 더 길어질 경우 시.. 2020. 10. 6.
[BOJ] 6549. 히스토그램에서 가장 큰 직사각형 6549번: 히스토그램에서 가장 큰 직사각형 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 www.acmicpc.net 나를 몇달동안 괴롭혔던 문제다. 처음에는 로직이 생각이 안 났고, 로직을 알고 나니 구현이 귀찮았다... 사실 귀찮아할 만큼 구현이 복잡한 문제는 아니고, 아이디어만 알면 쉽게 풀 .. 2020. 5. 13.
[BOJ] 15678. 연세워터파크 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 ≤ Ki ≤ 109) www.acmicpc.net 처음에는 아무 생각 없이 그냥 DP로 짰다가... 시간초과가 났다. 당연히 그렇게 쉬울 리가 없을 거라고는 생각했지만 도저히 로직이 생각이 안 나는걸.. 2주동안 이걸 못 풀고 죽어가고 있었는데 이 사람이 풀어주셨다. O(nlogn) 풀이 | #include using namespace std; #define INF 987654321987654321 int N, D; long long a[100000], .. 2020. 4. 29.

티스토리툴바