해설 보기
정답'명령어들은 현재 실행 가능한 연산이어야 한다'는 명확성이 아니라 유효성의 정의이므로 잘못 짝지어진 설명입니다.
핵심 개념
알고리즘이 갖추어야 할 다섯 가지 조건
알고리즘은 입력, 출력, 명확성, 유한성, 유효성의 다섯 조건을 만족해야 합니다. 입력은 외부에서 제공되는 자료가 0개 이상이면 되고, 출력은 적어도 1개 이상 만들어져야 합니다. 명확성(definiteness)은 각 명령이 모호하지 않고 분명하게 정의되어야 한다는 뜻이고, 유효성(effectiveness)은 각 명령이 실제로 실행 가능한 기본 연산이어야 한다는 뜻입니다. 유한성은 한정된 단계 뒤에 반드시 종료되어야 함을 의미합니다. 이 문제는 각 조건의 이름과 정의가 바르게 짝지어졌는지를 묻습니다.
선지별 해설
①입력은 외부에서 제공되는 자료가 0개 이상이면 되므로 옳은 설명입니다.
②출력은 적어도 1개 이상의 결과를 만들어야 하므로 옳은 설명입니다.
③'명령어들이 현재 실행 가능한 연산이어야 한다'는 것은 유효성(effectiveness)의 정의입니다. 명확성(definiteness)은 각 명령이 모호하지 않고 분명해야 한다는 조건이므로, 조건 이름과 정의가 어긋난 틀린 설명입니다.
④한정된 수의 단계 후 반드시 종료되어야 한다는 것은 유한성의 정의로 옳은 설명입니다.
해설 보기
정답점근 표기법은 알고리즘의 수행 시간을 대략적으로 나타내는 방법이라는 옳은 설명입니다.
핵심 개념
점근 표기법(Big-O, Ω, Θ)의 의미
점근 표기법은 입력 크기가 커질 때 알고리즘의 수행 시간이나 공간이 대략 어떻게 증가하는지를 나타내는 방법입니다. O(빅오)는 상한, 즉 최악의 경우 수행 시간을 나타내고, Ω(오메가)는 하한(최소한), Θ(세타)는 상·하한이 같은 정확한 증가율을 나타냅니다. 다항식의 점근 표기에서는 최고차항만 남기고 계수와 저차항을 무시합니다. 예를 들어 10n²+3n+2는 O(n²)입니다. 이 문제는 이러한 정의를 바르게 이해했는지를 묻습니다.