정보보안 정보처리 기술사

“Factorial n”을 구하는 재귀 알고리즘을 작성하시오.(90회 정보관리 기술사)

 1. 재귀알고리즘의 개념

가) 재귀알고리즘의 정의

- 수학적 귀납법을 역순으로 이용하여 자신의 함수를 반복적으로 호출하는 방법

 2. 재귀 알고리즘의 작성 절차 및 효율성

가) 재귀 알고리즘의 작성 절차

 나) 재귀 알고리즘의 효율성

- 공간적 비효율(저장공간)

- 시간적 비효율(저장, 복원에 걸리는 시간)

- 가능하다면 반복문으로 대치하는 것이 유리

3. 문제에서 제시한 Factorial n 에 대한 풀이

가) 문제에 대한 해석

n! = n • (n-1) • (n-2) • ... • 1 (단, 1! = 0! = 1)

int Factorial(int n)

{           if (n = = 1)

return 1;

else

return(n * Factorial(n-1));

}

나) 코드로 구현

4. 재귀 알고리즘의 이용

- 이진 탐색 : 문제 크기의 감소, N, N/2, N/4, … , 1

- 문자열 뒤집기

- K 번째 작은 수 찾기

- 피보나치 수열

“끝”

http://www.sorting-algorithms.com/
http://devbot.tistory.com/entry/
http://thrillfighter.tistory.com/210

104회 응용

1)2교시- 버블(bubble) 소트

99회

1)1교시=> 이진탐색트리 에서 데이터 삽입과정

2)4교시=> Quick sort의개념과 사례풀이

98회

1)4교시=>인공지은 응용정보시스템이나 게임 개발시

        길찾기에 이용되는 Dijkstra와 A*알고리즘 비교

96회

2)1교시=>최소 신장 트리(MST)알고리즘 설명

95회

1)2교시=>버블 정렬 알고리즘 설명 및 사례

90회

1)1교시=>재귀 알고리즘

2)1교시=>자료구조 heap을 설명하고 max-heap/min-heap

3)2교시=>삽입 정렬 알고리즘 설명, 효과적인 경우,평균 연산시간과 최악 연산시간

4)4교시=>A*알고리즘을 8-퍼즐 게임에 적용하에 설명하시오

89회

1)4교시=>알고리즘의 평가방법 인 time complexity와 space complexity대해서 설명하시오

87회

1)1교시=>휴리스틱 알고리즘인 A*에 대해 설명하시오

2)1교시=>알고리즘 설계 기법중 [동적 계획법]에 대해서 설명하시오

3)4교시=>MST 개념과 Prim 및 Kruskal 알고리즘을 통한 문제풀이

86회

1)2교시=> Bzier 곡선 생성 알고리즘

2)4교시=> Banker's 알고리즘

84회

1)3교시=>Dijkstra 알고리즘을 통한 문제풀이

83회

1)4교시=>Greedy Method 의 특징, 해를 구하는 절차 및 Knapsack 알고리즘

80회

1)3교시=>유전자 알고리즘의 특정,절차,활용방법

<미출제 영역>

1.문자열 패턴 탐색의 BEST Practice => 보이어 무어

2.알고리즘 설계 기법의 Base Theory => Back Tracking