✏️ 09/29 강의 필기

✔️ ex2) Hanoi Tower Puzzle

• 작은 것이 위에 있도록 쌓아야 한다.
• 순환호출 중단 조건: n==0

	HT(n,S,D,T) :S의 n disk를 D로 옮기기 (T는 임시)
	{
      if (n==0) return
      HT(n-1,S,T,D)
      #S => D
      HT(n-1,T,D,S)
    }

✔️ 알고리즘 분석

M(n) #total number moves for n disks
= 0 #(if n=0)
= 2M(n-1) +1 #(if n>=1)

M(n) = 2M(n-1) +1
	 = 2[2M(n-2)+1] +1
     = 2^2M(n-2) +2+1
     = 2^2[2M(n-3)+1] +2+1
     = 2^3M(n-3) +2^2+2+1
     
     => 2^kM(n-k)+2^k-1+2^k-2+ ... +2+1
     #(n=k가 될 때 순환함수 중단, M(n-k)=0)
     = 2^n-1 + 2^n-2 + ... + 2^1 + 2^0 #(등비수열의 합)
     = 1(1-2^n) / 1-2
     = 2^n-1
     = O(2^n)

✔️ 중복계산 ex1) 피보나치 수열
0,1,1,2,3,5,8,13,21,34,55,89 ...

f(n) = f(n-2) + f(n-1) //순환 (초기조건 필요)
f(n) = f(n-2) + f(n-1) (if n>=2)
	 = n (if n=0,1)
 
//중복계산으로 속도가 느려지는 예
f(n) = f(n-2) + f(n-1)
	 = f(n-4)+f(n-3) + f(n-3)+f(n-2)
     ...

✔️ 중복계산 ex2) nCk
n개에서 k개를 뽑는 조합의 수

= n! / (n-k)!k!