해설 보기
정답입력이 반드시 1개 이상 존재해야 한다는 설명 — 입력은 0개 이상이면 되므로 틀린 설명입니다.
핵심 개념
알고리즘의 5가지 조건 — 입력은 0개 이상, 출력은 1개 이상
알고리즘이 갖춰야 할 조건은 입력(input), 출력(output), 명확성(definiteness), 유한성(finiteness), 유효성(effectiveness)의 다섯 가지입니다. 이 중 시험에 가장 자주 나오는 함정이 입력과 출력의 개수 차이입니다. 크누스(Knuth)의 정의에 따르면 입력은 "0개 이상", 출력은 "1개 이상"이어야 합니다. 즉 외부에서 받는 값이 하나도 없어도(상수만으로 결과를 만들어 내는 알고리즘처럼) 알고리즘이 될 수 있지만, 아무 결과도 내놓지 않으면 알고리즘이라고 할 수 없습니다. 나머지 세 조건은 각 명령이 모호하지 않을 것(명확성), 유한한 단계 후 반드시 멈출 것(유한성), 각 연산이 실제로 수행 가능할 것(유효성)을 뜻합니다.
선지별 해설
①출력 조건에 해당합니다. 알고리즘은 수행 결과로 최소 1개 이상의 결과를 산출해야 하며, 결과가 전혀 없다면 알고리즘으로 인정되지 않으므로 옳은 설명입니다.
②입력 조건은 "0개 이상"입니다. 외부에서 주어지는 자료가 하나도 없이 내부 상수만으로 결과를 만드는 알고리즘도 성립하므로, 입력이 반드시 1개 이상이어야 한다는 서술은 옳지 않습니다.
③유한성(finiteness) 조건입니다. 알고리즘은 유한한 횟수의 단계를 거친 뒤 반드시 종료해야 하며, 무한 루프에 빠져 끝나지 않으면 알고리즘이 아니므로 옳은 설명입니다.
④명확성(definiteness) 조건입니다. 각 명령은 해석에 따라 결과가 달라지지 않도록 모호함 없이 정확하게 정의되어야 하므로 옳은 설명입니다.
해설 보기
정답시간 복잡도가 O(log₂n)이라는 설명 — 실제로는 지수 시간이므로 틀린 설명입니다.
핵심 개념
재귀 피보나치 — 중복 호출 횟수와 지수 시간 복잡도
재귀로 구현한 피보나치는 fib(n-1)과 fib(n-2)를 각각 따로 계산하기 때문에 같은 값을 몇 번이고 다시 구합니다. 호출 트리에서 어떤 값이 불리는 횟수는 다시 피보나치 수열을 이룹니다. 즉 fib(n)을 구할 때 fib(n-1)은 1번, fib(n-2)는 2번, fib(n-3)은 3번, fib(n-4)는 5번, fib(n-5)는 8번 호출됩니다. 총 호출 수가 황금비 φ의 n제곱에 비례해 커지므로 시간 복잡도는 O(2ⁿ) 수준의 지수 시간입니다. 이 중복 계산은 메모이제이션(하향식)이나 반복문을 이용한 상향식 계산으로 제거할 수 있고, 그러면 O(n)까지 줄어듭니다.