이진 탐색 트리란? 이진 트리의 한 종류로 왼쪽 자식 노드에는 부모 노드보다 작은 값, 오른쪽 자식 노드에는 부모 노드보다 큰 값을 저장하여 만든 트리 https://lgphone.tistory.com/90 13-2. 이진 탐색 트리와 자가 균형 이진 탐색 트리 (Binary Search Tree and Self-balancing Binary Tree): 파이썬 이진 탐색 트리 이진 탐색 트리 (binary search tree) 는 노드를 정렬된 순서로 유지하는 자료구조이다. 이진 트리로 이루어지며, 각 노드에는 값과 두 자식 노드에 대한 포인터가 있다. 또한 선택적으 lgphone.tistory.com https://ejklike.github.io/2018/01/09/traversing-a-binar..

1. 구간합이란? 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 개념 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법을 배웠다. 자연수 n에 대하여 수열 A(n)의 1 ~ n까지의 합을 S(n)이라고 할 때 두 자연수 a ~ b까지의 합은 S(b) - S(a-1)이다. [증명] a > a >> b; for (int i = 1; i > A[i]; //S(b), S(a) 구하기 for(int i=1; i Ai; S[i] = S[i-1] + Ai; } cin >> a >> b; cout

1. 문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 구간 K만큼의 합을 구하고 그 중에서 최댓값을 구하는 문제이다. 2. 풀이 구간합 https://wondrous-developer.tistory.com/47 동적 계획법을 이용하여 구간합 구하기 1. 구간합의 의미와 시간복잡도 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net #include using namespace std; int seq[20]; int N, S, ans; void func(int cur, int cnt, int sum) { if (cur == N) { if (sum == S && cnt != 0) ans++; return; } //다음 원소를 포함한 경우와 포함하지 않은 경우로 나누기 func(cur + 1, ..

필수 선행 개념: 분할 정복, 이분 탐색 배열 arr = {1, 3, 5, 10, 2}이 있다고 해보자. 특정 구간의 최댓값, 최솟값, 구간합, 구간곱을 구한다고 할 때 질문이 하나라면 O(N)에 해결할 수 있다. 만약 질문이 10만개라면 어떨까? O(N²) = 약 11자리 이므로 1초안에 해결이 불가능하다. 이때 세그먼트 트리를 이용하면 O(log N)에 해결이 가능하다. 배열의 크기는 자료의 개수(N)에 대해 N보다 크거나 같은 2의 제곱수에 두배한 크기만큼 미리 할당해두어야 한다. 시뮬레이션 1. 세그먼트 트리 초기화하기 int init(int st, int en, int node){ if(st == en) return tree[node] = arr[st]; int mid = (st + en) / ..

트리란? 트리란 싸이클이 없는 무방향 그래프를 말한다. 싸이클이 존재하지 않아서 모든 노드가 루트가 될 수 있다. 마치 실로 연결된 구슬이 있는데 한 구슬을 잡아서 들어올릴 때마다 그 구슬이 루트가 되고 트리 구조가 형성되는 것과 비슷하다. 트리 순회하기 그래프의 구조를 가지므로 BFS와 DFS를 이용할 수 있다. 이 과정에서 부모의 정보 or 깊이의 정보가 필요한 경우 중간중간에 기록해주면 된다. 1. BFS void bfs(int root){ queue q; q.push(root); while(!q.empty()){ int cur = q.front(); cout