컴퓨터 알고리즘에 대한 설명으로 옳지 않은 것을 ＜보기＞에서 모두 고른… | [계리직 컴퓨터일반] 18년 1회차 기출문제 상세 페이지
1[계리직 컴퓨터일반] 18년 1회차
컴퓨터 알고리즘에 대한 설명으로 옳지 않은 것을 ＜보기＞에서 모두 고른 것은?
＜보기＞
ㄱ. 힙 정렬(Heap Sort) 알고리즘의 시간 복잡도는 이다.
ㄴ. 0/1 배낭(0/1 Knapsack) 문제에 대하여 다항시간(Polynomialtime) 내에 해결 가능한 알고리즘이 개발되었다.
ㄷ. 모든 NP(Non-deterministic Polynomial time) 문제는 컴퓨터를 이용하여 다항시간에 해결할 수 없다.
1
ㄱ
2
ㄱ, ㄴ
3
ㄴ, ㄷ
4
ㄱ, ㄴ, ㄷ
해설
ㄱ, ㄴ, ㄷ 모두 옳지 않은 설명이다.
세 진술은 각각 힙 정렬의 복잡도, 0/1 배낭 문제의 난이도, NP와 P의 포함 관계를 잘못 서술하고 있다.
- ㄱ(힙 정렬): 최선·평균·최악 모두 이며 가 아니다.
- ㄴ(0/1 배낭): NP-완전 문제로, 다항시간에 푸는 알고리즘은 아직 알려져 있지 않다(동적 계획법 풀이는 용량에 따른 의사 다항시간이다).
- ㄷ(NP 문제): P는 NP에 포함되므로 정렬·탐색처럼 다항시간에 해결되는 NP 문제가 존재한다.
오류나 개정된 내용이 보이면 알려주세요