II-1 Skip List의 평균 높이·시간·공간 — 완전 초보자 Masterclass
먼저 이 문제의 정체부터
Skip list는 정렬 연결 리스트 위에 일부 원소만 뽑은 빠른 차선을 여러 층 쌓은 구조입니다. 각 원소가 다음 층으로 올라갈 확률이 p이므로 층별 원소 수는 \(n, \text{pn}, p^{2}n\)n, pn, p²n처럼 줄어듭니다.
일반도로 위에 확률적으로 진입하는 급행도로를 여러 층 둔 내비게이션이라고 생각하세요.
이 문항의 풀이 목표는 정답 label 암기가 아니라 다음 절차를 재현하는 것입니다. n,pn,\(p^{2}\)p²n,…을 쓰고 높이·연산시간·저장공간을 각각 따로 판정합니다.
복기 시험지는 공식 답안지가 아니므로 문언과 selection rule이 충돌하면 그 사실을 표시하고 현재 강의 자료로 각 보기를 독립 검증합니다.
0. 필요한 개념을 처음부터 배우기
개념 1 · 문제의 정체를 생활 언어로
Skip list는 정렬 연결 리스트 위에 일부 원소만 뽑은 빠른 차선을 여러 층 쌓은 구조입니다. 각 원소가 다음 층으로 올라갈 확률이 p이므로 층별 원소 수는 \(n, \text{pn}, p^{2}n\)n, pn, p²n처럼 줄어듭니다.
이 문항에서 가장 먼저 붙잡을 문장은 '레벨 i의 기대 원소 수는 \(\text{np}^{i}\)np^i이다.'입니다. 용어를 외우기 전에 이 문장이 어떤 상황을 말하는지 작은 예를 만들어 확인합니다.
이 절에서 꼭 기억할 것
- 레벨 i의 기대 원소 수는 \(\text{np}^{i}\)
np^i이다. - n,pn,\(p^{2}\)
p²n,…을 쓰고 높이·연산시간·저장공간을 각각 따로 판정합니다.
개념 2 · 반드시 알아야 하는 네 개의 뼈대
첫째, 레벨 i의 기대 원소 수는 \(\text{np}^{i}\)np^i이다. 둘째, 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다.
셋째, 기대 높이와 search/insert/delete 시간은 로그 규모다. 넷째, 복기 문항은 exactly-two라고 적혔지만 현재 문언에서는 C만 명확히 참이므로 문항 누락 가능성을 표시해야 한다. 이 네 문장을 서로 섞지 않고 별도 체크박스로 기억해야 합니다.
이 절에서 꼭 기억할 것
- 레벨 i의 기대 원소 수는 \(\text{np}^{i}\)
np^i이다. - 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)
n(1+p+p²+…)=n/(1-p)이다. - 기대 높이와 search/insert/delete 시간은 로그 규모다.
- 복기 문항은 exactly-two라고 적혔지만 현재 문언에서는 C만 명확히 참이므로 문항 누락 가능성을 표시해야 한다.
개념 3 · 강의 정의를 초보자 언어로 해체
스킵 리스트(skip list)는 여러 높이의 고속도로 진입 램프처럼 일부 노드를 건너뛰게 한다. 블룸 필터(Bloom filter)는 '확실히 없음' 또는 '아마 있음'만 말해 주는 스탬프 판과 같다.
스킵 리스트는 확률 p로 노드를 상위 레벨에 복제한다. 해시 테이블(hash table)은 결정적 해시 함수로 키를 버킷에 매핑한다. 블룸 필터는 k개 해시 함수가 지정한 비트를 사용해 포함 여부(membership)를 근사 판정한다.
수식으로 정확히 쓰기
핵심 규칙스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
이 절에서 꼭 기억할 것
- 기대값
- 기하급수
- 해시 충돌
- 비트 배열
개념 4 · 성립 조건·불변식·경계 사례
스킵 리스트의 기대 공간은 n/(1-p), 높이와 탐색 시간은 기대 \(\Theta(\log n)\)Θ(log n)이다. 표준 블룸 필터는 삭제하지 않는다면 거짓 음성(false negative)은 없지만 거짓 양성(false positive)은 가능하다.
완전 해싱(perfect hashing)과 일반 해싱, 카운팅 블룸 필터(counting Bloom filter)와 표준 블룸 필터를 구분한다.
이 절에서 꼭 기억할 것
- 전제조건을 생략하지 않는다.
- 존재 명제와 모든 경우 명제를 구분한다.
- 강한 단어는 작은 반례로 우선 검사한다.
개념 5 · 실행시간과 비용을 읽는 법
스킵 리스트의 탐색·삽입·삭제는 기대 \(\Theta(\log n)\)Θ(log n), 공간은 기대 \(\Theta(n)\)Θ(n)이다. 해시 테이블은 키가 잘 분산되면 기대 \(O(1)\)O(1), 최악에는 \(O(n)\)O(n)이다.
O는 upper bound이고 Θ는 tight bound입니다. 자료구조 연산 비용은 ADT 이름만이 아니라 구현과 유지하는 보조 정보에 따라 달라질 수 있습니다.
이 절에서 꼭 기억할 것
- O와 Θ를 같은 뜻으로 읽지 않는다.
- 구현 의존성을 확인한다.
- 필요 없는 runtime 주장도 억지로 만들지 않는다.
개념 6 · 정확히 두 개 선택(exactly two) 판정법
선택지를 서로 비교해 '가장 그럴듯한 두 개'를 고르지 않습니다. A부터 D까지 각각 독립적인 참·거짓 명제로 바꾸고 근거 또는 반례를 붙인 뒤 참의 개수를 셉니다.
현재 복기 데이터에서 판정된 정답 표시는 C입니다. 정답 수와 섹션 규칙이 충돌하는 문항은 억지로 두 개를 만들지 않고 복기 문언 누락 가능성을 명시합니다.
수식으로 정확히 쓰기
핵심 규칙선택 규칙: 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
핵심 규칙검증된 선택지: C
이 절에서 꼭 기억할 것
- 평균 높이·시간·공간을 서로 바꾸지 않는다.
- 레벨 크기 n,pn,\(p^{2}\)
p²n,…과 기하급수를 적는다.
1. 시험장에서 따라 할 풀이 순서
선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)(exactly(two))
Skip List의 평균 높이·시간·공간
레벨 i의 기대 원소 수는 \(\text{np}^{i}\)np^i이다. | 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다. | 기대 높이와 search/insert/delete 시간은 로그 규모다.
선택지 \(A =\)A =거짓
선택 규칙을 먼저 적는다
이 문항의 규칙은 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))입니다. 마지막에 참 개수를 반드시 재검산합니다.핵심 규칙선택 규칙 = 정확히 두 개 선택\((\text{exactly}_{\text{two}})\)
(exactly(two))문장을 쉬운 한국어로 다시 쓴다
n개 원소와 승격 확률 p를 갖는 skip list에 관한 옳은 설명 두 개를 고르시오.
핵심 규칙Skip List의 평균 높이·시간·공간
핵심 도구를 종이에 꺼낸다
n,pn,\(p^{2}\)
p²n,…을 쓰고 높이·연산시간·저장공간을 각각 따로 판정합니다.핵심 규칙레벨 i의 기대 원소 수는 \(\text{np}^{i}\)
np^i이다. | 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다. | 기대 높이와 search/insert/delete 시간은 로그 규모다.선택지 A를 독립 판정한다
강의 모델의 평균 높이는 \(\Theta(\log_{1/p} n)\)
Θ(log₁/p} n)이므로 \(\Omega(\log n)\)Ω(log n)에도 속한다.\[선택지 A = 거짓\]선택지 A = 거짓선택지 B를 독립 판정한다
탐색 경로를 포함한 기대 시간은 \(\Theta(\log n)\)
Θ(log n)이다.\[선택지 B = 거짓\]선택지 B = 거짓선택지 C를 독립 판정한다
기대 노드 복제 수 \(n(1+p+p^{2}+…)=n/(1-p)\)
n(1+p+p²+…)=n/(1-p)이다.\[선택지 C = 참\]선택지 C = 참선택지 D를 독립 판정한다
기대 탐색 시간은 \(\Theta(\log n)\)
Θ(log n)이다.\[선택지 D = 거짓\]선택지 D = 거짓정답 수와 애매성을 재검산한다
참으로 판정된 선택지는 C입니다. 복기 섹션 규칙과 수가 다르면 원문 누락 가능성을 기록하고 거짓을 참으로 조작하지 않습니다.
\[검증된 정답 = C\]검증된 정답 = C
2. 이 문제를 실제로 끝까지 풀기
Skip list는 정렬 연결 리스트 위에 일부 원소만 뽑은 빠른 차선을 여러 층 쌓은 구조입니다. 각 원소가 다음 층으로 올라갈 확률이 p이므로 층별 원소 수는 \(n, \text{pn}, p^{2}n\)n, pn, p²n처럼 줄어듭니다.
풀이를 시작할 때 다음 네 사실을 먼저 적습니다. (1) 레벨 i의 기대 원소 수는 \(\text{np}^{i}\)np^i이다. (2) 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다. (3) 기대 높이와 search/insert/delete 시간은 로그 규모다. (4) 복기 문항은 exactly-two라고 적혔지만 현재 문언에서는 C만 명확히 참이므로 문항 누락 가능성을 표시해야 한다.
선택지 A는 거짓입니다. 강의 모델의 평균 높이는 \(\Theta(\log_{1/p} n)\)Θ(log₁/p} n)이므로 \(\Omega(\log n)\)Ω(log n)에도 속한다. 가장 작은 확인 예는 \(p=1/2\)p=1/2에서 레벨별 기대 원소 수 n,n/2,n/4,…를 본다.
선택지 B는 거짓입니다. 탐색 경로를 포함한 기대 시간은 \(\Theta(\log n)\)Θ(log n)이다. 가장 작은 확인 예는 균형 잡힌 임의 레벨에서는 전체 n개를 훑지 않는다.
선택지 C는 참입니다. 기대 노드 복제 수 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다.
선택지 D는 거짓입니다. 기대 탐색 시간은 \(\Theta(\log n)\)Θ(log n)이다. 가장 작은 확인 예는 각 레벨에서 기대 상수 번 이동하고 레벨 수가 로그다.
따라서 현재 문언에서 참으로 검증된 선택지는 C입니다. 선택지는 서로 상대평가하지 않고 각 문장을 정의·전제·반례로 독립 검증했습니다.
시험장에서 쓸 압축 절차는 다음과 같습니다. n,pn,\(p^{2}\)p²n,…을 쓰고 높이·연산시간·저장공간을 각각 따로 판정합니다. 시간이 부족해도 '항상(always)', '오직(only)', '모든(every)' 같은 강한 단어와 전제조건, O와 Θ를 먼저 확인하면 대표 함정을 피할 수 있습니다.
3. 선택지 A–D를 한 줄도 건너뛰지 않고 판정하기
-
A거짓
강의 모델의 평균 높이는 \(\Theta(\log_{1/p} n)\)
Θ(log₁/p} n)이므로 \(\Omega(\log n)\)Ω(log n)에도 속한다.빠른 확인법: \(p=1/2\)
p=1/2에서 레벨별 기대 원소 수 n,n/2,n/4,…를 본다. -
B거짓
탐색 경로를 포함한 기대 시간은 \(\Theta(\log n)\)
Θ(log n)이다.빠른 확인법: 균형 잡힌 임의 레벨에서는 전체 n개를 훑지 않는다.
-
C참 — 정답 후보
기대 노드 복제 수 \(n(1+p+p^{2}+…)=n/(1-p)\)
n(1+p+p²+…)=n/(1-p)이다.빠른 확인법: 평균 저장 공간은 n/(1-p)이다.
-
D거짓
기대 탐색 시간은 \(\Theta(\log n)\)
Θ(log n)이다.빠른 확인법: 각 레벨에서 기대 상수 번 이동하고 레벨 수가 로그다.
4. 초보자가 가장 자주 틀리는 이유
- 평균 높이·시간·공간을 서로 바꾸지 않는다.
- exactly-two라는 이유만으로 근거 없이 두 선택지를 맞다고 만든다.
- 선택지의 절반만 맞는데 결합 문장 전체를 참으로 판정한다.
- always, only, every 같은 강한 단어를 놓친다.
- 정의와 구현, 전제조건과 결론, upper bound와 tight bound를 섞는다.
- 작은 예 하나로 거짓은 깰 수 있지만 참인 보편 명제를 증명했다고 착각한다.
- 복기 시험지가 공식 원문·공식 답안이라는 전제로 애매성을 숨긴다.
- 용어를 암기한 소리만 따라가고 실제 상태나 한 단계 실행을 그리지 않는다.
5. 시험 답안 템플릿
n,pn,\(p^{2}\)p²n,…을 쓰고 높이·연산시간·저장공간을 각각 따로 판정합니다. 각 선택지를 정의와 전제에 따라 독립 판정하면 참인 label은 C이다. 핵심 근거: 레벨 i의 기대 원소 수는 \(\text{np}^{i}\)np^i이다. 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다. 기대 높이와 search/insert/delete 시간은 로그 규모다. 복기 문항은 exactly-two라고 적혔지만 현재 문언에서는 C만 명확히 참이므로 문항 누락 가능성을 표시해야 한다.
6. 스스로 이해했는지 확인
II-1의 주제를 한 문장으로 설명하면?
정답: Skip list는 정렬 연결 리스트 위에 일부 원소만 뽑은 빠른 차선을 여러 층 쌓은 구조입니다. 각 원소가 다음 층으로 올라갈 확률이 p이므로 층별 원소 수는 \(n, \text{pn}, p^{2}n\)n, pn, p²n처럼 줄어듭니다.
이 문제에서 가장 먼저 꺼낼 판정법은?
정답: n,pn,\(p^{2}\)p²n,…을 쓰고 높이·연산시간·저장공간을 각각 따로 판정합니다.
핵심 사실 네 가지 중 첫 번째는?
정답: 레벨 i의 기대 원소 수는 \(\text{np}^{i}\)np^i이다.
핵심 사실 네 가지 중 두 번째는?
정답: 전체 기대 저장량은 \(n(1+p+p^{2}+…)=n/(1-p)\)n(1+p+p²+…)=n/(1-p)이다.
가장 위험한 함정은?
정답: 평균 높이·시간·공간을 서로 바꾸지 않는다.
정답 label은?
정답: C
이 개념의 핵심 정의를 한 문장으로 말하라.
정답: Skip list는 확률 p로 상위 레벨에 복제한다. Hash table은 결정적 hash로 키를 버킷에 매핑한다. Bloom filter는 k개 hash 비트로 근사 membership을 답한다.
판정 전에 확인할 전제 세 가지는 무엇인가?
정답: 기대값, 기하급수, 해시 충돌, 비트 배열
근거 자료
AuD Gedächtnisprotokoll SoSe 2025.md· Multiple Choice II-1
복기된 문언과 선택지; 공식 답안지가 아님AuD Gedächtnisprotokoll SoSe 2025.md· MC section, window 1
2025년 여름학기 객관식 복기 문구, 절 규칙, 문항 I-6·II-1·II-8과 배점입니다. 공식 정답지는 아닙니다.Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 10-20
스킵 리스트의 승격 확률 p, 층별 기대 크기, 평균 높이 \(O(\log_{1/p} n),\)O(log₁/p} n),검색·삽입·삭제의 평균 시간 \(\Theta(\log_{1/p} n)\)Θ(log₁/p} n), 평균 공간 n/(1-p).Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 25-34
해시 테이블은 해시 함수로 키를 배열 위치에 대응시키고 체이닝 등으로 충돌을 해결합니다. 기대 시간 분석에는 균등·독립 분포를 가정하며, 압축이나 암호화가 아니라 조회와 주소 지정에 쓰입니다.Vorlesung\05RandomizedDataStructures-wi.pdf· pp. 35-45
블룸 필터는 k개의 해시 함수와 m비트 배열을 사용합니다. 확인한 비트 중 하나가 0이면 확실히 없고, 모두 1이면 있을 가능성이 있습니다. 표준 삽입 전용 블룸 필터에는 거짓 음성이 없지만 거짓 양성은 생길 수 있습니다.