99코딩

재귀 알고리즘(Recursive Algorithm)

어떤 함수가 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘

자기 자신을 호출하고 자기 자신으로부터 호출이 되는 함수를 재귀 함(Recursive Function), 이러한 호출을  재귀 호출(Recursive Call)이라 한다.

재귀적으로 문제를 해결한다는 것은 문제를 점점 더 작은 단위로 쪼개어 해결하는 것을 의미한다.

재귀 알고리즘의 특징

• 재귀 호출이 수행될 때마다 문제는 점점 작아져야한다.
• 재귀 호출이 종료되는 종료 조건(Terminate Condition)이 존재해야한다.

피보나치 수열

하노이의 탑

재귀 함수를 비재귀 함수로

• 재귀 함수는 비재귀 함수에 비해 속도가 느리다.
• 시스템 다운의 위험이 있다.

위 두가지 문제로 최적화 단계에서 재귀 함수를 비재귀 함수로 변환하게 된다.

알고리즘의 정의

• 문제를 해결하기 위한 절차 또는 방법을 의미하는 단어
• 주어진 문제를 해결하기 위해 정의된 동작들의 유한 집합(Finate Set)

알고리즘과 자료구조

자료구조는 데이터를 저장하기 위한 구조이고, 알고리즘은 데이터를 활용해 문제를 해결하기 위한 방법이다.

프로그램은 자료구조 + 알고리즘이라 할 수 있다..

알고리즘의 분석

알고리즘의 분석에는 경험적 분석, 수학적 분석 두 가지가 있다.

경험적 분석(Empirical Analysis)

알고리즘을 직접 프로그래밍 언어로 구현하고 실행시키며 분석을 수행하는 것이다.

수학적 분석(Mathematical Analysis)

프로그래밍 언어로 구현하는 과정 없이 알고리즘 그 자체만으로 수학적 분석을 수행하는 것이다.

3가지 경우(Case)

• 최악(Worst Case) : 알고리즘을 수행하는 데 있어 가장 많은 시간과 공간을 필요로 하는 경우
• 최선(Best Case) : 알고리즘을 수행하는데 있어 가장 적은 시간과 공간을 필요로 하는 경우
• 평균(Average Case) : 평균적인 시간과 공간을 필요로 하는 경우 

알고리즘의 평가

알고리즘을 평가하는 항목에는 속도와 메모리가 있다.

최적의 알고리즘은 빠른 속도와 적은 메모리 사용을 모두 만족하는 알고리즘이다.

시간 복잡도(Time Complexity)

입력값과 연산의 수행 시간의 상관관계를 나타내는 척도이다.

입력값이 증가함에 따라 증가하는 시간의 비율이 적을수록 즉, 시간 복잡도 수치가 작을수록 효율적인 알고리즘이다.

공간 복잡도(Space Complexity) 

알고리즘이 얼마나 많은 공간을 필요로하는 지에 대한 척도이다.

빅 오 표기법(Big-Oh Notation)

알고리즘의 효율성을 표기하는 빅오, 빅오메가, 빅세타 중 가장 많이 사용하는 표기법이며 알고리즘의 효율성을 상한 즉, 최악의 경우를 기준으로 표기한다.

빅 오 표기법의 특징

• 상수항은 무시한다.
• 최고차항 이외에는 무시한다.

 ex) T(N) = 2N*N + N + 2  -> O(N*N)