해설 보기
정답평균적인 경우의 시간 복잡도를 O((n+1)/2)로 표기한 것은 잘못이며, 빅오 표기법으로는 O(n)입니다.
핵심 개념
순차 탐색(선형 탐색)의 시간 복잡도와 빅오 표기법
제시된 a_search 함수는 배열 list[0]부터 list[n-1]까지 앞에서부터 하나씩 key와 비교하다가 일치하면 그 인덱스를 반환하고, 끝까지 못 찾으면 -1을 반환하는 순차 탐색(선형 탐색)입니다. 비교 횟수는 최선의 경우 첫 원소에서 바로 찾는 1회, 최악의 경우 n회, 평균적으로는 (n+1)/2회입니다. 여기서 주의할 점은 '평균 비교 횟수'와 '빅오 표기'는 다르다는 것입니다. 빅오 표기법은 상수 계수와 낮은 차수 항을 모두 버리고 증가율만 남기므로, (n+1)/2는 O((n+1)/2)가 아니라 O(n)으로 적어야 합니다.
선지별 해설
①if(list[i]==key) return i; 에서 key와 같은 값을 찾으면 그 원소의 인덱스 i를 반환하므로 맞는 설명입니다. 실패하면 -1을 반환합니다.
②찾는 키가 list[0]에 있으면 비교 1회 만에 반환하므로, 최선의 경우 시간 복잡도는 상수 시간인 O(1)입니다.
③키가 마지막 원소에 있거나 아예 없으면 n번 모두 비교해야 하므로, 최악의 경우 시간 복잡도는 O(n)입니다.
④평균 비교 횟수가 (n+1)/2인 것은 맞지만, 빅오 표기법은 상수배와 낮은 차수 항을 무시하므로 O((n+1)/2)가 아니라 O(n)으로 표기해야 합니다. 따라서 이 선지가 옳지 않습니다.
해설 보기
정답func(10) = 2 + (2+3+...+10) = 2 + 54 = 56이므로 56이 출력됩니다.
핵심 개념
재귀 함수의 추적과 누적 합 계산
func 함수는 n이 1 이하이면 2를 반환하고, 그 외에는 func(n-1)에 n을 더해 반환하는 재귀 함수입니다. 즉 func(n) = 2 + (2 + 3 + 4 + ... + n) 형태가 되며, 기저 조건에서 0이 아니라 2를 반환한다는 점이 이 문제의 함정입니다. 등차수열 합 공식으로 2부터 10까지의 합은 (2+10)×9/2 = 54이고, 여기에 기저값 2를 더하면 func(10) = 56이 됩니다. 재귀 문제는 기저 조건에서 무엇을 반환하는지, 그리고 더해지는 항의 범위가 어디부터인지를 정확히 확인하는 것이 핵심입니다.