본문 바로가기

알고리즘 & 자료구조

 (16)
Splay Tree (4) - Lazy Propagation, 구간 뒤집기 안녕하세요. Splay Tree의 활용 중에서 lazy propagation과 구간 뒤집기에 대해 알아보겠습니다. Lazy Propagation 스플레이 트리로 레이지 프로퍼게이션 또한 가능합니다. Node 구조체 lazy 변수를 추가해 줍니다. struct Node { ... long long lazy; ... }; Propagation 함수 작성 struct Node { ... void propagate() { if (lazy) { val += lazy; if (l) { l->lazy += lazy; l->sum += lazy * l->cnt; } if (r) { r->lazy += lazy; r->sum += lazy * r->cnt; } } lazy = 0; } }; propagation은 자식으..
Splay Tree (3) - k번째 수, 구간 쿼리 안녕하세요. Splay Tree의 활용 중 가장 많이 사용되는 구간 쿼리에 대해 알아보겠습니다. Kth 원소 찾기 Tree 상에서 k번째 원소가 무엇인지 찾는 연산입니다. 구간 쿼리를 하려면 kth 원소가 무엇인지 알아야 합니다. first element : 2 second element : 3 4th element : 5 가장 쉽게 구하는 방식으로는, 중위 순회해서 원소들의 리스트를 다 뽑아줍니다. 그리고 그 중 kth 원소를 인덱스를 통해 접근하면 됩니다. 하지만 이 방식은 O(N)의 시간 복잡도가 걸립니다. 스플레이 트리는 이를 다른 방식으로 찾아 O(log N) 만에 가능합니다. Node 구조체 자신을 루트로 하는 서브트리의 크기를 알아야 합니다. 이를 childCnt로 Node 구조체 안에 변수..
Splay Tree (2) - find, insert, delete, 최솟값 최댓값 찾기 안녕하세요. Splay Tree 연산 중 find, insert, delete, 그리고 최솟값 최댓값 찾기를 알아보겠습니다. Binary Tree 이진 트리라서 아래 연산이 가능합니다. find insert delete 최솟값, 최댓값 찾기 Find key 값이 Tree에 있는지 없는지를 확인합니다. BST의 특징을 이용해 값을 찾아 나가면 됩니다. node x의 value == key -> 탐색 종료 node x의 value right child of node x 로 이동 node x의 value > key -> left child of node x 로 이동 탐색이 종료됐으면, 마지막으로 access한 노드를 루트로 올려줍니다. 아래 두 그림은 각각 7과 2를 find 한 뒤의 Spla..
Splay Tree (1) - rotate, splay 안녕하세요. 오늘은 Splay Tree에 대해 알아보겠습니다. 이번 글에서는 기본 연산인 rotate와 splay에 대해 알아보겠습니다. AVL Tree 스플레이 트리는 자가 균형 이진 트리에 속합니다. https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC AVL 트리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 ko.wikipedia.org 일반 이진 탐색 트리의 경우 한쪽으로 노드가 쏠리는 skewed tree가 나타날 수 있습니다. 이렇게 되면 ins..
곱셈의 역원 나머지 연산 modular를 씌울 때 사칙연산 중 다음이 성립합니다. 더하기 : 성립함 빼기 : 성립함 곱하기 : 성립함 나누기 : 성립하지 않음 나눗셈이 성립하기 위해서는 곱셈의 역원을 구해서 곱해줘야 합니다. 정의 어떤 정수 a가 주어질 때, a * x % N == 1인 정수 x를 찾는 문제 +) a와 N이 서로소 일 때만 x가 존재 example) N = 11, a = 3 일 때 => 곱셈의 역원 x = 4 3 * 4 % 11 = 1 풀이 1) 반복문 1부터 N-1까지 반복문으로 찾아본다 O(N) #include int inverseMul(int N, int a) { for (int i = 1; i < N; ++i) { if (a * i % N == 1) return i; } return -1; }..
확장 유클리드 알고리즘 아래 영상을 참고해 작성했습니다. https://www.youtube.com/watch?v=PmwLXveLtqc 정의 유클리드 호제법을 확장한 알고리즘 입니다. https://kdr06006.tistory.com/21 유클리드 호제법 아래 영상을 참고해 작성했습니다. https://www.youtube.com/watch?v=Obs-HC5j5bI 정의 자연수 a, b가 주어질 때 a와 b의 최대 공약수 (=gcd(a, b))를 구하는 방법 과정 gcd(A, B) = gcd(B, A % B)를 이용해 재귀적으로 구 kdr06006.tistory.com ax + by = c c의 값이 gcd(a, b)의 배수일 때만 (x, y)가 정수해를 갖습니다. 즉, 확장 유클리드 알고리즘은 위의 식을 만족하는 정수해 (..
유클리드 호제법 아래 영상을 참고해 작성했습니다. https://www.youtube.com/watch?v=Obs-HC5j5bI 정의 자연수 a, b가 주어질 때 a와 b의 최대 공약수 (=gcd(a, b))를 구하는 방법 과정 gcd(A, B) = gcd(B, A % B)를 이용해 재귀적으로 구할 수 있습니다. gcd(12345, 123)을 구해봅시다. (B == 0이 될 때 A 값이 정답임) 증명 위의 영상으로 대체하겠습니다. 코드 매번 큰 비트가 사라지기 때문에 O(max(log a, log b)) 만에 gcd(a, b)를 구할 수 있습니다. #include int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { printf("%d\n", gcd(..
Rabin Karp (라빈 카프) 알고리즘 Rabin-Karp 알고리즘은 해싱(Hashing)을 사용해서 문자열에서 특정 패턴을 찾아주는 알고리즘 입니다. Pattern에서 Target을 찾는 문제 길이가 더 긴 Pattern = "abacbaacb" 에서 길이가 더 짧은 Target = "acb" 를 찾는 문제가 있습니다. 문자열에 hash 값을 부여한 뒤, 그 hash 값으로 문자열을 판별하면 됩니다. 해시 함수 해시 함수로는 Rabin fingerprint를 많이 사용합니다. 각 문자에 m 거듭제곱을 곱해서 다 더한 값이 hash 값이 됩니다. Example) 먼저, Target의 hash 값을 구하겠습니다. 거듭제곱으로 사용할 m은 2로 가정했습니다. 이후 Pattern에서 Target의 길이만큼 잘라서 hash 값을 비교해주면 됩니다. ..

티스토리툴바