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

재귀 함수의 기저 사례(base case)란 무엇입니까?

1. A메모리를 가장 많이 쓰는 호출
2. B함수의 첫 줄
3. C또 다른 재귀 호출 없이 직접 답을 내는 경우
4. D입력이 가장 큰 경우로, 재귀 호출보다 먼저 처리된다

알고리즘의 실행 시간이 O(n)입니다. 이 증가를 무엇이라고 합니까?

1. A선형
2. B상수
3. C로그
4. D이차

정렬된 배열에서 이진 탐색(binary search)의 시간 복잡도는 무엇입니까?

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

탐욕 알고리즘(greedy algorithm)은 무엇을 합니까?

1. A각 단계에서 지역적으로 가장 좋은 선택을 합니다
2. B항상 최적해를 제공합니다
3. C가능한 모든 해를 시도합니다
4. D재귀만 사용합니다

분할 상환 분석(amortised analysis)은 무엇을 측정합니까?

1. A무작위 입력에 대한 기대 비용
2. B최악의 연산 순서에 걸친 연산당 평균 비용
3. C최선의 입력에서 알고리즘의 비용
4. D연산열 전체에서 가장 비싼 단일 연산 하나의 비용

프림 알고리즘은 최소 신장 트리를 어떻게 만듭니까?

1. A너비 우선 탐색을 실행하고 BFS 트리를 유지한다
2. B간선을 가중치순으로 모두 정렬하여 숲에서 사이클을 만들지 않는 간선을 하나씩 추가한다
3. C시작 정점에서 트리 하나를 키우며 트리를 떠나는 가장 싼 간선을 추가한다
4. D사이클이 없어질 때까지 가장 비싼 간선을 제거한다

누군가 NP-complete 문제 하나에 대한 다항 시간 알고리즘을 찾는다면 어떤 결과가 따릅니까?

1. A모든 지수 시간 알고리즘이 즉시 선형 시간에 실행된다
2. B정지 문제가 결정 가능해진다
3. CNP의 모든 문제를 다항 시간에 풀 수 있으므로 P = NP이다
4. D그 문제 하나만 P로 옮겨진다

단일 연결 리스트에서 이진 탐색이 O(log n) 시간을 주지 못하는 이유는 무엇입니까?

1. A연결 리스트 노드의 비교가 더 느리기 때문에
2. B직접 인덱스 접근이 없으므로 가운데 원소에 도달하는 데 O(n) 단계가 걸리기 때문에
3. C이진 탐색에는 최소 두 배의 메모리가 필요하기 때문에
4. D연결 리스트는 정렬할 수 없기 때문에