본문 바로가기

알고리즘/메모44

에라토스테네스, 소수 필요한것 : 불린형 배열 bool isPrime[MAX+1]; fill(isPrime, isPrime + MAX+1, true); isPrime[1] = false; for (int i = 2; i 2019. 8. 18.
Segment Tree, LIS https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 회수이고, K는 구간의 합을 구하는 회수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 정수 a, b, c가 주어지는데, a가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 www.acmicpc.net 가장 기본문제. 구간의 합,최댓값,최소값 등, 원소간 결합,교환법칙이 성립하는 연산에대해 구간의 연산을 구할 수 있는 알고리즘. .. 2019. 8. 18.
Union Find (=disjoint set) 필요한 것: uf배열. find 함수 : 1. uf 배열이 -1로 초기화된 경우 2. uf 배열이자기자신으로 초기화된 경우 merge 함수: 1. merge함수가 일반적으로 union의 기능만을 수행하는 경우 2. MST등에서 union에 성공했을 떄 true, 실패했을 때 false 반환하는 경우 3. merge 후 대표정점(집합)에 포함된 요소의 크기를 초기화해주는 경우 등등등.. 상황에 맞게 구현할 수 있다 int uf[MAX]; //uf배열이 -1로 초기화된 경우 int find(int a) { if (uf[a] == -1) return a; return uf[a] = find(uf[a]); } //union기능만 수행 void merge(int a, int b) { a = find(a); b =.. 2019. 8. 18.
GCD 함수 int gcd(int a, int b) { if (b > a) swap(a, b); int r; while (b != 0) { r = a % b; a = b; b = r; } return a; } int gcd(int a,int b){ if(a 2019. 8. 18.

티스토리툴바