[자료구조] 2. 순환 - 팩토리얼

팩토리얼

중등 교육과정을 겪어본 사람이라면 모두가 아는 팩토리얼!!

오늘은 팩토리얼을 계산하는 함수를 순환을 통해 구현해보자.

 

순환 알고리즘

앞선 포스팅에서도 말했지만, 순환 알고리즘은 알고리즘 내에서 자기 자신을 호출하는 방식으로 문제를 해결한다.

 

예상할 수 있는 순환 알고리즘의 가장 큰 문제점은 알고리즘의 종료에 있다.

알고리즘에 순환의 종료시점을 구현하지 않는다면, 알고리즘은 무한히 반복될 수 있다.

따라서 순환 알고리즘을 구현할 때, 순환부와 종료부를 확실하게 구현하도록 하자!

 

착오 없이 순환 알고리즘을 구현하려면, 큰 문제를 작은 부분문제로 생각하는 것이 중요하다.

알고리즘을 통해 해결하려는 문제점을 동일한 알고리즘의 작은 문제로 나누어 생각해야 순환부를 작성할 때 착오가 생기지 않는다.

 

정리하면 다음과 같다. 

• 큰 문제를 작은 단위로 생각할 것.
• 알고리즘이 종료되는 부분을 구현할 것

 

구현

순환

팩토리얼에서는 다음과 같이 생각할 수 있다.

• n! = n * (n-1)! 로 생각할 수 있다.
• n=1이 되는 순간이 알고리즘이 종료될 때. 

이를 바탕으로 쉽게 코드를 작성할 수 있다.

반복

일반적으로 순환하지 않고 한번에 팩토리얼을 계산하는 방식으로 구현할 수도 있다.

 

성능

빅 오 표기법을 통해 위의 두 구현의 성능을 비교해보자.

 

순환 방식	반복 방식
O(n)	O(n)

 

그러나 공간 복잠도의 경우 순환방식은 함수 호출을 하게 되므로 반복방식보다 더 큰 복잡도를 가지므로 For문을 활용한 반복 방식이 더 효율적이다.