반복 알고리즘

반복 알고리즘이란?

반복적인 방법으로 문제를 해결하는 알고리즘이다.

반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용한다.

루프 변성이란 반복문을 수행하면서 변하는 성질을 의미하며, 루프 불변성이란 변하지 않는 성질을 의미한다. 

 

예를 들어, start에서 end까지 숫자의 합계를 구하는 문제는 다음과 같은 알고리즘을 갖는다.

 

sum:=0
반복(index:=start -> end)
	sum := sum + index
반환 sum

 

위 알고리즘에서 index는 반복문이 실행 될 때마다 start에서 end까지 값이 순차적으로 증가한다. 이처럼 반복문을 수행할 때마다 변하는 성질을 루프 변성이라고 한다.

 

반대로 sum은 반복문이 몇 번 수행되더라도 start에서 index까지의 합을 나타내는 변하지 않는 성질을 갖고 있다. 이를 루프 불변성이라고 한다.

 

위 알고리즘을 C++ 코드로 나타내면 다음과 같다.

 

#include <iostream>
using namespace std;

int sumAtoB(int start, int end);

int main()
{
	int result = sumAtoB(1, 10);
	cout << result << endl;
	return 0;
}

int sumAtoB(int start, int end)
{
	int sum = 0;
	for (int index = start; index <= end; index++)
	{
		sum += index;
	}

	return sum;
}