Ierative Algorithm-반복 알고리즘

반복 알고리즘

반복 알고리즘은 동일한 루프를 반복해 문제를 해결하는 알고리즘 입니다. 

 

반복 알고리즘은 밑의 세가지 법칙을 따릅니다.

• 반드시 종료 조건이 있어야 한다.
• 반드시 자기 자신의 상태를 변경하면서 종료 조건에 가까워져야 한다.
• 반드시 자기 자신을 재귀적으로(다시 돌아와) 호출해야 한다.

반복 알고리즘의 예시로는 팩토리얼이 있다.

 

https://www.acmicpc.net/problem/10872

백준 10872번 팩토리얼 문제

위의 코드를 설명해보자면 일단 N 이라는 함수에 정수를 입력받는다. factorial이라는 함수를 선언 후, 앞에서 입력받은 정수 N을 인수로 받는다. 만약 N의 값이 1보다 크다면 N과 factorial(N-1)의 값을 곱한다. 여기서 factorial(N-1)이 다시 호출되고(자기 자신을 재귀적으로 호출), N-1의 값이 1보다 큰 경우에는 또 다시 factorial 함수를 재귀적으로 호출할 것이다. 예를 들어 N의 값이 3이라고 하자. factorial함수에는 3이 인수로 들어갈 것이고, 3은 1보다 크기 때문에 3 x factorial(2)를 return 할 것입니다. 다시 재귀적으로 호출된 factorial(2)함수는 다시 2 x factorial(1)으로 돌아올 것입니다. 그리고 factorial 함수의 인자가 1 이므로 1을 return 합니다. 따라서 3 x 2 x 1 = 6이  되고 print에 의해 6이 출력됩니다.

 

또 다른 재귀 알고리즘의 예시로는 피보나치 수열이 있다.

https://www.acmicpc.net/problem/10870

위의 코드를 설명해보자면 일단 N 이라는 함수에 정수를 입력받는다. fibonacci라는 함수를 선언 후, 앞에서 입력받은 정수 N을 인수로 받는다. 만약 N의 값이 2보다 작다면 즉 0, 1 이면 0과 1을 리턴한다. 그 다음은 fibonacci(N-1)과 fibonacci(N-2)가 호출되고 계속해서 더해진다. 예를 들어 N의 값이 3이라고 하자. 3은 2보다 커서 fibonacci(2)+fibonacci(1)로 리턴된다. 이 리턴된 fibonacci(2)는 2로, fibonacci(1)은 1로 리턴된다. 그리고 2와 1은 더해져 3이 되고 print에 의해 3이 출력된다.

 

장점	단점
코드가 간결해짐	파이썬 내부 스택에 데이터를 저장함으로 메모리를 더 소비를 함

 

따라서 메모리 사용량이 중요하다면 반복 알고리즘을, 그렇지 않다면 재귀 알고리즘을 사용하면 되겠습니다.