피보나치 수 재귀함수 구현 및 효율적 기법
컴퓨터시스템응용기술사 제119회 3교시 20번 문항으로, 과목은 SW공학/프로젝트관리입니다. ‘시간 복잡도’ 키워드는 컴퓨터시스템응용기술사 기출 4문항에 나왔습니다.
원문 문제
컴퓨터시스템응용기술사 제119회 20번. 피보나치 수 재귀함수 구현 및 효율적 기법
핵심 키워드
- 재귀함수
- 메모이제이션
- 동적 프로그래밍
- 시간 복잡도
- 최적화 기법
고득점 가이드 — 1. 개요
피보나치 수 F(n) = F(n-1) + F(n-2) 는 정의 자체가 재귀적이라 학습용으로 자주 쓰이지만, 단순 재귀 구현은 동일 부분 문제를 반복 계산해 입력이 커지면 응답 시간이 폭발적으로 증가한다. 메모이제이션과 동적 프로그래밍은 이 중복 계산을 제거해 다항 시간으로 끌어내리는 대표적 최적화 기법이며, 성능·메모리·구현 복잡도 사이의 트레이드오프를 이해하는 것이 실무 적용의 출발점이다.
출제 이력
- 재귀함수기출 1문항
- 메모이제이션기출 1문항
- 동적 프로그래밍기출 1문항
- 시간 복잡도기출 4문항
- 최적화 기법기출 1문항