#binary-search
노트 4개
Algorithm › Data Structure
트리와 이진 탐색 트리계층 구조를 표현하는 트리의 용어, 이진 트리의 종류와 배열 표현, 네 가지 순회와 반복 구현, 이진 탐색 트리의 연산·편향·검증, 균형 트리의 종류와 AVL 회전, 레드-블랙 트리가 널리 쓰이는 이유, B 트리와 B+ 트리의 차이.
Algorithm › Paradigm
최장 증가 부분 수열 (LIS)수열에서 순서를 지키며 고른 증가 부분 수열 중 가장 긴 것을 구하는 문제. O(n²) DP, 이분 탐색으로 길이를 구하는 O(n log n) 방법, 실제 수열까지 복원하는 방법.
Algorithm › Search
이분 탐색정렬된 데이터에서 탐색 범위를 절반씩 줄여 O(log n)에 원하는 값을 찾는 방법과 그 복잡도 증명, lower bound·upper bound, 경계 조건 실수, 삼분할이 빠르지 않은 이유, 순차 탐색과 어느 쪽을 고를지.
Algorithm › Sorting
병합 삽입 정렬 (Ford-Johnson)비교 횟수를 최소화하도록 설계된 Ford-Johnson 알고리즘. 짝짓기로 큰 원소를 재귀 정렬하고, 작은 원소를 야콥스탈 수 순서로 이진 삽입해 이진 탐색 비용을 낭비하지 않는다.