정답이 있는 알고리즘과 복잡도 학습지

무차별 대입(brute-force) 알고리즘이란 무엇입니까?

1. A항상 재귀를 사용하는 알고리즘
2. B여러 프로세서에서 실행되는 알고리즘
3. C무작위로 답을 추측하는 알고리즘
4. D가능한 모든 후보 해를 시도하는 알고리즘

순서가 잘못된 인접 원소를 반복적으로 교환하는 정렬 알고리즘은 무엇입니까?

1. A퀵 정렬(Quicksort)
2. B병합 정렬(Merge sort)
3. C버블 정렬(Bubble sort)
4. D힙 정렬(Heap sort)

배열에서 인덱스로 원소에 접근하는 데 걸리는 시간은 무엇입니까?

1. AO(n²)
2. BO(n)
3. CO(log n)
4. DO(1)

간선 가중치가 음이 아닌 그래프에서 하나의 출발점으로부터 최단 경로를 찾는 알고리즘은 무엇입니까?

1. AKruskal 알고리즘
2. B깊이 우선 탐색(DFS)
3. C모든 경우에 Bellman–Ford가 필요함
4. DDijkstra 알고리즘

최악의 경우 비교 기반 정렬의 하한은 무엇입니까?

1. AΩ(log n)
2. BΩ(n²)
3. CΩ(n log n)
4. DΩ(n)

가득 차면 용량을 두 배로 늘리는 동적 배열에 원소를 추가하는 연산의 분할 상환(amortised) 시간 복잡도는 무엇입니까?

1. AO(n²)
2. BO(log n)
3. CO(1)
4. DO(n)

한 번 증가할 때 많은 비트가 뒤집힐 수 있다는 점을 고려할 때, 이진 카운터 증가의 분할 상환 비용은 얼마입니까?

1. A증가당 O(log n)
2. B증가당 O(n log n)
3. C증가당 O(n)
4. D증가당 O(1)

정렬되지 않은 배열에서 k번째로 작은 원소를 선택하는 것에 대한 진술 중 옳은 것은 무엇입니까?

1. A퀵셀렉트는 피벗의 한쪽에만 재귀하므로 최악의 경우에도 O(log n)에 실행된다
2. B퀵셀렉트는 기대 O(n)에 실행되고, 중앙값의 중앙값은 최악의 경우 O(n)을 보장한다
3. C선택은 정렬이 필요하므로 항상 Ω(n log n)이 필요하다
4. D선택은 O(n²)에만 가능하다