분리 연결 해시 테이블의 기대 연산 비용과 최악의 비용은?

적재율이 제한되고 해시가 고르게 분포하며 키 연산이 상수 비용이면 검색·삭제는 기대 O(1)이다. 기하급수적 용량 증가를 쓰는 삽입은 기대 분할상환 O(1)이다. 충돌하는 n개 키의 사슬은 O(n)을 초래할 수 있다.

경로 압축과 랭크 기준 합치기를 쓰는 union/find의 분할상환 비용은?

연산당 O(α(n))이다. α는 역 아커만 함수, n은 원소 수다. 초기화는 O(n)이다. 이 경계는 연산열에 대한 것이며 모든 호출의 최악 비용이 상수라는 뜻은 아니다.

BST의 검색·삽입·삭제는 높이 h에 어떻게 의존하는가?

O(h) 시간이 든다. 균형 트리는 h = O(log n), 사슬은 h = O(n)이다. 기대 O(log n)을 얻으려면 무작위 삽입 순서 같은 가정이 필요하다.

음이 아닌 함수 f와 g에 대해 f(n) ∈ O(g(n))는 무엇을 뜻하는가?

모든 n ≥ n₀에서 f(n) ≤ c·g(n)이 성립하도록 하는 상수 c > 0과 n₀ ≥ 0이 존재한다.

경로 압축, 랭크 기준 합치기, 크기 기준 합치기는 어떻게 다른가?

경로 압축은 방문한 노드가 루트를 가리키도록 바꾼다. 랭크 기준은 낮은 랭크의 루트를 높은 루트 아래에, 크기 기준은 작은 집합을 큰 집합 아래에 붙인다. 랭크는 현재 높이와 같지 않을 수 있다.

트라이란 무엇이며 L자 키 검색은 언제 O(L)인가?

문자 경로에 키를 저장하고 완성된 키를 표시하는 접두사 트리다. 다음 문자로의 각 전이가 O(1)이면 검색은 O(L)이다.

O, Ω, Θ는 어떻게 다른가?

각각 점근적 상한, 하한, 상하한이 일치하는 차수의 경계를 나타낸다. 지정한 비용 함수를 설명하며, O 자체가 최악의 경우를 뜻하지는 않는다.

이진 힙의 삽입·루트 제거·루트 확인 비용은?

배열 크기 변경이 필요 없다면 각각 O(log n), O(log n), O(1)이다. 크기 변경은 O(n)일 수 있다.

원형 배열 큐는 꺼낸 뒤 원소 이동을 어떻게 피하는가?

앞·뒤 인덱스를 용량으로 나눈 나머지를 이용해 순환시킨다. 꺼낼 때 앞 인덱스를 옮겨 다른 원소를 이동하지 않고 빈 칸을 재사용한다.

레벨 순서는 이진 트리를 어떻게 방문하는가?

FIFO 큐로 깊이별 한 레벨씩 방문한다. 왼쪽 자식을 오른쪽 자식보다 먼저 넣으면 왼쪽에서 오른쪽 순서가 된다.

AVL 균형 조건은?

모든 노드에서 높이(왼쪽) − 높이(오른쪽) ∈ {−1, 0, 1}이다. BST 순서 불변식도 만족해야 한다.

스택은 어떻게 작동하며 언제 연산이 O(1)인가?

후입선출(LIFO): 마지막에 넣은 원소를 먼저 꺼낸다. 연결 리스트의 머리에서는 넣기·빼기·맨 위 확인이 O(1)이다. 배열 크기 변경이 있으면 한 번 넣기가 O(n)일 수 있다.

AVL 삽입 뒤 왼쪽-오른쪽 불균형은 어떻게 고치는가?

먼저 왼쪽 자식을 왼쪽으로 회전하고, 불균형 노드를 오른쪽으로 회전한다.

해시 테이블의 적재율은 무엇이며 왜 크기를 바꾸기도 하는가?

α = n/m으로, n은 저장 항목 수, m은 버킷 또는 슬롯 수다. 구현의 임계값을 넘으면 확장과 재해싱이 일어날 수 있다. 0.75는 보편적인 기준이 아니다.

이진 최소 힙을 정의하는 두 성질은?

완전 이진 트리이며, 각 부모 키가 자식 키보다 크지 않다. 따라서 루트에는 최솟값이 있다.

서로소 집합 자료구조에서 find와 union은 무엇을 하는가?

find(x)는 x가 속한 집합의 대표를 반환한다. union(x,y)는 집합이 다르면 합치며, 이미 같은 집합이면 분할은 그대로다.

고정 크기 배열의 인덱스 접근이 O(1)인 이유는?

같은 크기의 칸이 연속되어 주소(i) = 시작주소 + i·칸크기로 계산된다. 주소 계산에 상수 시간이 든다고 가정한다.

n → ∞일 때 다음 증가율을 느린 순으로 나열하라: n!, n, 1, n², log n, 2ⁿ, n log n.

점근적으로 1 < log n < n < n log n < n² < 2ⁿ < n!이다.

이중 연결 리스트에서 주어진 노드를 O(1)에 삭제할 수 있는 이유는?

이전·다음 링크로 이웃 노드를 바로 다시 연결할 수 있다. 필요하면 머리·꼬리를 갱신하며, 이전 노드를 검색할 필요가 없다.

키가 서로 다른 BST를 중위 순회하면 무엇을 얻는가?

모든 키를 엄격한 오름차순으로 얻는다. n개 노드를 방문하는 데 O(n)이 든다.

삽입만 허용하는 블룸 필터는 어떤 답을 내는가?

음성이면 삽입된 적이 없고, 양성이면 삽입되었을 가능성이 있다. 해시로 비트 배열의 비트를 설정하므로 거짓 양성은 가능하지만 상태가 온전하면 거짓 음성은 없다.

분리 연결법은 해시 충돌을 어떻게 해결하는가?

각 버킷은 해당 인덱스의 항목들을 모아 두며, 흔히 연결 리스트를 쓴다. 같은 버킷의 서로 다른 키도 별도 항목으로 남는다.

n개 원소로 아래에서 위로 힙을 만드는 비용은?

O(n)이다. 대부분의 노드는 잎에 가까워 조금만 내려보내면 된다. 노드 높이별 작업량을 합하면 선형이 된다.

테이블 검색용 해시 함수는 어떤 성질을 가져야 하는가?

결정적이어야 하고 예상되는 키를 고르게 분산해야 한다. 고정 크기 키의 해시는 O(1)일 수 있지만, 새로운 L자 문자열의 해시는 보통 O(L)이다.

키가 모두 다른 이진 탐색 트리(BST)의 순서 불변식은?

각 노드에서 왼쪽 서브트리의 모든 키는 더 작고 오른쪽의 모든 키는 더 크다. 이 규칙이 재귀적으로 적용된다.

길이가 n이고 인덱스가 0부터인 힙 배열에서 노드 i의 부모와 자식 위치는?

부모: i>0일 때 ⌊(i−1)/2⌋. 자식: 2i+1과 2i+2이며 인덱스가 n보다 작을 때만 존재한다. 인덱스 0에는 부모가 없다.

단일 연결 리스트와 동적 배열의 맨 앞 삽입 및 인덱스 접근을 비교하라.

리스트: 맨 앞 삽입 O(1), 인덱스 접근 O(n). 배열: 맨 앞 삽입 O(n), 인덱스 접근 O(1). 배열의 맨 앞 삽입은 원소를 이동시킨다.

큐의 접근 규칙과 일반적인 연산 비용은?

선입선출(FIFO): 뒤에 넣고 앞에서 꺼낸다. 머리·꼬리 링크나 고정 용량 원형 버퍼를 쓰면 둘 다 O(1)이다. 배열 원소를 이동시키면 꺼내기가 O(n)이 된다.

이진 트리의 전위·중위·후위 순회 순서는?

전위: 노드 → 왼쪽 → 오른쪽. 중위: 왼쪽 → 노드 → 오른쪽. 후위: 왼쪽 → 오른쪽 → 노드.

개방 주소법에서 선형 탐사와 이차 탐사는 어떻게 다른가?

항목은 배열 안에 둔다. 크기가 m, 처음 인덱스가 h이면 각각 (h+i) mod m과 (h+c₁i+c₂i²) mod m을 탐사한다. 이차 탐사는 적절한 매개변수가 필요하다.

용량을 두 배로 늘리는 동적 배열에서 끝에 추가하는 분할상환 비용은?

추가당 O(1)이다. 크기 변경 한 번은 O(n)일 수 있지만, 빈 배열에서 시작한 n번의 추가는 총 O(n)이다.

레드-블랙 BST를 균형 있게 유지하는 색 규칙은?

노드는 빨강 또는 검정이고 루트와 NIL 잎은 검정이다. 빨간 노드는 빨간 자식을 갖지 않는다. 한 노드에서 그 아래 NIL 잎까지의 모든 경로는 검정 노드 수가 같다. 이 규칙으로 높이가 O(log n)으로 제한된다.

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

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

Level: basic
Languages: ko → ko
Cards: 32
Markdown: 자료구조, 복잡도 분석(Big-O) 및 핵심 알고리즘 (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
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)으로 제한된다.