머지소트트리 (merge sort tree)머지 소트 트리는 세그먼트 트리의 변형으로, 특정 구간에서 정렬된 데이터를 효율적으로 처리할 수 있는 자료구조이다. 주로 구간 내 특정 값의 개수를 세거나 k번째 작은 수를 찾는 문제 등에 활용된다. 1. 머지 소트 트리의 개념머지 소트 트리는 세그먼트 트리와 비슷하지만, 각 노드에 구간에 해당하는 데이터를 정렬된 상태로 저장한다. 세그먼트 트리에서 각 노드가 단일 값을 저장하는 반면, 머지 소트 트리에서는 리스트 또는 배열 형태로 정렬된 값을 저장한다.2. 머지 소트 트리의 구성리프 노드: 각 배열의 원소를 저장내부 노드: 해당 구간의 두 하위 노드 데이터를 합친 후 정렬한 리스트를 저장3. 구현 방법1) 트리 구축void build(int s, int e, ..
알고리즘
그래프에서 음의 사이클 구하기벨만 포드 알고리즘을 이용하는 것과 플로이드 워셜 알고리즘을 이용하면 그래프에서 음의 사이클을 찾아낼 수 있다. 플로이드 워셜 알고리즘을 이용한 방법mp를 그래프라고 할 때, 플로이드 워셜 알고리즘에서 사이클의 존재 여부는 mp[i][i] 값을 통해서 확인할 수 있다. 플로이드 워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 구하기 위해 각 정점 i에서 j로 가는 최단 경로를 mp[i][j]에 저장하게 된다.사이클이 없는 경우라면, 어떤 정점에서든 자신으로 돌아오는 경로가 존재하지 않으므로 mp[i][i]는 초기화된 값인 INF를 유지하게 된다.반면, 사이클이 존재하는 경우 해당 경로의 길이를 갱신하게 되어 mp[i][i] (자기 자신에게로 돌아오는 경로)가 INF가 아닌 값..
느리게 갱신되는 세그먼트 트리 (Lazy Propagation)느리게 갱신되는 세그먼트 트리(Lazy Propagation)는 세그먼트 트리에서 구간 업데이트를 더 효율적으로 처리하기 위해 사용하는 기법이다. 구간의 여러 값을 한 번에 갱신하고, 그 후에 구간에 대한 정보를 빠르게 얻어야 할 때 사용된다. 1. 느리게 갱신되는 세그먼트 트리란?기본 세그먼트 트리는 특정 구간의 값(합, 최대값 등)을 빠르게 쿼리할 수 있게 해준다. 그런데 만약 구간 내 모든 값에 동일한 연산(ex. 더하기)을 여러 번 적용해야 하는 경우, 기본 세그먼트 트리로는 비효율적일 수 있다. 최악의 경우 nlogn의 시간이 걸릴 수 있기 때문이다. 이때 느리게 갱신되는 세그먼트 트리를 사용하면 구간 전체에 대한 업데이트를 지연시..
세그먼트 트리세그먼트 트리는 효율적인 구간 연산을 처리하기 위해 사용되는 트리 구조이다. 주어진 배열에서 특정 구간의 합이나 최대값/최소값 등과 같은 정보를 빠르게 구해야 할 때 유용하다. 이 구조를 사용하면 배열의 값을 업데이트하거나 구간의 값을 구하는 작업을 빠르게 처리할 수 있다. 1. 세그먼트 트리란 무엇인가세그먼트 트리는 주어진 배열을 관리하는 트리 구조로, 배열의 특정 구간에 대한 연산(예: 합, 최대값, 최소값 등)을 효율적으로 처리하는 데 사용된다. 일반적으로 배열의 크기가 커질수록 배열의 구간 합이나 구간 최대/최소를 구하는 시간이 오래 걸리는데, 세그먼트 트리를 사용하면 로그 시간(O(logN)))에 이런 연산을 처리할 수 있다. 즉, 세그먼트 트리는 배열의 구간 정보를 미리 저장해 두..
가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)가장 긴 증가하는 부분 수열은 주어진 배열에서 순서를 유지한 채로 길이가 가장 긴 증가하는 부분 수열을 찾는 문제이다. 예를 들면 배열 [10, 9, 2, 5, 3, 7, 101, 18]이 주어지면 이 배열에서 길이가 가장 긴 증가하는 부분 수열은 [2, 3, 7, 101]이며 길이는 4이다. 간단해 보이는데, 접근 방법을 모르면 어려운 유형이므로 기록한다. 해결 방법해결 방법은 2가지가 있다. 동적 계획법을 이용한 방법과 이분 탐색을 활용한 방법이다. 동적 계획법, 시간복잡도 O(N^2)#include using namespace std;int n,a[1003],cnt[1003],res;int main() { ..
유클리드 호제법 def gcd(a,b): while b: # b가 0이 아닐때까지 a,b = b, a%b # a는 나누는 값을 할당하고 b는 a와 b를 나누었을 때 나머지를 할당 return a # 최대공약수 int gcd(int x, int y) { while (y) { int temp = x%y; x = y; y = temp; } return x; } 유클리드 호제법은 최대공약수를 구할 때 사용하는 알고리즘이다. 증명은 어려우므로 다른 블로그를 참고하는 게 좋을 것 같다. 최소공배수는 두 수를 곱한 뒤 최대공약수로 나누면 구할 수 있다. https://roytravel.tistory.com/43 유클리드 호제법 증명 정의 유클리드 호제법이란 두 정수 사이에 최대공약수(GCD)를 보다 효과적으로 구하는..
소수의 정의 1을 제외한 자연수 중, 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수 판별 def prime_num(x): for i in range(2,x): if not x % i: return "합성수" return "소수" 효율성 개선 def primenum(x): for i in range(2, int((x**0.5)+1)): # x의 제곱근까지만 나누어떨어지는지 확인 if not x % i: return "합성수" return "소수" x의 제곱근까지만 나누어떨어졌는지 확인하는 이유는, x의 약수를 펼쳐보면 x의 제곱근 값을 기준으로 대칭을 이루고 있기 때문이다. 이를테면 9는 1, 3, 9를 약수로 가지고 있고, 20은 1, 2, 4, 5, 10, 20을 약수로 가진다. 딱 나누어 떨..
0-1 BFS 0-1 bfs는 가중치가 0과 1만 있는 최단 경로 문제를 말한다. 시간복잡도는 O(V+E) (V는 노드, E는 간선)으로, 조건을 만족하는 경우 다익스트라 알고리즘보다 더 효율적으로 작동한다. 일반적인 BFS 탐색과 동일하지만, 가중치가 0인 정점이 존재하기 때문에 실제로 정점의 방문 횟수가 더 많더라도 가중치가 더 낮은 경우를 고려해야 한다. 즉, 결과 값이 방문 횟수의 최소가 아닌 가중치가 최소인 경우를 찾기 때문에 가중치가 낮은 경로부터 탐색해야 한다. 0-1 BFS 동작 1. 덱의 front에서 현재 노드를 꺼낸다. 2. 연결된 인접 노드를 살펴본다. 3. 현재까지 소비된 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이면 소비된 비용을 갱신해준다. 4. 노드..
파라메트릭 서치 파라메트릭 서치는 최적화 문제를 결정문제로 바꾸어 해결하는 기법, 즉 주어진 상황에서 최소값, 최대값 등의 값을 구하는 문제를 그 값이 어떠한 조건을 만족하는지만 확인하면 되는 문제로 바꾸어 해결하는 기법이다. 이 기법에 의하면 중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문이다. 이를테면 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제이다. 파라메트릭 서치와 이진 탐색은 비슷하게 생겼는데, 활용에 있어서 차이가 조금 있다. 이진탐색은 정렬된 주어진 값 중에서 원하는 값을 찾는 알고리즘이다. (이진탐색 알고리즘을 사용하는 것에 있어 정렬은 전제조건이다.) 순차탐색을 했을 때 시간이 너무 오래걸릴 것 같으면 (ex. 탐색할 것이 몇 억을 넘어갈 경우) 이진탐색을 선..
이진탐색 이진탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법이다. 시작점 끝점을 이용해 탐색범위를 결정한다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 logn에 비례한다. O(logN)을 보장해준다. 이진탐색은 위치를 나타내는 변수 3개를 이용한다. 시작점, 중간점, 끝점 -> 중간점이 실수인 경우, 버림한다. 중간값에 있는 데이터와 찾고자하는 값을 비교한 후, 크냐 작으냐에 따라 중간점 + 1, 중간점 - 1 값을 시작점 또는 끝점으로 변경한 후 다시 중간점을 찾는다. 이후 값을 찾거나 탈출조건에 해당할 때까지 위 과정을 반복한다. 구현 방법 반복문, 재귀함수 기억해야 할 것 이진탐색은 정렬된 리스트에서만 사용가능한 알고리즘이다. 따라서 이진탐색을..
