#tree
노트 6개
Algorithm › Data Structure
기초 자료구조: 배열에서 트라이까지연산의 약속(추상 자료형)과 구현(자료구조)을 나누는 관점, 배열과 realloc 크기 조정 비용, 배열·행렬 문제의 요령(부분 배열과 부분 수열, 인덱스 변환, 전치), 연결 리스트(C 구조체·Kotlin 예제)와 둘 중 고르는 기준, 더미 노드·제자리 뒤집기 같은 연결 리스트 기법, 층을 쌓아 건너뛰는 스킵 리스트, 이진 탐색 트리와 균형, 해시 테이블과 충돌, 트라이, 얕은 복사와 깊은 복사.
Algorithm › Data Structure
세그먼트 트리배열을 구간별로 나눠 각 구간의 합·최솟값 같은 요약을 이진 트리에 저장해, 값이 바뀌는 배열에서도 구간 질의와 갱신을 모두 O(log n)에 처리하는 자료구조. 배열 크기 잡기, 재귀 구현, 지연 전파와 펜윅 트리 비교까지 정리한다.
Algorithm › Data Structure
트리와 이진 탐색 트리계층 구조를 표현하는 트리의 용어, 이진 트리의 종류와 배열 표현, 네 가지 순회와 반복 구현, 이진 탐색 트리의 연산·편향·검증, 균형 트리의 종류와 AVL 회전, 레드-블랙 트리가 널리 쓰이는 이유, B 트리와 B+ 트리의 차이.
Algorithm › Graph
최소 공통 조상 (LCA)트리에서 두 노드의 가장 가까운 공통 조상을 찾는 LCA. 깊이를 맞춰 함께 올라가는 O(N) 방법과, 2^k번째 조상 표(희소 테이블)로 질의마다 O(log N)에 답하는 이진 올리기(binary lifting), 두 노드 사이 거리 구하기까지.
Algorithm
파싱 알고리즘과 프랫 파서토큰열을 구문 트리로 만드는 파싱 알고리즘의 흐름. BNF 규칙을 함수로 옮기는 재귀 하향 파서(JSON 예제), 연산자 우선순위로 그리디하게 묶는 플로이드의 상향식 파서, 바인딩 파워로 둘의 장점을 합친 프랫 파서를 셸 문법 예제로 정리한다.
AI & Data
비헤이비어 트리게임 AI·로봇·대화 시스템에서 행동을 고르는 트리 구조. 매 틱마다 루트부터 깊이 우선으로 평가하고, 노드는 Success·Failure·Running 중 하나를 돌려준다. Sequence·Selector·Parallel 복합 노드, 데코레이터, 액션·조건 리프로 행동을 조립하며, 상태 전이가 폭증하는 FSM보다 모듈화와 재사용이 쉽다.