# 자료구조, 복잡도 분석(Big-O) 및 핵심 알고리즘

> 기초 프로그래밍 지식이 필요한 대학 학부 수준 복습용 카드 32장. 배열, 리스트, 해시, 트리, 힙, 트라이, Union–Find, 블룸 필터와 복잡도를 다룹니다.

- **Canonical URL:** https://flashcards.world/flashcards/sets/077e79ed-afcd-4539-a952-44f3c500255e/
- **Markdown URL:** https://flashcards.world/flashcards/sets/077e79ed-afcd-4539-a952-44f3c500255e.md
- **Level:** basic
- **Languages:** ko → ko
- **Total Cards:** 32

## Flashcards (32 Cards)

| # | Front (Term / Prompt) | Back (Definition / Answer) | Example | Multiple-Choice Options |
| :--- | :--- | :--- | :--- | :--- |
| 1 | 분리 연결 해시 테이블의 기대 연산 비용과 최악의 비용은? | 적재율이 제한되고 해시가 고르게 분포하며 키 연산이 상수 비용이면 검색·삭제는 기대 O(1)이다. 기하급수적 용량 증가를 쓰는 삽입은 기대 분할상환 O(1)이다. 충돌하는 n개 키의 사슬은 O(n)을 초래할 수 있다. |  |  |
| 2 | 경로 압축과 랭크 기준 합치기를 쓰는 union/find의 분할상환 비용은? | 연산당 O(α(n))이다. α는 역 아커만 함수, n은 원소 수다. 초기화는 O(n)이다. 이 경계는 연산열에 대한 것이며 모든 호출의 최악 비용이 상수라는 뜻은 아니다. |  |  |
| 3 | BST의 검색·삽입·삭제는 높이 h에 어떻게 의존하는가? | O(h) 시간이 든다. 균형 트리는 h = O(log n), 사슬은 h = O(n)이다. 기대 O(log n)을 얻으려면 무작위 삽입 순서 같은 가정이 필요하다. |  |  |
| 4 | 음이 아닌 함수 f와 g에 대해 f(n) ∈ O(g(n))는 무엇을 뜻하는가? | 모든 n ≥ n₀에서 f(n) ≤ c·g(n)이 성립하도록 하는 상수 c > 0과 n₀ ≥ 0이 존재한다. |  |  |
| 5 | 경로 압축, 랭크 기준 합치기, 크기 기준 합치기는 어떻게 다른가? | 경로 압축은 방문한 노드가 루트를 가리키도록 바꾼다. 랭크 기준은 낮은 랭크의 루트를 높은 루트 아래에, 크기 기준은 작은 집합을 큰 집합 아래에 붙인다. 랭크는 현재 높이와 같지 않을 수 있다. |  |  |
| 6 | 트라이란 무엇이며 L자 키 검색은 언제 O(L)인가? | 문자 경로에 키를 저장하고 완성된 키를 표시하는 접두사 트리다. 다음 문자로의 각 전이가 O(1)이면 검색은 O(L)이다. |  |  |
| 7 | O, Ω, Θ는 어떻게 다른가? | 각각 점근적 상한, 하한, 상하한이 일치하는 차수의 경계를 나타낸다. 지정한 비용 함수를 설명하며, O 자체가 최악의 경우를 뜻하지는 않는다. |  |  |
| 8 | 이진 힙의 삽입·루트 제거·루트 확인 비용은? | 배열 크기 변경이 필요 없다면 각각 O(log n), O(log n), O(1)이다. 크기 변경은 O(n)일 수 있다. |  |  |
| 9 | 원형 배열 큐는 꺼낸 뒤 원소 이동을 어떻게 피하는가? | 앞·뒤 인덱스를 용량으로 나눈 나머지를 이용해 순환시킨다. 꺼낼 때 앞 인덱스를 옮겨 다른 원소를 이동하지 않고 빈 칸을 재사용한다. |  |  |
| 10 | 레벨 순서는 이진 트리를 어떻게 방문하는가? | FIFO 큐로 깊이별 한 레벨씩 방문한다. 왼쪽 자식을 오른쪽 자식보다 먼저 넣으면 왼쪽에서 오른쪽 순서가 된다. |  |  |
| 11 | AVL 균형 조건은? | 모든 노드에서 높이(왼쪽) − 높이(오른쪽) ∈ {−1, 0, 1}이다. BST 순서 불변식도 만족해야 한다. |  |  |
| 12 | 스택은 어떻게 작동하며 언제 연산이 O(1)인가? | 후입선출(LIFO): 마지막에 넣은 원소를 먼저 꺼낸다. 연결 리스트의 머리에서는 넣기·빼기·맨 위 확인이 O(1)이다. 배열 크기 변경이 있으면 한 번 넣기가 O(n)일 수 있다. |  |  |
| 13 | AVL 삽입 뒤 왼쪽-오른쪽 불균형은 어떻게 고치는가? | 먼저 왼쪽 자식을 왼쪽으로 회전하고, 불균형 노드를 오른쪽으로 회전한다. |  |  |
| 14 | 해시 테이블의 적재율은 무엇이며 왜 크기를 바꾸기도 하는가? | α = n/m으로, n은 저장 항목 수, m은 버킷 또는 슬롯 수다. 구현의 임계값을 넘으면 확장과 재해싱이 일어날 수 있다. 0.75는 보편적인 기준이 아니다. |  |  |
| 15 | 이진 최소 힙을 정의하는 두 성질은? | 완전 이진 트리이며, 각 부모 키가 자식 키보다 크지 않다. 따라서 루트에는 최솟값이 있다. |  |  |
| 16 | 서로소 집합 자료구조에서 find와 union은 무엇을 하는가? | find(x)는 x가 속한 집합의 대표를 반환한다. union(x,y)는 집합이 다르면 합치며, 이미 같은 집합이면 분할은 그대로다. |  |  |
| 17 | 고정 크기 배열의 인덱스 접근이 O(1)인 이유는? | 같은 크기의 칸이 연속되어 주소(i) = 시작주소 + i·칸크기로 계산된다. 주소 계산에 상수 시간이 든다고 가정한다. |  |  |
| 18 | n → ∞일 때 다음 증가율을 느린 순으로 나열하라: n!, n, 1, n², log n, 2ⁿ, n log n. | 점근적으로 1 < log n < n < n log n < n² < 2ⁿ < n!이다. |  |  |
| 19 | 이중 연결 리스트에서 주어진 노드를 O(1)에 삭제할 수 있는 이유는? | 이전·다음 링크로 이웃 노드를 바로 다시 연결할 수 있다. 필요하면 머리·꼬리를 갱신하며, 이전 노드를 검색할 필요가 없다. |  |  |
| 20 | 키가 서로 다른 BST를 중위 순회하면 무엇을 얻는가? | 모든 키를 엄격한 오름차순으로 얻는다. n개 노드를 방문하는 데 O(n)이 든다. |  |  |
| 21 | 삽입만 허용하는 블룸 필터는 어떤 답을 내는가? | 음성이면 삽입된 적이 없고, 양성이면 삽입되었을 가능성이 있다. 해시로 비트 배열의 비트를 설정하므로 거짓 양성은 가능하지만 상태가 온전하면 거짓 음성은 없다. |  |  |
| 22 | 분리 연결법은 해시 충돌을 어떻게 해결하는가? | 각 버킷은 해당 인덱스의 항목들을 모아 두며, 흔히 연결 리스트를 쓴다. 같은 버킷의 서로 다른 키도 별도 항목으로 남는다. |  |  |
| 23 | n개 원소로 아래에서 위로 힙을 만드는 비용은? | O(n)이다. 대부분의 노드는 잎에 가까워 조금만 내려보내면 된다. 노드 높이별 작업량을 합하면 선형이 된다. |  |  |
| 24 | 테이블 검색용 해시 함수는 어떤 성질을 가져야 하는가? | 결정적이어야 하고 예상되는 키를 고르게 분산해야 한다. 고정 크기 키의 해시는 O(1)일 수 있지만, 새로운 L자 문자열의 해시는 보통 O(L)이다. |  |  |
| 25 | 키가 모두 다른 이진 탐색 트리(BST)의 순서 불변식은? | 각 노드에서 왼쪽 서브트리의 모든 키는 더 작고 오른쪽의 모든 키는 더 크다. 이 규칙이 재귀적으로 적용된다. |  |  |
| 26 | 길이가 n이고 인덱스가 0부터인 힙 배열에서 노드 i의 부모와 자식 위치는? | 부모: i>0일 때 ⌊(i−1)/2⌋. 자식: 2i+1과 2i+2이며 인덱스가 n보다 작을 때만 존재한다. 인덱스 0에는 부모가 없다. |  |  |
| 27 | 단일 연결 리스트와 동적 배열의 맨 앞 삽입 및 인덱스 접근을 비교하라. | 리스트: 맨 앞 삽입 O(1), 인덱스 접근 O(n). 배열: 맨 앞 삽입 O(n), 인덱스 접근 O(1). 배열의 맨 앞 삽입은 원소를 이동시킨다. |  |  |
| 28 | 큐의 접근 규칙과 일반적인 연산 비용은? | 선입선출(FIFO): 뒤에 넣고 앞에서 꺼낸다. 머리·꼬리 링크나 고정 용량 원형 버퍼를 쓰면 둘 다 O(1)이다. 배열 원소를 이동시키면 꺼내기가 O(n)이 된다. |  |  |
| 29 | 이진 트리의 전위·중위·후위 순회 순서는? | 전위: 노드 → 왼쪽 → 오른쪽. 중위: 왼쪽 → 노드 → 오른쪽. 후위: 왼쪽 → 오른쪽 → 노드. |  |  |
| 30 | 개방 주소법에서 선형 탐사와 이차 탐사는 어떻게 다른가? | 항목은 배열 안에 둔다. 크기가 m, 처음 인덱스가 h이면 각각 (h+i) mod m과 (h+c₁i+c₂i²) mod m을 탐사한다. 이차 탐사는 적절한 매개변수가 필요하다. |  |  |
| 31 | 용량을 두 배로 늘리는 동적 배열에서 끝에 추가하는 분할상환 비용은? | 추가당 O(1)이다. 크기 변경 한 번은 O(n)일 수 있지만, 빈 배열에서 시작한 n번의 추가는 총 O(n)이다. |  |  |
| 32 | 레드-블랙 BST를 균형 있게 유지하는 색 규칙은? | 노드는 빨강 또는 검정이고 루트와 NIL 잎은 검정이다. 빨간 노드는 빨간 자식을 갖지 않는다. 한 노드에서 그 아래 NIL 잎까지의 모든 경로는 검정 노드 수가 같다. 이 규칙으로 높이가 O(log n)으로 제한된다. |  |  |

---
Study this deck interactively with FSRS-6 spaced repetition, audio review, and multiple-choice mode at [Flashcards World](https://flashcards.world/flashcards/sets/077e79ed-afcd-4539-a952-44f3c500255e/).