[고급-5] 동적표와 상/하향식 설계

학습 목표 : 

1. 동적표를 활용하여 알고리즘의 효율을 높일 수 있다.

2. 동적표를 이용하여 상/하향식으로 알고리즘을 설계할 수 있다.

1. 동적표

표에서 하나의 값을 이용해 나머지 칸을 차례차례 채워가는 것.

예제 ) 10칸의 표를 만들고 k번째 칸에는 1부터 k까지의 합을 기록한 표를 만들기.

풀이 ) 

<방법 1> 수학적인 식 이용. n(n+1)/2 = 1~n까지의 합

<방법 2> 동적으로 표 채우기. 

T[k] = 1+2+3+...+(k-1)+k

T[k-1] = 1+2+3+...+(k-1)

=>T[k]=T[k-1]+k

예제 ) 피보나치 수열.

반복적으로 계산된 것들을 모아둔 표를 생성해서 참고한다.

2. 상향식 설계와 하향식 설계

(1) 반복문에서 보면...

상향식 : for(i=0; i<n; ++i)

하향식 : for(i=n; i>=1; --i)

(2) 재귀함수

상향식 : void f(int k){ if( ~~~ ) return; f(k+1); }

하향식 : void f(int k){ if( ~~~ ) return; f(k-1); }

예제 ) 1~n까지의 합.

첫번째 값에서 출발. n번째 값 = n-1번째 값 + n

반복문을 이용하는 방법과 재귀함수를 이용하는 방법, 그리고 T[k]를 굳이 선언하지 않고 변수로 선언해도 별로 상관이 없다는 것을 이용한 방법.