알고리즘 기초

재귀 함수

실행 도중 자기 자신을 호출하는 함수.

최대 재귀 깊이(Maximum recursion depth)

재귀 함수가 자기 자신을 호출 하는 횟수가 늘어날수록 컴퓨터의 가용 메모리 공간은 점점 줄어든다. 컴퓨터의 메모리에는 한계가 있으므로 결국 자기 자신을 호출하는 횟수의 한계인 최대 재귀 깊이를 초과해 스택 오버플로우가 발생할 수 있다.

 

분할 정복 알고리즘(Divide and Conquer Algorithm)

큰 문제를 여러 개의 작은 문제로 나누어 해결하고 결과를 결합해 하나의 해결 방법을 얻는 알고리즘.

 

탐욕 알고리즘(Greedy Algorithm)

실행되는 순간마다 최상의(가장 적합한) 결정을 내리는 알고리즘.

단, 매 순간 최선의 결정을 하더라도 결과적으로 전체에 대한 최적의 결정인지는 장담할 수 없다.

최선의 근사치는 찾아낼 수 있다.

 

동적 프로그래밍(Dynamic Programming)

과거에 내린 결정이 앞으로의 결정에 영향을 주는 알고리즘.

탐욕 알고리즘은 특정 순간에 최적인 해결 방법을 찾고 동적 프로그래밍 알고리즘은 문제를 해결하는 다양한 방법을  찾아 저장한 후 나중에 재사용한다.

 

탐욕 알고리즘은 근사치를 찾고 동적 프로그래밍 알고리즘은 최적화를 한다.