![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bkrxgF/btsFR2P62Jq/TbxKi7uvGCzkdF9CYxQfgk/img.jpg)
Algorithm 공부 #21 - 세그먼트 트리 세그먼트 트리(Segmant Tree) ● 주어진 제이터의 구간 합과 데이트 업데이트를 빠르게 수행하기 위한 알고리즘 ● 트리 초기화 / 질의값 구하기(구간 합 구하기, 최대, 최소) / 데이터 업데이트하기의 과정으로 나뉨 ● 트리 초기화하기 1. 데이터의 개수가 2^k일때 start_index=2^k 2. 2^k+1 인덱스부터 리프노드를 제외한 나머지 노드의 값을 채우기 3. 구간 합일 때 : A[N] = A[2N] + A[2N+1] / 최대 : A[N] = max(A[2N], A[2N+1) 최소 : A[N] =min(A[2N],A[2N+1]) ● 질의값 구하기 1. 질의 인덱스를 세그먼트 트리 인덱스로 변환 => 세그먼트 트리 index = 주어진 질의..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/oNdcY/btsFQgoo8hN/GNIvHUGpJ2Vw21PXwmI6Tk/img.jpg)
Algorithm 공부 #20 - 이진 트리 이진 트리(Binary Tree) ● 각 노드의 자식 노드의 개수가 2개 이하인 트리 ● 편리하고 직관적인 자료구조 형태는 배열 ● 이진 트리의 종류 1. 편향 이진 트리 : 트리의 노드들이 한쪽 방향으로만 편향돼 생성된 트리, 탐색 속도가 저하되고 공간이 많이 낭비 2. 포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 모두 꽉 찬 트리 3. 완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 ● 이진 트리의 순차 표현 1. 루트 노드 : index = 1; 2. 부모 노드 : index = index / 2; (단, 현재 노드가 루트 노드가 아닐 때) 3. 왼쪽 자식 노드 : index ..
- Total
- Today
- Yesterday
- C++ Stack
- 최단 경로
- 백준
- 자바스크립트
- 에라토스테네스의 체
- java
- 백준 풀이
- c++ string
- Do it!
- 투 포인터
- 자바
- C++
- 카운팅 정렬
- 이분 매칭
- html
- 반복문
- CSS
- 알고리즘
- 알고리즘 공부
- BFS
- 스택
- 유클리드 호제법
- 자료구조
- DP
- DFS
- js
- 유니온 파인드
- 우선순위 큐
- HTML5
- 세그먼트 트리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |