알고리즘16 [자료구조] Segment Tree(세그먼트 트리) 1. Segment Tree(세그먼트 트리) Segment Tree(세그먼트 트리)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. Segment Tree를 도식화하면, 아래와 같습니다. Segment Tree는 다양한 활용법이 있겠지만, 특히 특정 데이터 배열의 구간 합을 계산할 때 유용합니다. 아래 예시를 통해, 단순 배열 방법과 Segment Tree 활용법을 비교해보겠습니다. 예시 1) 단순 배열 방법 array = {1, 2, 3, ..., N} 배열에서 특정 범위의 구간 합과 특정 인덱스의 값 변경을 M번 수행 (1) array 배열에서 1번째 ~ N번째까지 구간 합 연산S = array[0] + array[1] + array[2] + ... + array[N - 1]시간 복.. 2024. 9. 12. [알고리즘] 파스칼 삼각형을 활용한 조합 계산 1. 파스칼 삼각형 2. 소스 코드(C++)int Combination[53][53];// 조합 계산 함수int cal_combination(int n, int r) { if (Combination[n][r]) return Combination[n][r]; // 이전에 계산해놓은 값이 있으면, 바로 반환 else if (n == r || r == 0) Combination[n][r] = 1; // n=r 이거나, r = 0일 때, 1 반환 else { Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD; // nCr = n-1Cr + n-1Cr -1 } return Combination[n][r];} 2024. 9. 5. [알고리즘] 다이나믹 프로그래밍(DP, Dynamic Programming) 1. 문제https://www.acmicpc.net/problem/1509 2024. 5. 4. [알고리즘] CCW(Counter ClockWise) 기하 알고리즘 1. 개요1. 세 점의 방향관계를 알 수 있는 알고리즘 2. 외적http://www.findmean.com/%EC%88%98%ED%95%99/%EB%B2%A1%ED%84%B0/%EB%B2%A1%ED%84%B0%EC%9D%98-%EC%99%B8%EC%A0%81/ 링크 참조외적의 기하학적 표현정리하자면)1. 반시계방향이면 윗 방향인 (+) 값이 나온다.2. 시계방향이면 아랫 방향인 (-) 값이 나온다.3. 동일한 방향이면 0 값이 나온다.계산식은 아래와 같다.https://snowfleur.tistory.com/98 참조 3. 소스 코드// CCW(Counter ClockWise) 알고리즘int ccw(pair p1, pair p2, pair p3){ // 외적 계산 long long temp = p1.fi.. 2024. 5. 1. [알고리즘] 이진 탐색(이분 탐색, Binary Search) 1. 개요1. O(logN) 시간 복잡도로 해당 배열에서 특정 값을 찾는 알고리즘 2. 알고리즘 코드vector ans;// 이진 탐색 알고리즘int binary_search(int n){ int low = 0; int high = ans.size() - 1; int ret = MAX_N; while (low = n) { ret = min(ret, mid); high = mid - 1; } else low = mid + 1; } return ret;} 3. 문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가.. 2024. 4. 14. [알고리즘] 분리 집합(Union-Find) 1. 개요 1. 각 노드들을 그룹을 지을 때 사용하는 알고리즘 2. 알고리즘 코드 int parent[MAX_G]; int Find(int a) { int pA = parent[a]; if (pA == a) return a; return parent[a] = Find(pA); } void Union(int a, int b) { int pA = Find(a); int pB = Find(b); if (pA 2024. 4. 14. [알고리즘] 누적 합 1. 문제 https://www.acmicpc.net/problem/9527 9527번: 1의 개수 세기 두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오. 즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라 www.acmicpc.net 2024. 4. 11. [알고리즘] 그리디 알고리즘 1. 문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.a.. 2024. 4. 6. [알고리즘] BFS(너비 우선 탐색) 1. Breadth First Search (BFS, 너비 우선 탐색1. 완전 탐색 알고리즘 - 모든 경우의 수를 탐색하는 알고리즘2. 시작점에서 가까운 점부터 탐색하는 방식 - 개미굴에 물을 부어서 물이 점점 안 쪽으로 스며들어가는 방식과 비슷하다. 2. 장점1) 출발노드에서 목표 노드까지의 최단 길이 경로를 보장한다. 3. 단점1) 경로가 매우 길 경우에는 탐색 기지가 급격히 증가하여 많은 기억 공간을 필요로 한다. 4. 구현Queue를 통해 구현아래 3가지 구조로 나눌 수 있다.1) 시작점 셋팅2) 현재 방문 노드를 Queue에서 pop하기3) 다음으로 방문할 노드 Queue에 삽입#include #include #include ;using namespace std;bool visited[11];v.. 2024. 4. 3. [알고리즘] DFS (깊이 우선 탐색) 1. Depth First Search (DFS, 깊이 우선 탐색)1. 완전 탐색 알고리즘 - 모든 경우의 수를 탐색하는 알고리즘2. 한 루트로 최대한 깊이 탐색하는 방식 - 트리나 그래프에서 한 루트로 쭉 탐색하다가 끝에 도달하면 다시 이전으로 돌아와서 다른 루트로 가는 방식 - 미로 찾기에서 한 방향으로 쭉 가다가 막히면, 다시 이전 분기점으로 돌아와서 다른 방향으로 가보면서 모든 루트를 탐색하는 방식 2. 장점1) 저장 공간의 수요가 비교적 적다. - 현 경로상의 노드들만 기억하면 되므로2) 목표 노드가 깊은 단계에 있을 경우, 해를 빨리 구할 수 있다. 3. 단점1) 해가 없는 경로에 깊이 빠질 가능성이 있다. - 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못했다면, 다른 경로를.. 2024. 4. 3. 이전 1 2 다음
