|
이 책으로 공부하는 법
선형 기본 1. 동적 배열 — 칸을 두 배로 늘리고 4분의 1 에서 절반으로 줄이면 옮기는 일이 넣고 빼기 수에 묶이는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 2. 비트 배열 — 자리 번호의 몫과 나머지로 워드 하나만 다루고, 자리를 비트에 담는지는 계약이 가르지 못하는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 선형 특수 3. 갭 버퍼 — 커서 앞과 뒤를 커서 쪽 끝이 맞닿게 갈라 두면 커서 자리의 편집이 원소 수와 상관없어진다 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 4. 피스 테이블 — 넣은 원소를 옮기지 않고 조각으로 이어 두면 편집 한 번이 담긴 원소 수가 아니라 편집 수에 묶이는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 5. 언롤드 연결 리스트 — 원소를 √n 개 안팎의 묶음으로 나눠 두면 자리 찾기와 뒤로 옮기기가 둘 다 √n 에 묶이는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 6. XOR 연결 리스트 — 끝에서 출발하면 주소를 XOR 한 한 칸으로 양쪽 방향을 걸을 수 있는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 그래프 표현 7. 이웃 목록 — 간선을 두 끝 정점에 항목으로 나눠 두면 정점 하나를 다루는 비용이 그 정점의 이웃 수를 따른다 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 8. 인접 행렬 — 정점 쌍마다 칸을 하나씩 정해 두면 간선 하나를 다루는 비용이 정점 수와 이웃 수에 기대지 않는다 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 9. DAG — 간선 u→v 는 v 에서 u 로 가는 길이 있을 때만 사이클을 닫으므로 넣는 비용이 그 간선 주변에 묶인다 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 고급 힙 10. 이항 힙 — 차수마다 이항 트리를 하나씩만 두면 두 힙의 합치기가 이진수 덧셈이 되어 로그 걸음에 끝나는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 11. 피보나치 힙 — 정리를 빼기까지 미루고 자식을 두 번 잃은 노드를 떼어 내면 차수가 원소 수의 로그에 묶이는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 12. 좌향 힙 — 왼쪽을 오른쪽보다 가볍지 않게 두면 오른쪽 길이 로그로 묶여 두 힙을 로그 걸음에 합치는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 13. 짝짓기 힙 — 넣기와 합치기를 잇기 한 번으로 끝내고 빼기 때 자식들을 두 단계로 짝지으면 빼기의 상각 비용이 로그에 묶이는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 14. 반 엠데 보아스 트리 — 키의 비트를 반씩 가르고 최소를 아래로 내려보내지 않으면 넣기와 이웃 찾기가 우주 크기의 로그의 로그 걸음에 끝나는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 공간 자료구조 15. k-d 트리 — 크기가 2 의 거듭제곱인 정적 k-d 트리를 이진수처럼 합치면 넣기는 상각 로그 제곱, 범위 질의는 제곱근 안에 드는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 16. 쿼드트리 — 점의 순위로 네 갈래를 나눈 정적 쿼드트리를 이진수처럼 합치면 범위 질의가 점 사이의 간격과 상관없이 제곱근 안에 드는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 기타 17. 머클 트리 — 이웃한 두 토큰을 해시로 이어 꼭대기까지 묶으면 블록 하나를 형제 토큰 몇 개로 확인하고 다시 묶을 수 있는 이유 파트 1 — 계약에서 동작하는 코드까지 파트 2 — 적용 조건 · 보장 · 비용 실습 — 직접 풀어 보기 마무리 |