이 편의 문항은 실제 독학사 기출 문제를 그대로 옮긴 것이 아닙니다. 국가평생교육진흥원이 공개한 4단계 알고리즘 과목 출제기준(평가영역)과 공개·복원된 기출의 유형 분포를 바탕으로, 동일한 출제 의도를 갖도록 새로 재구성한 예상·유사 문항입니다. 이 과목의 계산 복잡도 파트는 정의·판별 수준까지만 출제되며 증명 테크닉의 세부 전개는 범위 밖이므로, 문항도 그 수준에 맞추어 구성했습니다. 실제 시험의 문항 수·배점·시간은 매 회차 공고를 통해 반드시 다시 확인하세요.
문제 14지선다
계산 복잡도 이론에서 다루는 결정 문제(decision problem)에 대한 설명으로 옳은 것은?
문제 24지선다
복잡도 클래스 P에 대한 설명으로 옳은 것은?
문제 34지선다
복잡도 클래스 NP에 대한 설명으로 옳은 것은?
문제 44지선다
P와 NP의 관계에 대한 설명으로 옳은 것은?
문제 54지선다
NP-완전(NP-complete)의 정의로 옳은 것은?
문제 64지선다
NP-완전(NP-complete)과 NP-난해(NP-hard)의 차이로 옳은 것은?
문제 74지선다
다항시간 환원(polynomial-time reduction)의 의미로 옳은 것은?
문제 84지선다
쿡-레빈 정리(Cook-Levin theorem)의 의미로 옳은 것은?
문제 94지선다
다음 중 대표적인 NP-완전 문제로 알려져 있지 않은 것은?
문제 104지선다
해밀턴 사이클 문제(그래프의 모든 정점을 정확히 한 번씩 방문하고 시작 정점으로 돌아오는 사이클이 존재하는지 판별)를 예로 들어, 'NP에 속한다'는 것이 '검증이 쉽다'는 뜻이지 '풀기가 쉽다'는 뜻이 아님을 보여 주는 설명으로 옳은 것은?
문제 114지선다
어떤 새로운 문제 X가 NP-완전임을 증명하는 표준적인 절차로 옳은 것은?
문제 124지선다
P = NP 문제(P와 NP가 사실은 같은 집합인지를 묻는 미해결 문제)의 현재 상태에 대한 설명으로 옳은 것은?
문제 134지선다
어떤 문제가 NP-완전임이 밝혀졌을 때, 실무에서 그 문제를 다루기 위해 흔히 선택하는 전략으로 옳지 않은 것은?
문제 144지선다
다음 서술 중 계산 복잡도 개념에 대한 흔한 오개념을 바르게 지적한 것은?
문제 154지선다
정지 문제(halting problem)에 대한 설명과 NP와의 관계로 옳은 것은?
문제 164지선다
다음 중 옳지 않은 것을 고르시오.
문제 174지선다
다음 중 최단경로 문제(다익스트라로 풀리는, 음수 가중치 없는 단일 출발점 최단경로)와 해밀턴 경로 문제(그래프의 모든 정점을 정확히 한 번씩 방문하는 경로가 존재하는지 판별)를 복잡도 클래스 관점에서 비교한 설명으로 옳은 것은?
문제 184지선다
다음 중 계산 복잡도 이론에 대한 설명으로 옳지 않은 것은?
문제 194지선다
만약 어떤 연구자가 3-SAT 문제(각 절이 정확히 세 개의 리터럴로 이루어진 SAT의 특수 형태로, NP-완전으로 알려져 있음)를 다항시간에 정확히 푸는 알고리즘을 발견하고 그 정확성을 증명했다고 하자. 이로부터 논리적으로 이끌어낼 수 있는 결론으로 옳은 것은?
문제 204지선다
독학사 4단계 알고리즘 시험에서 계산 복잡도(P, NP, NP-완전) 파트가 주로 요구하는 학습 수준으로 옳은 것은?
참고 자료
Last updated on