팬텀 리드란 무엇이며 어떻게 막는가?

다른 트랜잭션이 변경을 커밋한 뒤 같은 술어 질의를 반복하면 조건에 맞는 행 집합이 달라지는 현상이다. 표준 모델의 SERIALIZABLE은 이를 막는다. PostgreSQL의 REPEATABLE READ 등 일부 구현은 더 낮은 수준에서도 막는다.

SQL Server의 행 저장소에서 클러스터형과 비클러스터형 인덱스는 어떻게 다른가?

클러스터형 인덱스는 테이블 행을 키 순서로 저장하므로 테이블당 최대 하나이다. 비클러스터형 인덱스는 자체 키와 행 위치 지정자를 가지며 다른 열을 포함할 수도 있다. 용어와 저장 세부 사항은 데이터베이스 시스템마다 다르다.

일반적인 동기 커밋에서 PostgreSQL WAL은 지속성을 어떻게 지원하는가?

관련 로그 레코드는 커밋 완료를 알리기 전과 변경된 데이터 페이지를 쓰기 전에 영속 저장소에 도달한다. 시스템이 비정상 종료된 뒤 WAL로 데이터 페이지에 빠진 변경을 재실행할 수 있다. 비동기 커밋에서는 최근 완료를 알린 트랜잭션을 잃을 수 있다.

더티 리드란 무엇이며 이를 처음 막는 표준 격리 수준은 무엇인가?

다른 트랜잭션의 미커밋 데이터를 읽는 것이다. 그 트랜잭션이 나중에 롤백되는지와는 무관하다. READ COMMITTED 이상의 표준 격리 수준은 더티 리드를 금지한다.

PostgreSQL에서 기본 키와 외래 키는 어떻게 다른가?

기본 키는 유일하고 NULL이 아닌 값으로 행을 식별한다. 외래 키는 해당 NULL 규칙에 따라 참조 대상 키 값과의 일치를 요구한다. 같은 테이블이나 다른 테이블의 적격 UNIQUE 키 또는 기본 키를 참조할 수 있다.

너비 우선 탐색은 가중치 없는 그래프에서 어떻게 최단 경로를 찾는가?

BFS는 FIFO 큐를 사용해 간선 수로 잰 거리 순서대로 정점을 탐색한다. 큐에 넣을 때 정점을 표시하면 중복 방문을 피한다. 도달 가능한 정점으로 처음 발견한 경로는 간선 수가 최소이다.

계수 정렬이나 기수 정렬은 언제 선형 시간으로 동작할 수 있는가?

계수 정렬은 k개 값을 갖는 범위의 키 n개에 O(n+k)가 든다. 기수 b로 d번의 안정적인 자릿수 정렬을 하는 기수 정렬은 O(d(n+b))이다. 이 매개변수들이 허용할 때만 선형이며, 단순 비교 외에 키의 구조를 활용한다.

표준 배열 병합 정렬의 동작과 시간·공간 복잡도는 무엇인가?

두 절반을 재귀적으로 정렬한 뒤 선형 시간에 병합한다. 비교가 상수 시간이라고 가정하면 표준 구현은 Θ(n log n) 시간과 O(n) 보조 공간을 사용한다.

최장 공통 부분 수열(LCS) 길이의 동적 계획법 점화식은 무엇인가?

L[i,j]를 길이가 i,j인 접두 부분의 LCS 길이라 하자. L[0,j]=L[i,0]=0이다. 마지막 문자가 같으면 L[i,j]=1+L[i−1,j−1], 다르면 L[i,j]=max(L[i−1,j],L[i,j−1])이다. 전체 표의 시간과 공간은 O(mn)이다.

탐욕 알고리즘과 동적 계획법은 어떻게 다른가?

탐욕 알고리즘은 국소 선택을 확정하며, 그 선택들이 최적해를 보존한다는 증명이 필요하다. DP는 점화식으로 대안을 비교하고 부분 문제 결과를 재사용한다. 전역 최적해에는 올바른 모델과 점화식이 필요하며, 단순히 'DP'라고 부르는 것으로 충분하지 않다.

반복 불가능한 읽기란 무엇이며 어떤 표준 격리 수준이 막는가?

다른 트랜잭션이 갱신이나 삭제를 커밋한 뒤 같은 행을 다시 읽으면 값이 바뀌거나 행이 사라지는 현상이다. REPEATABLE READ와 SERIALIZABLE은 이를 금지한다.

다익스트라 알고리즘의 유효 조건과 흔한 힙 구현의 시간 경계는 무엇인가?

간선 가중치가 음수가 아니면 잠정 거리가 가장 작은 정점을 반복해서 확정한다. 인접 리스트와 이진 최소 힙 구현은 O((V+E) log V) 시간이 걸린다. 음수 간선은 확정된 거리에 관한 논증을 무효로 만들 수 있다.

정수 용량 W에 대한 표준 0/1 배낭 점화식은 무엇인가?

D[i,w]를 앞의 i개 물건으로 용량 w에서 얻는 최대 가치라 하고 무게 wᵢ는 양의 정수라 하자. D[0,w]=0으로 둔다. wᵢ>w이면 D[i−1,w]를 복사하고, 아니면 max(D[i−1,w],vᵢ+D[i−1,w−wᵢ])를 택한다. O(NW) 시간은 의사다항 시간이다.

제1·제2·제3정규형의 조건은 무엇인가?

1NF: 속성값이 원자적이다. 2NF: 1NF이며 비주요 속성이 어떤 후보 키의 진부분집합에도 종속되지 않는다. 3NF: 1NF이며 모든 비자명한 종속성 X→A에서 X가 슈퍼키이거나 A가 주요 속성이다. 주요 속성은 적어도 하나의 후보 키에 속한다.

위상 순서란 무엇이며 칸 알고리즘은 어떻게 구하는가?

DAG에서 모든 간선 u→v에 대해 u가 v보다 앞에 온다. 진입 차수가 0인 정점을 반복해서 출력하고 그 출발 간선들을 지우며, 새로 진입 차수가 0이 된 정점을 큐에 넣는다. 출력한 정점 수가 V보다 적으면 방향 그래프에 사이클이 있다.

인접 행렬과 일반적인 인접 리스트는 어떻게 다른가?

정점 V개, 간선 E개일 때 행렬은 O(V²) 공간을 쓰고 간선 존재를 O(1)에 확인한다. 리스트는 O(V+E) 공간을 쓴다. 정렬되지 않은 리스트에서 간선 (u,v)를 찾는 시간은 O(deg(u))이며, deg(u)는 그 리스트의 길이이다.

메모이제이션과 상향식 동적 계획법은 어떻게 다른가?

메모이제이션은 필요한 부분 문제를 보통 재귀적으로 계산하고 결과를 저장한다. 상향식 DP는 의존하는 값이 이미 준비된 순서로 상태를 계산하며 보통 표를 채운다.

깊이 우선 탐색으로 방향 그래프의 사이클을 어떻게 검출하는가?

DFS는 재귀나 명시적 스택으로 깊이 탐색한다. 현재 DFS 경로에서 아직 활성 상태인 정점으로 가는 간선은 역방향 간선이며 방향 사이클의 존재를 증명한다. 단순히 이전에 방문한 정점으로 가는 간선만으로는 충분하지 않다.

그룹화 질의에서 WHERE와 HAVING은 어떻게 다른가?

WHERE는 그룹화 전에 입력 행을 필터링한다. HAVING은 생성된 그룹을 필터링하며 COUNT(*)>1 같은 집계 조건을 쓸 수 있다.

안정 정렬이란 무엇인가?

키가 같은 항목들의 원래 상대적 순서를 보존하는 정렬이다. 병합 정렬은 동률일 때 왼쪽 항목을 먼저 택하면 안정적으로 만들 수 있다. 표준 제자리 퀵 정렬은 대체로 불안정하다. 안정성은 구현에 달려 있다.

트랜잭션의 ACID 속성은 각각 무엇을 뜻하는가?

원자성: 효과가 전부 적용되거나 전혀 적용되지 않는다. 일관성: 올바른 트랜잭션이 제약과 애플리케이션 불변 조건을 보존한다. 격리성: 동시 동작이 선택한 격리 수준을 따른다. 지속성: 설정된 데이터베이스 보장 범위의 장애 뒤에도 커밋한 효과가 남는다.

제자리 힙 정렬의 최악 시간과 추가 공간 복잡도는 무엇인가?

힙 구성에는 O(n), 이후 모든 추출 작업에는 합계 O(n log n)이 걸린다. 입력 배열에서 반복적 하향 조정을 쓰면 최악 시간은 O(n log n), 추가 공간은 O(1)이다.

퀵 정렬이 Θ(n²) 시간이 걸릴 수 있는 이유와 무작위화의 효과는 무엇인가?

서로 다른 키 중 최솟값을 매번 피벗으로 고르는 것처럼 매우 불균형한 분할이 반복되면 이차 작업량이 생긴다. 키가 모두 다르거나 중복 키를 적절히 처리하면 무작위 피벗의 기대 시간은 O(n log n)이다. 세 값의 중앙값 선택은 유용한 휴리스틱이지만 최악의 경우를 보장하지는 않는다.

이진 탐색에는 어떤 조건이 필요하며 언제 O(log n) 시간이 걸리는가?

비교 순서대로 정렬된 데이터에서 탐색 구간을 반복해서 절반으로 줄인다. 인덱스 접근이 O(1)이고 비교가 상수 시간인 배열에서 n개 원소를 탐색하면 O(log n) 시간이 걸린다.

삽입 정렬은 어떻게 동작하며 거의 정렬된 입력의 시간은 무엇에 좌우되는가?

각 항목을 정렬된 접두 부분에 삽입한다. 인접 항목 이동이나 교환을 쓰는 일반 구현은 역전 쌍의 수를 I라 할 때 Θ(n+I) 시간이 걸린다. I=O(n)이면 선형 시간이다. 입력이 작다는 사실만으로 최악 Θ(n²) 경계가 달라지지는 않는다.

벨만–포드 알고리즘은 음수 간선을 어떻게 처리하고 도달 가능한 음수 사이클을 어떻게 검출하는가?

모든 간선을 최대 V−1회 완화한다. 도달 가능한 정점에서 추가로 거리를 개선할 수 있으면 시작점에서 도달 가능한 음수 사이클이 있다. 최악 시간은 O(VE)이다. 그 사이클에서 도달 가능한 정점은 유한한 최단 경로 비용이 없다.

INNER JOIN과 LEFT JOIN은 어떻게 다른가?

INNER JOIN은 조인 조건을 만족하는 행 조합을 반환한다. LEFT JOIN은 일치하지 않는 왼쪽 행도 각각 유지하고 오른쪽 열에 NULL을 넣는다. 오른쪽에 여러 일치 행이 있으면 하나의 왼쪽 행에서 여러 출력 행이 생길 수 있다.

2단계 잠금(2PL)의 두 단계는 무엇인가?

확장 단계: 잠금을 해제하지 않고 획득한다. 축소 단계: 새 잠금을 획득하지 않고 해제한다. 적절히 충돌하는 읽기·쓰기 잠금을 쓰면 2PL은 스케줄의 충돌 직렬 가능성을 보장하지만 교착 상태는 여전히 가능하다.

SQL SELECT 질의의 단순화한 논리적 처리 순서는 무엇인가?

CTE, 윈도 함수, 집합 연산이 없는 질의에서는 FROM/JOIN → WHERE → GROUP BY와 집계 → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET이다. 이는 논리 모델이며 옵티마이저의 실제 물리 실행 순서와 같을 필요는 없다.

B+ 트리가 데이터베이스 인덱스와 범위 질의에 유용한 이유는 무엇인가?

높은 분기 수가 트리를 얕게 유지해 페이지 접근을 줄인다. 정렬된 키와 연결된 잎이 범위 스캔을 지원한다. 해시 인덱스는 동등 비교 검색용이며 같은 정렬 기반 범위 접근을 본질적으로 제공하지는 않는다.

크루스칼과 프림 알고리즘은 최소 신장 트리를 어떻게 만드는가?

연결된 가중 무방향 그래프에서 크루스칼은 간선을 가중치 오름차순으로 보고 Union–Find로 사이클을 만드는 간선을 거부한다. 프림은 트리 내부와 외부 정점을 잇는 최소 가중치 간선을 반복 선택해 하나의 트리를 확장한다.

동적 계획법은 왜 여러 최적화 문제에 유용한가?

최적 부분 구조가 있으면 전체 최적해를 부분 문제의 최적해로 표현할 수 있다. 부분 문제가 겹칠 때 답을 저장하면 반복 작업을 피한다. 상태 정의와 점화식이 원래 문제를 올바르게 나타내야 한다.

알고리즘, 그래프, 동적 계획법과 관계형 데이터베이스

정렬, 그래프 알고리즘, 동적 계획법, SQL, 인덱스, 트랜잭션을 복습하는 학부 수준의 카드 32개. 기본 프로그래밍, 자료구조, SQL 지식을 전제로 한다.

Level: basic
Languages: ko → ko
Cards: 32
Markdown: 알고리즘, 그래프, 동적 계획법과 관계형 데이터베이스 (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	팬텀 리드란 무엇이며 어떻게 막는가?	다른 트랜잭션이 변경을 커밋한 뒤 같은 술어 질의를 반복하면 조건에 맞는 행 집합이 달라지는 현상이다. 표준 모델의 SERIALIZABLE은 이를 막는다. PostgreSQL의 REPEATABLE READ 등 일부 구현은 더 낮은 수준에서도 막는다.
2	SQL Server의 행 저장소에서 클러스터형과 비클러스터형 인덱스는 어떻게 다른가?	클러스터형 인덱스는 테이블 행을 키 순서로 저장하므로 테이블당 최대 하나이다. 비클러스터형 인덱스는 자체 키와 행 위치 지정자를 가지며 다른 열을 포함할 수도 있다. 용어와 저장 세부 사항은 데이터베이스 시스템마다 다르다.
3	일반적인 동기 커밋에서 PostgreSQL WAL은 지속성을 어떻게 지원하는가?	관련 로그 레코드는 커밋 완료를 알리기 전과 변경된 데이터 페이지를 쓰기 전에 영속 저장소에 도달한다. 시스템이 비정상 종료된 뒤 WAL로 데이터 페이지에 빠진 변경을 재실행할 수 있다. 비동기 커밋에서는 최근 완료를 알린 트랜잭션을 잃을 수 있다.
4	더티 리드란 무엇이며 이를 처음 막는 표준 격리 수준은 무엇인가?	다른 트랜잭션의 미커밋 데이터를 읽는 것이다. 그 트랜잭션이 나중에 롤백되는지와는 무관하다. READ COMMITTED 이상의 표준 격리 수준은 더티 리드를 금지한다.
5	PostgreSQL에서 기본 키와 외래 키는 어떻게 다른가?	기본 키는 유일하고 NULL이 아닌 값으로 행을 식별한다. 외래 키는 해당 NULL 규칙에 따라 참조 대상 키 값과의 일치를 요구한다. 같은 테이블이나 다른 테이블의 적격 UNIQUE 키 또는 기본 키를 참조할 수 있다.
6	너비 우선 탐색은 가중치 없는 그래프에서 어떻게 최단 경로를 찾는가?	BFS는 FIFO 큐를 사용해 간선 수로 잰 거리 순서대로 정점을 탐색한다. 큐에 넣을 때 정점을 표시하면 중복 방문을 피한다. 도달 가능한 정점으로 처음 발견한 경로는 간선 수가 최소이다.
7	계수 정렬이나 기수 정렬은 언제 선형 시간으로 동작할 수 있는가?	계수 정렬은 k개 값을 갖는 범위의 키 n개에 O(n+k)가 든다. 기수 b로 d번의 안정적인 자릿수 정렬을 하는 기수 정렬은 O(d(n+b))이다. 이 매개변수들이 허용할 때만 선형이며, 단순 비교 외에 키의 구조를 활용한다.
8	표준 배열 병합 정렬의 동작과 시간·공간 복잡도는 무엇인가?	두 절반을 재귀적으로 정렬한 뒤 선형 시간에 병합한다. 비교가 상수 시간이라고 가정하면 표준 구현은 Θ(n log n) 시간과 O(n) 보조 공간을 사용한다.
9	최장 공통 부분 수열(LCS) 길이의 동적 계획법 점화식은 무엇인가?	L[i,j]를 길이가 i,j인 접두 부분의 LCS 길이라 하자. L[0,j]=L[i,0]=0이다. 마지막 문자가 같으면 L[i,j]=1+L[i−1,j−1], 다르면 L[i,j]=max(L[i−1,j],L[i,j−1])이다. 전체 표의 시간과 공간은 O(mn)이다.
10	탐욕 알고리즘과 동적 계획법은 어떻게 다른가?	탐욕 알고리즘은 국소 선택을 확정하며, 그 선택들이 최적해를 보존한다는 증명이 필요하다. DP는 점화식으로 대안을 비교하고 부분 문제 결과를 재사용한다. 전역 최적해에는 올바른 모델과 점화식이 필요하며, 단순히 'DP'라고 부르는 것으로 충분하지 않다.
11	반복 불가능한 읽기란 무엇이며 어떤 표준 격리 수준이 막는가?	다른 트랜잭션이 갱신이나 삭제를 커밋한 뒤 같은 행을 다시 읽으면 값이 바뀌거나 행이 사라지는 현상이다. REPEATABLE READ와 SERIALIZABLE은 이를 금지한다.
12	다익스트라 알고리즘의 유효 조건과 흔한 힙 구현의 시간 경계는 무엇인가?	간선 가중치가 음수가 아니면 잠정 거리가 가장 작은 정점을 반복해서 확정한다. 인접 리스트와 이진 최소 힙 구현은 O((V+E) log V) 시간이 걸린다. 음수 간선은 확정된 거리에 관한 논증을 무효로 만들 수 있다.
13	정수 용량 W에 대한 표준 0/1 배낭 점화식은 무엇인가?	D[i,w]를 앞의 i개 물건으로 용량 w에서 얻는 최대 가치라 하고 무게 wᵢ는 양의 정수라 하자. D[0,w]=0으로 둔다. wᵢ>w이면 D[i−1,w]를 복사하고, 아니면 max(D[i−1,w],vᵢ+D[i−1,w−wᵢ])를 택한다. O(NW) 시간은 의사다항 시간이다.
14	제1·제2·제3정규형의 조건은 무엇인가?	1NF: 속성값이 원자적이다. 2NF: 1NF이며 비주요 속성이 어떤 후보 키의 진부분집합에도 종속되지 않는다. 3NF: 1NF이며 모든 비자명한 종속성 X→A에서 X가 슈퍼키이거나 A가 주요 속성이다. 주요 속성은 적어도 하나의 후보 키에 속한다.
15	위상 순서란 무엇이며 칸 알고리즘은 어떻게 구하는가?	DAG에서 모든 간선 u→v에 대해 u가 v보다 앞에 온다. 진입 차수가 0인 정점을 반복해서 출력하고 그 출발 간선들을 지우며, 새로 진입 차수가 0이 된 정점을 큐에 넣는다. 출력한 정점 수가 V보다 적으면 방향 그래프에 사이클이 있다.
16	인접 행렬과 일반적인 인접 리스트는 어떻게 다른가?	정점 V개, 간선 E개일 때 행렬은 O(V²) 공간을 쓰고 간선 존재를 O(1)에 확인한다. 리스트는 O(V+E) 공간을 쓴다. 정렬되지 않은 리스트에서 간선 (u,v)를 찾는 시간은 O(deg(u))이며, deg(u)는 그 리스트의 길이이다.
17	메모이제이션과 상향식 동적 계획법은 어떻게 다른가?	메모이제이션은 필요한 부분 문제를 보통 재귀적으로 계산하고 결과를 저장한다. 상향식 DP는 의존하는 값이 이미 준비된 순서로 상태를 계산하며 보통 표를 채운다.
18	깊이 우선 탐색으로 방향 그래프의 사이클을 어떻게 검출하는가?	DFS는 재귀나 명시적 스택으로 깊이 탐색한다. 현재 DFS 경로에서 아직 활성 상태인 정점으로 가는 간선은 역방향 간선이며 방향 사이클의 존재를 증명한다. 단순히 이전에 방문한 정점으로 가는 간선만으로는 충분하지 않다.
19	그룹화 질의에서 WHERE와 HAVING은 어떻게 다른가?	WHERE는 그룹화 전에 입력 행을 필터링한다. HAVING은 생성된 그룹을 필터링하며 COUNT(*)>1 같은 집계 조건을 쓸 수 있다.
20	안정 정렬이란 무엇인가?	키가 같은 항목들의 원래 상대적 순서를 보존하는 정렬이다. 병합 정렬은 동률일 때 왼쪽 항목을 먼저 택하면 안정적으로 만들 수 있다. 표준 제자리 퀵 정렬은 대체로 불안정하다. 안정성은 구현에 달려 있다.
21	트랜잭션의 ACID 속성은 각각 무엇을 뜻하는가?	원자성: 효과가 전부 적용되거나 전혀 적용되지 않는다. 일관성: 올바른 트랜잭션이 제약과 애플리케이션 불변 조건을 보존한다. 격리성: 동시 동작이 선택한 격리 수준을 따른다. 지속성: 설정된 데이터베이스 보장 범위의 장애 뒤에도 커밋한 효과가 남는다.
22	제자리 힙 정렬의 최악 시간과 추가 공간 복잡도는 무엇인가?	힙 구성에는 O(n), 이후 모든 추출 작업에는 합계 O(n log n)이 걸린다. 입력 배열에서 반복적 하향 조정을 쓰면 최악 시간은 O(n log n), 추가 공간은 O(1)이다.
23	퀵 정렬이 Θ(n²) 시간이 걸릴 수 있는 이유와 무작위화의 효과는 무엇인가?	서로 다른 키 중 최솟값을 매번 피벗으로 고르는 것처럼 매우 불균형한 분할이 반복되면 이차 작업량이 생긴다. 키가 모두 다르거나 중복 키를 적절히 처리하면 무작위 피벗의 기대 시간은 O(n log n)이다. 세 값의 중앙값 선택은 유용한 휴리스틱이지만 최악의 경우를 보장하지는 않는다.
24	이진 탐색에는 어떤 조건이 필요하며 언제 O(log n) 시간이 걸리는가?	비교 순서대로 정렬된 데이터에서 탐색 구간을 반복해서 절반으로 줄인다. 인덱스 접근이 O(1)이고 비교가 상수 시간인 배열에서 n개 원소를 탐색하면 O(log n) 시간이 걸린다.
25	삽입 정렬은 어떻게 동작하며 거의 정렬된 입력의 시간은 무엇에 좌우되는가?	각 항목을 정렬된 접두 부분에 삽입한다. 인접 항목 이동이나 교환을 쓰는 일반 구현은 역전 쌍의 수를 I라 할 때 Θ(n+I) 시간이 걸린다. I=O(n)이면 선형 시간이다. 입력이 작다는 사실만으로 최악 Θ(n²) 경계가 달라지지는 않는다.
26	벨만–포드 알고리즘은 음수 간선을 어떻게 처리하고 도달 가능한 음수 사이클을 어떻게 검출하는가?	모든 간선을 최대 V−1회 완화한다. 도달 가능한 정점에서 추가로 거리를 개선할 수 있으면 시작점에서 도달 가능한 음수 사이클이 있다. 최악 시간은 O(VE)이다. 그 사이클에서 도달 가능한 정점은 유한한 최단 경로 비용이 없다.
27	INNER JOIN과 LEFT JOIN은 어떻게 다른가?	INNER JOIN은 조인 조건을 만족하는 행 조합을 반환한다. LEFT JOIN은 일치하지 않는 왼쪽 행도 각각 유지하고 오른쪽 열에 NULL을 넣는다. 오른쪽에 여러 일치 행이 있으면 하나의 왼쪽 행에서 여러 출력 행이 생길 수 있다.
28	2단계 잠금(2PL)의 두 단계는 무엇인가?	확장 단계: 잠금을 해제하지 않고 획득한다. 축소 단계: 새 잠금을 획득하지 않고 해제한다. 적절히 충돌하는 읽기·쓰기 잠금을 쓰면 2PL은 스케줄의 충돌 직렬 가능성을 보장하지만 교착 상태는 여전히 가능하다.
29	SQL SELECT 질의의 단순화한 논리적 처리 순서는 무엇인가?	CTE, 윈도 함수, 집합 연산이 없는 질의에서는 FROM/JOIN → WHERE → GROUP BY와 집계 → HAVING → SELECT → DISTINCT → ORDER BY → LIMIT/OFFSET이다. 이는 논리 모델이며 옵티마이저의 실제 물리 실행 순서와 같을 필요는 없다.
30	B+ 트리가 데이터베이스 인덱스와 범위 질의에 유용한 이유는 무엇인가?	높은 분기 수가 트리를 얕게 유지해 페이지 접근을 줄인다. 정렬된 키와 연결된 잎이 범위 스캔을 지원한다. 해시 인덱스는 동등 비교 검색용이며 같은 정렬 기반 범위 접근을 본질적으로 제공하지는 않는다.
31	크루스칼과 프림 알고리즘은 최소 신장 트리를 어떻게 만드는가?	연결된 가중 무방향 그래프에서 크루스칼은 간선을 가중치 오름차순으로 보고 Union–Find로 사이클을 만드는 간선을 거부한다. 프림은 트리 내부와 외부 정점을 잇는 최소 가중치 간선을 반복 선택해 하나의 트리를 확장한다.
32	동적 계획법은 왜 여러 최적화 문제에 유용한가?	최적 부분 구조가 있으면 전체 최적해를 부분 문제의 최적해로 표현할 수 있다. 부분 문제가 겹칠 때 답을 저장하면 반복 작업을 피한다. 상태 정의와 점화식이 원래 문제를 올바르게 나타내야 한다.