유혁스쿨

세그먼트(인덱스)트리 주어진 데이터의 구간 합(합배열)과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조의 형태 더 큰 범위로 '인덱스 트리' 라고 불리며 이는 코딩테스트 영역에서 큰 차이가 없음. 구간합이 있는데 왜 세그먼트 트리를 학습하여 사용하는가? 합배열의 가장 큰 문제점은 특정 데이터 업데이트시 굉장히 느리다. 만약 1번 인덱스 값 5를 10으로 변경한다면 나머지 모든 구간에 5를 더해줘야 한다. 인덱스 0 1 2 3 4 5 6 데이터 3 5 4 2 3 7 4 합배열 S 3 8 12 14 17 24 28 index 4의 구간합인 17은 index 0 ~ 4까지의 데이터의 합이다. 합배열로는 S[4]로 표현하며 S[4] = S[3] + A[4] 라는 공식이 성립된다. 중간 영역인 ind..

이진 트리 각 노드의 자식의 갯수(차수)가 2 이하로 구성된 트리 트리는 기본적으로 그래프의 표현과 일차원 배열 표현으로 나뉜다. 그래프의 표현으로는 인접리스트를 활용한 BFS, DFS탐색 알고리즘 유형이 있으며 1차원 배열 표현으로는 인덱스 트리와 LCA 유형이 있다. 이진트리는 1차원 배열로 표현하는 인덱스 트리, LCA라고 볼 수 있다. 종류 편향 이진 트리 포화 이진 트리 완전 이진 트리 노드들이 한쪽으로 편향 돼 생성됨 트리의 높이 모두 일정, 리프노드가 꽉참 마지막 레벨 제외하고 노드들이 완전하게 채워짐, 마지막 레벨은 왼쪽부터 채워짐 ⓐ ／ ⓑ ／ ⓒ ／ ⓓ ／ ⓔ ⓐ ∧ ⓑ ⓒ ∧ ∧ ⓓ ⓔⓕ ⓖ ⓐ ∧ ⓑ ⓒ ∧ ⓓ ⓔ 편향 이진 트리에 저장시 탐색속도 저하 및 많은 공간이 낭비된다. 따..