-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheap_lecture.html
More file actions
447 lines (393 loc) · 27.7 KB
/
Copy pathheap_lecture.html
File metadata and controls
447 lines (393 loc) · 27.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
<!DOCTYPE html>
<html lang="ko">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>힙(Heap) 완전 정복</title>
<link href="https://fonts.googleapis.com/css2?family=Noto+Sans+KR:wght@300;400;500;700&family=JetBrains+Mono:wght@400;600&family=Gowun+Batang:wght@400;700&display=swap" rel="stylesheet">
<link rel="stylesheet" href="study_notes.css">
</head>
<body>
<nav>
<a class="nav-logo" href="index.html">// heap.md</a>
<div class="nav-links">
<a class="nav-link" href="index.html">홈</a>
<a class="nav-link active" href="#binary-tree">이진 트리</a>
<a class="nav-link" href="#heap-def">힙 정의</a>
<a class="nav-link" href="#complexity">시간복잡도</a>
<a class="nav-link" href="#array-map">배열 매핑</a>
<a class="nav-link" href="#priority-queue">우선순위 큐</a>
<a class="nav-link" href="#problem">문제 해설</a>
</div>
<div class="nav-actions">
<button class="theme-toggle" type="button" data-theme-toggle aria-label="테마 전환">Light</button>
</div>
</nav>
<main>
<div class="hero">
<div class="hero-tag">// DATA STRUCTURE · ALGORITHM</div>
<h1 class="hero-title">힙(Heap)<span>과</span><br>우선순위 큐</h1>
<p class="hero-sub">이진 트리의 구조적 특성이 O(log N)을 보장하는 원리부터, 프로그래머스 '더 맵게' 문제 풀이까지 단계별로 해설합니다.</p>
</div>
<!-- ── 1. 이진 트리 ───────────────────────────────────────── -->
<section class="section" id="binary-tree">
<div class="section-header">
<span class="section-num">01</span>
<h2 class="section-title">이진 트리 (Binary Tree)</h2>
</div>
<p>이진 트리는 각 노드가 <strong>최대 두 개의 자식 노드</strong>를 가질 수 있는 계층적 자료구조입니다. 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분됩니다.</p>
<div class="card-grid">
<div class="card">
<div class="card-head text-green">루트 노드 (Root)</div>
<div class="card-desc">트리의 최상단, 부모가 없는 유일한 노드</div>
</div>
<div class="card">
<div class="card-head text-blue">리프 노드 (Leaf)</div>
<div class="card-desc">자식이 없는 최하단 노드들</div>
</div>
<div class="card">
<div class="card-head text-amber">높이 (Height)</div>
<div class="card-desc">루트에서 가장 깊은 리프까지의 거리</div>
</div>
<div class="card">
<div class="card-head text-purple">레벨 (Level)</div>
<div class="card-desc">루트가 레벨 0, 아래로 내려갈수록 +1</div>
</div>
</div>
<p>힙의 근간이 되는 <strong>완전 이진 트리(Complete Binary Tree)</strong>는 추가 조건이 있습니다.</p>
<div class="highlight-box">
<strong>완전 이진 트리의 조건</strong><br>
① 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있다.<br>
② 마지막 레벨의 노드는 반드시 <strong>왼쪽부터 순서대로</strong> 채워진다.
</div>
<div class="tree-wrap">
<div class="tree-label">완전 이진 트리 (N=10) — 레벨·높이 구조</div>
<svg width="100%" viewBox="0 0 620 270" style="display:block;max-width:620px;font-family:'Noto Sans KR',sans-serif">
<line x1="310" y1="38" x2="175" y2="108" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="310" y1="38" x2="445" y2="108" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="175" y1="108" x2="108" y2="178" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="175" y1="108" x2="242" y2="178" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="445" y1="108" x2="378" y2="178" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="445" y1="108" x2="512" y2="178" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="108" y1="178" x2="75" y2="238" stroke="var(--border)" stroke-width="1.5"/>
<line x1="108" y1="178" x2="141" y2="238" stroke="var(--border)" stroke-width="1.5"/>
<line x1="242" y1="178" x2="209" y2="238" stroke="var(--border)" stroke-width="1.5"/>
<line x1="242" y1="178" x2="275" y2="238" stroke="var(--border)" stroke-width="1.5"/>
<!-- level labels -->
<text x="14" y="42" font-size="10" fill="var(--text3)" font-family="'JetBrains Mono',monospace">lv.0</text>
<text x="14" y="112" font-size="10" fill="var(--text3)" font-family="'JetBrains Mono',monospace">lv.1</text>
<text x="14" y="182" font-size="10" fill="var(--text3)" font-family="'JetBrains Mono',monospace">lv.2</text>
<text x="14" y="242" font-size="10" fill="var(--text3)" font-family="'JetBrains Mono',monospace">lv.3</text>
<!-- height brace -->
<line x1="590" y1="38" x2="590" y2="238" stroke="var(--green2)" stroke-width="1"/>
<line x1="585" y1="38" x2="590" y2="38" stroke="var(--green2)" stroke-width="1"/>
<line x1="585" y1="238" x2="590" y2="238" stroke="var(--green2)" stroke-width="1"/>
<text x="596" y="142" font-size="10" fill="var(--green)" font-family="'JetBrains Mono',monospace">H=3</text>
<!-- root -->
<circle cx="310" cy="38" r="22" fill="var(--green-dim)" stroke="var(--green)" stroke-width="2"/>
<text x="310" y="32" text-anchor="middle" font-size="9" fill="var(--green)" font-family="'JetBrains Mono',monospace">root</text>
<text x="310" y="44" text-anchor="middle" font-size="13" font-weight="700" fill="var(--green)">●</text>
<!-- lv1 -->
<circle cx="175" cy="108" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="175" y="108" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text2)">●</text>
<circle cx="445" cy="108" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="445" y="108" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text2)">●</text>
<!-- lv2 -->
<circle cx="108" cy="178" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="108" y="178" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text2)">●</text>
<circle cx="242" cy="178" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="242" y="178" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text2)">●</text>
<circle cx="378" cy="178" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="378" y="178" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text2)">●</text>
<circle cx="512" cy="178" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="512" y="178" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text2)">●</text>
<!-- lv3 leaf -->
<circle cx="75" cy="238" r="18" fill="var(--blue-dim)" stroke="var(--blue)" stroke-width="1"/>
<text x="75" y="238" text-anchor="middle" dominant-baseline="central" font-size="10" fill="var(--blue)">leaf</text>
<circle cx="141" cy="238" r="18" fill="var(--blue-dim)" stroke="var(--blue)" stroke-width="1"/>
<text x="141" y="238" text-anchor="middle" dominant-baseline="central" font-size="10" fill="var(--blue)">leaf</text>
<circle cx="209" cy="238" r="18" fill="var(--blue-dim)" stroke="var(--blue)" stroke-width="1"/>
<text x="209" y="238" text-anchor="middle" dominant-baseline="central" font-size="10" fill="var(--blue)">leaf</text>
<circle cx="275" cy="238" r="18" fill="var(--blue-dim)" stroke="var(--blue)" stroke-width="1"/>
<text x="275" y="238" text-anchor="middle" dominant-baseline="central" font-size="10" fill="var(--blue)">leaf</text>
<text x="310" y="262" text-anchor="middle" font-size="10" fill="var(--text3)" font-family="'JetBrains Mono',monospace">← 왼쪽부터 채워짐</text>
</svg>
</div>
<div class="highlight-box blue">
<strong>핵심 공식: H = ⌊log₂N⌋</strong><br>
N=10 → H=3 | N=100 → H=6 | N=1,000 → H=9 | N=1,000,000 → H=19<br>
<span class="text-subtle">노드가 1,000배 늘어도 높이는 3배 증가에 불과합니다. 이것이 O(log N)의 근거입니다.</span>
</div>
</section>
<hr class="divider">
<!-- ── 2. 힙 정의 ─────────────────────────────────────────── -->
<section class="section" id="heap-def">
<div class="section-header">
<span class="section-num">02</span>
<h2 class="section-title">힙 (Heap)</h2>
</div>
<p>힙은 <strong>완전 이진 트리</strong>에 <strong>힙 속성(Heap Property)</strong>이라는 추가 규칙을 부여한 자료구조입니다. 최댓값 또는 최솟값을 O(1)에 조회하기 위해 설계되었습니다.</p>
<div class="card-grid with-top-gap">
<div class="card green">
<div class="card-head text-green">최소 힙 (Min Heap)</div>
<div class="card-desc">부모 ≤ 자식 (항상 성립)<br>루트 = 전체 <strong class="text-main">최솟값</strong><br>Java PriorityQueue 기본값</div>
</div>
<div class="card coral">
<div class="card-head text-coral">최대 힙 (Max Heap)</div>
<div class="card-desc">부모 ≥ 자식 (항상 성립)<br>루트 = 전체 <strong class="text-main">최댓값</strong><br>Collections.reverseOrder() 사용</div>
</div>
</div>
<div class="tree-wrap">
<div class="tree-label">최소 힙 (Min Heap) — 부모 ≤ 자식이 항상 성립 / 루트 = 최솟값</div>
<svg width="100%" viewBox="0 0 620 280" style="display:block;max-width:620px;font-family:'Noto Sans KR',sans-serif">
<line x1="310" y1="42" x2="175" y2="118" stroke="var(--green2)" stroke-width="1.5"/>
<line x1="310" y1="42" x2="445" y2="118" stroke="var(--green2)" stroke-width="1.5"/>
<line x1="175" y1="118" x2="108" y2="192" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="175" y1="118" x2="242" y2="192" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="445" y1="118" x2="378" y2="192" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="445" y1="118" x2="512" y2="192" stroke="var(--border2)" stroke-width="1.5"/>
<line x1="108" y1="192" x2="75" y2="255" stroke="var(--border)" stroke-width="1.5"/>
<line x1="108" y1="192" x2="141" y2="255" stroke="var(--border)" stroke-width="1.5"/>
<line x1="242" y1="192" x2="209" y2="255" stroke="var(--border)" stroke-width="1.5"/>
<line x1="242" y1="192" x2="275" y2="255" stroke="var(--border)" stroke-width="1.5"/>
<!-- 힙속성 annotation -->
<text x="336" y="82" font-size="10" fill="var(--green)" font-family="'JetBrains Mono',monospace">2≤5 ✓</text>
<text x="390" y="82" font-size="10" fill="var(--green)" font-family="'JetBrains Mono',monospace">2≤8 ✓</text>
<!-- root -->
<circle cx="310" cy="42" r="28" fill="var(--green-dim)" stroke="var(--green)" stroke-width="2"/>
<text x="310" y="35" text-anchor="middle" font-size="9" fill="var(--green)" font-family="'JetBrains Mono',monospace">MIN</text>
<text x="310" y="50" text-anchor="middle" dominant-baseline="central" font-size="18" font-weight="700" fill="var(--green)">2</text>
<!-- lv1 -->
<circle cx="175" cy="118" r="22" fill="var(--green-dim)" stroke="var(--green2)" stroke-width="1.5"/>
<text x="175" y="118" text-anchor="middle" dominant-baseline="central" font-size="15" font-weight="600" fill="var(--green)">5</text>
<circle cx="445" cy="118" r="22" fill="var(--green-dim)" stroke="var(--green2)" stroke-width="1.5"/>
<text x="445" y="118" text-anchor="middle" dominant-baseline="central" font-size="15" font-weight="600" fill="var(--green)">8</text>
<!-- lv2 -->
<circle cx="108" cy="192" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="108" y="192" text-anchor="middle" dominant-baseline="central" font-size="14" fill="var(--text2)">12</text>
<circle cx="242" cy="192" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="242" y="192" text-anchor="middle" dominant-baseline="central" font-size="14" fill="var(--text2)">9</text>
<circle cx="378" cy="192" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="378" y="192" text-anchor="middle" dominant-baseline="central" font-size="14" fill="var(--text2)">20</text>
<circle cx="512" cy="192" r="20" fill="var(--bg3)" stroke="var(--border2)" stroke-width="1"/>
<text x="512" y="192" text-anchor="middle" dominant-baseline="central" font-size="14" fill="var(--text2)">15</text>
<!-- lv3 -->
<circle cx="75" cy="255" r="18" fill="var(--bg3)" stroke="var(--border)" stroke-width="1"/>
<text x="75" y="255" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text3)">25</text>
<circle cx="141" cy="255" r="18" fill="var(--bg3)" stroke="var(--border)" stroke-width="1"/>
<text x="141" y="255" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text3)">30</text>
<circle cx="209" cy="255" r="18" fill="var(--bg3)" stroke="var(--border)" stroke-width="1"/>
<text x="209" y="255" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text3)">18</text>
<circle cx="275" cy="255" r="18" fill="var(--bg3)" stroke="var(--border)" stroke-width="1"/>
<text x="275" y="255" text-anchor="middle" dominant-baseline="central" font-size="13" fill="var(--text3)">11</text>
</svg>
</div>
<p class="mt-half">힙은 <strong>완전 정렬이 아닙니다.</strong> 부모가 자식보다 작다는 것만 보장하며, 형제 노드 사이에는 순서 보장이 없습니다. (예: 위 트리에서 9와 20의 위치는 바뀌어도 유효한 힙입니다)</p>
</section>
<hr class="divider">
<!-- ── 3. 시간복잡도 ──────────────────────────────────────── -->
<section class="section" id="complexity">
<div class="section-header">
<span class="section-num">03</span>
<h2 class="section-title">시간복잡도 — 왜 O(log N)인가</h2>
</div>
<p>힙의 모든 핵심 연산이 O(log N)인 이유는 하나입니다. <strong>완전 이진 트리의 높이가 ⌊log₂N⌋이기 때문</strong>입니다. 삽입과 삭제 모두 트리를 위아래로 한 번만 이동하며, 최대 이동 횟수 = 높이 = log N입니다.</p>
<!-- 삽입 -->
<div class="section-intro">
<span class="section-kicker green">OFFER / PUSH — Heapify Up (위로 올라가기)</span>
<p class="section-copy">새 값을 배열 맨 끝(= 트리 마지막 리프)에 추가한 뒤, 부모보다 작으면 교환하며 위로 올라갑니다. 루트 도달 또는 힙 조건 만족 시 종료합니다.</p>
</div>
<div class="tree-wrap">
<div class="tree-label">삽입 시뮬레이션 — 값 <span style="color:var(--amber)">3</span> 추가 (최소 힙: [2,5,8,12,9,20,15,25,30,18])</div>
<div class="progress-steps" id="ins-steps">
<div class="ps active">0. 리프 삽입</div>
<div class="ps">1. 비교 #1</div>
<div class="ps">2. 비교 #2</div>
<div class="ps">3. 완료</div>
</div>
<svg id="ins-svg" width="100%" viewBox="0 0 620 280" style="display:block;max-width:620px;font-family:'Noto Sans KR',sans-serif"></svg>
<div class="step-ctrl">
<button class="btn" id="ins-prev" data-action="prev" disabled>← 이전</button>
<button class="btn primary" id="ins-next" data-action="next">다음 →</button>
<button class="btn" id="ins-reset" data-action="reset">↺ 처음</button>
<span id="ins-badge" style="display:none" class="badge">✓ 완료 (2회 교환)</span>
</div>
<div class="step-log" id="ins-log">새 값 3을 맨 마지막 위치(인덱스 10)에 삽입합니다. 완전 이진 트리 구조를 유지합니다.</div>
</div>
<!-- 삭제 -->
<div class="section-intro tight">
<span class="section-kicker coral">POLL / POP — Heapify Down (아래로 내려가기)</span>
<p class="section-copy">루트(최솟값)를 꺼내고, 배열 마지막 노드를 루트 자리로 이동합니다. 두 자식 중 작은 쪽과 비교해서 부모가 더 크면 교환하며 아래로 내려갑니다.</p>
</div>
<div class="tree-wrap">
<div class="tree-label">삭제 시뮬레이션 — 루트(최솟값 <span style="color:var(--green)">2</span>) 꺼내기</div>
<div class="progress-steps" id="del-steps">
<div class="ps active">0. 루트 제거, 마지막→루트</div>
<div class="ps">1. 자식 비교 #1</div>
<div class="ps">2. 자식 비교 #2</div>
<div class="ps">3. 완료</div>
</div>
<svg id="del-svg" width="100%" viewBox="0 0 620 265" style="display:block;max-width:620px;font-family:'Noto Sans KR',sans-serif"></svg>
<div class="step-ctrl">
<button class="btn" id="del-prev" data-action="prev" disabled>← 이전</button>
<button class="btn primary" id="del-next" data-action="next">다음 →</button>
<button class="btn" id="del-reset" data-action="reset">↺ 처음</button>
<span id="del-badge" style="display:none" class="badge">✓ 완료 (2회 교환)</span>
</div>
<div class="step-log" id="del-log">루트(2)를 꺼내고, 마지막 노드 18을 루트 자리로 이동합니다.</div>
</div>
<!-- 복잡도 표 -->
<div class="table-wrap with-top-gap">
<table>
<thead>
<tr><th>연산</th><th>힙 (PriorityQueue)</th><th>정렬 배열</th><th>이유</th></tr>
</thead>
<tbody>
<tr><td>최솟값 조회 peek()</td><td><code class="good">O(1)</code></td><td><code class="good">O(1)</code></td><td>루트 = 배열[0] 직접 접근</td></tr>
<tr><td>삽입 offer()</td><td><code class="good">O(log N)</code></td><td><code class="bad">O(N)</code></td><td>힙: 높이만큼만 / 배열: 자리 찾아 이동</td></tr>
<tr><td>최솟값 삭제 poll()</td><td><code class="good">O(log N)</code></td><td><code class="good">O(1)</code></td><td>힙: 재정렬 필요 / 배열: 그냥 제거</td></tr>
<tr><td>임의 검색</td><td><code>O(N)</code></td><td><code class="good">O(log N)</code></td><td>힙: 이진탐색 불가 / 배열: 이진탐색 가능</td></tr>
</tbody>
</table>
</div>
</section>
<hr class="divider">
<!-- ── 4. 배열 매핑 ───────────────────────────────────────── -->
<section class="section" id="array-map">
<div class="section-header">
<span class="section-num">04</span>
<h2 class="section-title">배열 인덱스 매핑</h2>
</div>
<p>힙은 트리 구조이지만 실제 메모리는 <strong>1차원 배열</strong>에 저장됩니다. 완전 이진 트리를 레벨 순서대로 나열하면 인덱스 산술만으로 부모·자식 위치를 O(1)에 계산할 수 있기 때문입니다. 포인터가 전혀 필요 없고, 메모리가 연속 배치되어 캐시 효율도 우수합니다.</p>
<div class="highlight-box blue">
<strong>인덱스 공식 (0-based · Java PriorityQueue 기준)</strong><br>
<div class="formula-row">
<div><span class="text-subtle">부모 인덱스</span><br><span class="formula">(i - 1) / 2</span></div>
<div><span class="text-subtle">왼쪽 자식</span><br><span class="formula">2 * i + 1</span></div>
<div><span class="text-subtle">오른쪽 자식</span><br><span class="formula">2 * i + 2</span></div>
</div>
</div>
<div class="tree-wrap">
<div class="tree-label">노드를 클릭하면 부모·자식 인덱스 계산 결과를 확인합니다</div>
<svg id="map-svg" class="svg-block clickable" width="100%" viewBox="0 0 620 265"></svg>
<div class="array-panel-head">
<div class="array-panel-label">배열 표현 (레벨 순서대로)</div>
<div class="array-row" id="arr-display"></div>
</div>
<div class="legend-row">
<span class="text-amber">■ 선택 노드</span>
<span class="text-blue">■ 부모</span>
<span class="text-coral">■ 자식</span>
</div>
<div class="step-log" id="map-log">노드를 클릭하면 인덱스 계산 과정을 보여줍니다.</div>
</div>
</section>
<hr class="divider">
<!-- ── 5. 우선순위 큐 ─────────────────────────────────────── -->
<section class="section" id="priority-queue">
<div class="section-header">
<span class="section-num">05</span>
<h2 class="section-title">우선순위 큐 (Priority Queue)</h2>
</div>
<p>우선순위 큐는 FIFO(선입선출) 방식의 일반 큐와 달리, <strong>우선순위가 가장 높은(= 값이 가장 작은) 데이터가 항상 먼저 나오는</strong> 추상 자료형입니다. 내부 구현으로 힙을 사용합니다.</p>
<div class="card-grid">
<div class="card blue">
<div class="card-head text-blue">일반 큐 (Queue)</div>
<div class="card-desc">먼저 들어온 순서대로 나옴 — FIFO<br>삽입 O(1), 제거 O(1)</div>
</div>
<div class="card green">
<div class="card-head text-green">우선순위 큐 (PQ)</div>
<div class="card-desc">값이 작을수록 먼저 나옴 — 순서 무관<br>삽입 O(log N), 제거 O(log N)</div>
</div>
</div>
<div class="code-block">
<span class="code-label">// Java — PriorityQueue 핵심 API</span>
<span class="cm">// ① 최소 힙 (기본값) — 작은 값이 먼저 나옴</span>
<span class="ct">PriorityQueue</span><<span class="ct">Integer</span>> pq = <span class="ck">new</span> <span class="ct">PriorityQueue</span><>();
<span class="cm">// ② 최대 힙 — Comparator 역순</span>
<span class="ct">PriorityQueue</span><<span class="ct">Integer</span>> maxPQ = <span class="ck">new</span> <span class="ct">PriorityQueue</span><>(<span class="ct">Collections</span>.<span class="co">reverseOrder</span>());
<span class="cm">// ③ 주요 메서드</span>
pq.<span class="co">offer</span>(<span class="cs">5</span>); <span class="cm">// 삽입 O(log N) — 끝에 추가 후 Heapify Up</span>
pq.<span class="co">peek</span>(); <span class="cm">// 최솟값 확인 O(1) — 루트 조회 (제거 안 함)</span>
pq.<span class="co">poll</span>(); <span class="cm">// 최솟값 제거 O(log N) — 루트 제거 후 Heapify Down</span>
pq.<span class="co">size</span>(); <span class="cm">// 원소 개수 O(1)</span>
pq.<span class="co">isEmpty</span>(); <span class="cm">// 비어있는지 O(1)</span>
</div>
<p>내부적으로 <span class="keyword">offer()</span>는 배열 끝에 추가 후 Heapify Up을, <span class="keyword">poll()</span>은 루트 제거 후 마지막 원소를 루트로 올리고 Heapify Down을 실행합니다. 앞서 확인한 O(log N) 과정과 완전히 동일합니다.</p>
</section>
<hr class="divider">
<!-- ── 6. 문제 해설 ───────────────────────────────────────── -->
<section class="section" id="problem">
<div class="section-header">
<span class="section-num">06</span>
<h2 class="section-title">문제 해설 — 더 맵게</h2>
</div>
<div class="card amber">
<div class="card-head text-amber">문제 정의 (프로그래머스 Lv.2)</div>
<div class="card-desc problem-head">
모든 음식의 스코빌 지수를 K 이상으로 만들어야 합니다.<br>
<strong class="text-main">섞는 공식:</strong> <span class="font-mono text-amber">새 음식 = 가장 작은 값 + (두 번째로 작은 값 × 2)</span><br>
최소 횟수를 반환. 불가능하면 -1 반환.
</div>
</div>
<p>매 단계마다 가장 작은 값 2개를 찾아야 합니다. <strong>이 작업을 반복적으로 효율적으로 수행하는 것이 핵심</strong>입니다.</p>
<div class="highlight-box amber">
<strong>왜 힙을 써야 하는가?</strong><br>
<strong>배열 재정렬 방식:</strong> 매 단계 O(N log N) × 최대 N 단계 = <span style="color:var(--coral)">O(N² log N)</span> → 시간 초과<br>
<strong>최소 힙 방식:</strong> 꺼내기 O(log N) × 2 + 삽입 O(log N) = 단계당 O(log N), 전체 <span style="color:var(--green)">O(N log N)</span> → 통과
</div>
<div class="code-block with-top-gap">
<span class="code-label">// ParkYuBin.java — 전체 풀이</span>
<span class="ck">public int</span> <span class="cf">solution</span>(<span class="ck">int</span>[] scoville, <span class="ck">int</span> K) {
<span class="cm">// ① 모든 값을 최소 힙에 삽입 — O(N log N)</span>
<span class="ct">PriorityQueue</span><<span class="ct">Integer</span>> pq = <span class="ck">new</span> <span class="ct">PriorityQueue</span><>();
<span class="ck">for</span> (<span class="ck">int</span> s : scoville) {
pq.<span class="co">offer</span>(s);
}
<span class="ck">int</span> count = <span class="cs">0</span>;
<span class="cm">// ② peek()으로 루트(최솟값) 확인 — O(1)</span>
<span class="ck">while</span> (pq.<span class="co">peek</span>() < K) {
<span class="cm">// ③ 원소 1개 남았는데 K 미만 → 불가능</span>
<span class="ck">if</span> (pq.<span class="co">size</span>() == <span class="cs">1</span>) <span class="ck">return</span> -<span class="cs">1</span>;
<span class="cm">// ④ 가장 작은 두 값 꺼내기 — 각 O(log N)</span>
<span class="ck">int</span> first = pq.<span class="co">poll</span>(); <span class="cm">// 최솟값 → Heapify Down</span>
<span class="ck">int</span> second = pq.<span class="co">poll</span>(); <span class="cm">// 두 번째 최솟값 → Heapify Down</span>
<span class="cm">// ⑤ 섞어서 다시 삽입 — O(log N)</span>
pq.<span class="co">offer</span>(first + second * <span class="cs">2</span>); <span class="cm">// Heapify Up</span>
count++;
}
<span class="ck">return</span> count;
}
</div>
<!-- 시뮬레이션 -->
<div class="tree-wrap with-top-gap">
<div class="tree-label">
풀이 시뮬레이션 · K = <span class="text-amber">7</span> · 초기: [1, 2, 3, 9, 10, 12]
</div>
<div class="array-panel-label">힙 배열 상태 (루트 = 맨 왼쪽)</div>
<div class="array-row" id="prob-arr"></div>
<div class="step-ctrl mt-md">
<button class="btn" id="prob-prev" data-action="prev" disabled>← 이전</button>
<button class="btn primary" id="prob-next" data-action="next">다음 →</button>
<button class="btn" id="prob-reset" data-action="reset">↺ 처음</button>
<span id="prob-count" class="badge" style="display:none"></span>
</div>
<div class="step-log" id="prob-log">초기 상태. 최솟값 1이 루트. K=7보다 작으므로 섞기를 시작합니다.</div>
</div>
<div class="highlight-box mt-lg">
<strong>최종 정리</strong><br>
<span class="keyword">peek()</span>: 루트 읽기 → O(1) |
<span class="keyword">offer()</span>: Heapify Up → O(log N) |
<span class="keyword">poll()</span>: Heapify Down → O(log N)<br>
전체 시간복잡도: <strong>O(N log N)</strong> — 완전 이진 트리의 높이가 log N임을 이용한 결과
</div>
</section>
<footer class="site-footer" id="footer">
<div class="footer-copy">Algo Crushers study notes</div>
<a class="footer-link" href="https://github.com/algo-crushers" target="_blank" rel="noreferrer">github.com/algo-crushers</a>
</footer>
</main>
<script type="module" src="study_notes_theme.js"></script>
<script type="module" src="heap_lecture.js"></script>
</body>
</html>