포털:고등학교/과학 계열 전문 교과/정보과학(2015 개정)/관계 기반 알고리즘

관계 기반 알고리즘

해를 구하는 행위를 하나의 함수로 표현한 뒤, 이 함수들의 관계를 이용하여 해를 구하는 방법

필요한 조건

• 문제의 정의 및 상태를 함수로 정의
• 이 함수들의 관계를 점화식 또는 유사한 형태로 표현

예시

1에서 n까지의 합을 구하는 프로그램

f(k)를 f(n-1)이라는 값으로 가정

1. f(1) = 1
2. f(5) = 1+2+3+4+5
3. f(6) = f(5) + 6

int f(int n)
{
if(n==1)
	return 1;
	
return f(n-1)+n;
}

f(k)를 n/2라는 값으로 가정

1. f(1) = 1
2. f(5) = 1+2+3+4+5
3. f(11) = 1+2+3+4+5+6+7+8+9+10+11

= f(5)+(5+1)+(5+2)+(5+3)+(5+4)+(5+5)+(5+6)

= f(5) + f(5) + 5*6 + 6

= 2f(5) + 6*6

int f(int n)
{
if(n==1)
	return 1;
	
return	2 * f(n / 2) + ((n + 1) / 2) * ((n + 1) / 2);
}