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

분할 정복 알고리즘의 세 단계는 무엇입니까?

1. A읽기, 계산, 쓰기
2. B분할, 정복, 결합
3. C정렬, 탐색, 반환
4. D추측, 확인, 반복

3n² + 5n + 2의 Big O는 무엇입니까?

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

메모이제이션(memoisation)이란 무엇입니까?

1. A함수 호출 결과를 저장하여 반복 호출에 메모리에서 답하는 것
2. B코드의 각 줄 옆에 주석을 쓰는 것
3. C재귀를 동등한 루프로 자동 변환하여 호출 스택이 필요 없게 만드는 것
4. D함수가 반환된 뒤 메모리를 해제하는 것

표준 삼중 루프로 두 n × n 행렬을 곱하는 시간 복잡도는 무엇입니까?

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

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

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

상향식 표로 n번째 피보나치 수를 계산하는 시간 복잡도는 무엇입니까?

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

클래스 NP의 올바른 정의는 무엇입니까?

1. A어떤 알고리즘으로도 풀 수 없는 문제
2. B인증서가 주어지면 "예" 답을 다항 시간에 검증할 수 있는 결정 문제
3. C다항이 아닌 문제
4. D다항 시간에 풀 수 없는 문제

log(n!)에 대한 올바른 한계는 무엇입니까?

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