해설 보기
정답명확성(ㄱ)과 유효성(ㄴ)만 옳은 설명이므로 ㄱ, ㄴ입니다.
핵심 개념
알고리즘의 5가지 조건 — 특히 '유한성'
알고리즘이 갖추어야 할 조건은 입력(input), 출력(output), 명확성(definiteness), 유한성(finiteness), 유효성(effectiveness) 다섯 가지입니다. 명확성은 각 명령이 모호하지 않고 뜻이 하나로 정해져야 한다는 뜻이고, 유효성은 모든 명령이 사람이나 컴퓨터가 실제로 수행할 수 있는 연산이어야 한다는 뜻입니다. 그리고 유한성은 알고리즘이 유한한 단계를 거친 뒤 반드시 종료되어야 한다는 조건입니다. 따라서 '무한히 반복 실행된다'는 서술은 알고리즘의 조건이 아니라 오히려 알고리즘이 되지 못하게 만드는 성질이므로, 이 문제는 유한성을 정확히 알고 있는지를 묻고 있습니다.
선지별 해설
①ㄱ(명확성)만 골랐지만 ㄴ의 '실행 가능한 연산이어야 한다'는 서술도 유효성 조건으로 옳으므로, ㄱ만 고른 것은 정답이 될 수 없습니다.
②ㄱ은 명확성, ㄴ은 유효성에 해당하는 정확한 서술이고 ㄷ만 유한성에 어긋나므로, 옳은 것만 모은 조합은 ㄱ, ㄴ입니다.
③ㄴ은 옳지만 ㄷ은 알고리즘이 유한 단계 안에 종료되어야 한다는 유한성에 정면으로 반하는 서술이므로 함께 고를 수 없습니다.
④ㄷ을 포함시켰다는 점에서 틀렸습니다. 무한히 실행되는 명령의 나열은 알고리즘의 조건을 만족하지 못합니다.
해설 보기
정답최선의 경우 수행 시간을 모든 입력에 대한 상한이라고 한 ③이 틀린 설명입니다.
핵심 개념
수행 시간 분석 — 최악/평균/최선의 경우와 상한
알고리즘의 수행 시간은 특정 컴퓨터의 속도나 언어에 좌우되지 않도록, 입력 크기 n에 대한 기본 연산 횟수의 함수로 정의합니다. 같은 크기의 입력이라도 값의 배치에 따라 연산 횟수가 달라지므로 최악의 경우(worst case), 평균의 경우(average case), 최선의 경우(best case)로 나누어 분석합니다. 이때 모든 입력에 대한 수행 시간의 상한(upper bound), 즉 '아무리 나빠도 이만큼'을 보장해 주는 것은 최악의 경우 분석이고, 최선의 경우는 오히려 하한(lower bound)에 해당합니다. 이 구분을 뒤집어 놓은 선지를 찾는 문제입니다.