여가생활 개발일지

[C++] Lazy propagation

정의 게으르게 전파하여 갱신하는 자료구조이다. 기존 세그먼트 트리는 갱신을 즉시 처리 했지만, Lazy를 이용하여 필요할 때 한꺼번에 처리한다. 특정 구간 [a, b]에 값 c를 동시에 연산할 때 사용된다 단순한 세그먼트 트리로 특정 구간의 길이 N을 연산 한다면 O(NlogN)가 걸리지만 O(logN)로 줄일 수 있다 예시 코드 세그먼트 트리 + Lazy propagation 세그먼트 트리는 완전 이진트리가 아닐 수 있음 그러므로 propagate 함수 안에 현재 노드가 자식인지를 확인하는 if(l != r)가 if(node < si)로 대체될 수 없음 // 백준 10999번 구간 합 구하기2 #include using namespace std; using ll = long long; int si = ..

[C++] 세그먼트 트리, 인덱스 트리

정의 세그먼트 트리란 구간의 값을 전처리하여 특정 구간의 쿼리를 빠르게 수행하는 자료구조이다. 빈번한 구간 연산이 일어날 때 유용하다. 구간의 합, 곱, 최솟값, 최댓값, 최대공약수 등을 빠르게 구할 때 사용한다. 세그먼트 트리와 인덱스 트리를 이용하면 O(lgN)으로 구간의 값을 구할 수 있다. 세그먼트 트리 인덱스 트리 접근 방식 Top-down Bottom-up 구조 포화 이진트리 (2^n 일때 완전 이진트리) 완전 이진트리 특징 범용성이 높아 응용하기 좋음 구현 난이도가 쉽고 직관적임 세그먼트 트리 예시 코드 백준 2042번 바로가기 // 백준 2042번 구간 합 구하기 #include using namespace std; using ll = long long; int si = 1; ll arr[..

[C++] 투 포인터

정의투포인터란 포인터 2개를 조작하여 원하는 결과를 얻는 방법이다무식하게 for문을 사용하면 O(N^2)이지만 투 포인터는 O(N)구간 용어폐구간이상~이하 [ ]개구간초과~미만( )반개구간초과~이하( ]이상~미만[ ) 같은 방향의 투 포인터 주로 구간의 경우의 수를 구하는데 사용한다배열의 원소가 모두 자연수여야 한다배열이 정렬 되어 있지 않아도 된다.알고리즘 원리초기 상태포인터 2개 모두 출발점종료 조건종료 포인터가 끝에 도달할 때까지 알고리즘 반복동작구간 합이 목표보다 작으면 종료 포인터 전진 구간 합이 목표보다 크거나 같으면 시작 포인터 전진 예시코드 (백준 2003번)int arr[1001];// 구간합 경우의 수 구하기int twoPoint(int n, int k) { // 원소 수, 목표 ..

[C++] LCS

정의 LCS란 공통되는 부분 문자열 중 가장 길이가 긴 문자열을 찾는 알고리즘이다 공통 부분 수열과 공통 부분 문자열이 있다 공통 부분 수열(Longest Common Subsequence) 연속적 X 예시코드 int lcs() { int lcs[1001][1001]; string s1, s2; for(int i = 1; i

[C++] 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

정의 BFS(Breadth-First Search): 현재 노드에서 인접한 노드 탐색 DFS(Depth-First Search): 최대한 깊이 이동 후 다음 경로 탐색 모든 노드를 탐색할 때의 시간 복잡도는 같지만, 그렇지 않을 경우 BFS가 더 빠르다. DFS를 재귀로 구현할 때 스택 영역 오버플로우를 주의해야 한다. DFS의 스택 구현은 방문 하다가 막히면 pop 하는 방식이다. BFS DFS 언제 사용할까? 최소 경로를 탐색할 때 경로의 특징을 저장해야 할 때 무엇으로 구현할까? queue stack 또는 재귀 시간복잡도 인접 리스트 O(V+E) 인접 행렬 O(n²) 인접 리스트 O(V+E) 인접 행렬 O(n²) BFS 예시 코드 // 간선으로 이동 bool visited[101]; // 방문 배열..

[C++] 매개변수 탐색(Parametric Search)

정의 매개변수 탐색이란 이분탐색을 사용하여 조건을 만족하는 최솟값/최댓값을 찾는 자료구조이다. 매개변수 탐색 매개변수 탐색에서 최종적으로 구한 최솟값/최댓값이 찾아야 하는 매개변수이다. 결정함수 Fn(param)이 어떠한 조건을 만족하면 T, 만족하지 않으면 F를 반환한다고 정의해 보자. 이분 탐색에서 배열이 오름차순이기 때문에 매개변수 param의 결과인 결정함수 Fn(param)는 연속적이다. 연속적인 결정함수에서 중간에 T → F 또는 F → T로 바뀌는 부분이 찾아야 할 값이다. 매개변수 탐색을 위한 이분탐색을 할 때, (lo+1

[C++] 이분 탐색(Binary Search)

정의 이분탐색이란 검색 범위를 절반씩 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다 검색하는 배열의 데이터가 정렬되어 있어야 한다 이분탐색은 범위 설정이 헷갈리고 실수하기 쉽다. 시간복잡도는 O(logN) 이분탐색 while문 설정 이분 탐색에서 분배를 잘못하면 무한 루프에 빠지므로 while 탈출 조건을 고려해야 한다 while문 조건 구간 설정 탈출 직전 값 lo

[C++] Merge Sort, Quick Sort

정의 병합 정렬과 퀵 정렬은 분할 정복 알고리즘이며, 정렬 속도가 매우 빠르다. 퀵 정렬이 평균적으로 더 빠르지만 오름차순(또는 내림차순)일 때 최악의 경우에 O(n²)이다 하지만 Algorithm 헤더파일의 sort 함수는 퀵 정렬이며, 아래의 방식으로 최악의 경우를 피한다 피벗을 랜덤으로 지정 3개의 피벗 중에 중앙값을 사용 Merge Sort Quick Sort 공통점 평균 O(NlgN) 장점 stable_sort가 가능 임시 배열을 사용하지 않아서 cache hit rate가 높음 Merge Sort 예시코드 #include using namespace std; int arr[1000001]; int tmp[1000001]; void merge(int st, int en){ int mid = (s..

[C++] 페르마의 소정리

정의 결과값이 큰 이항계수를 구할 때 n,r이 크면, mod 연산을 필요로 한다 기존 한계 1. 단순 계산 모듈러 연산은 나누기가 성립하지 않기 때문에 분모의 역원 구하고 곱해주어야 한다 2.파스칼의 삼각형 메모리를 많이 차지하기 때문에 사용할 수 없다 페르마의 소정리 p가 소수이고 a와 p가 서로소라면 페르마의 소정리를 이용하여 분수를 정수로 바꿔줄 수 있다. 더보기 이를 통해 이항계수의 분모에 모듈러 연산이 가능해진다. 더보기 코드 #include using namespace std; #define ll long long ll result = 1; const ll MOD = 1e9+7; void divide(ll a, ll p) { if(p == 0) return; if(p % 2 == 0) divi..

Big-O 빅오 시간복잡도

정의 빅오 표기법의 시간복잡도 차이를 비교하기 시간 복잡도 순서 O(1)