Recurrence relation.md

점화식(Recurrence relation)

점화식이란?

수학에서 점화식은 수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식

• 두 관계식 $a_n = ar^{n-1}$, $a_n = ra_{n-1}$이 있을 때, 첫 번째는 n의 값을 아는 순간 바로 n번째 항의 값을 알 수 있지만 두 번째는 n번째 항의 값을 구하려면 n-1번째, n-1번째 항의 값을 구하려면 n-2번째 항의 값을 알아야 한다.
• 두 번째와 같은 관계식에 대해 나타낸 것이 점화식이다.
• 알고리즘 뿐만 아니라 DP(Dynamic Programming)에서도 흔히 쓰이는 것이 점화식이다.

점화식의 개념

• 수열 ${a_n}$의 각 항 $a_n$이 함수 $f$를 이용해서 $a_{n+1} = f(a_n)$ 처럼 정해져 있을 때, 함수 $f$를 수열 ${a_n}$의 점화식이라고 하며, 수열 ${a_n}$은 점화식 $f$로 정의된다고 한다.
• 점화식을 푼다는 것은 귀납적으로 주어진 수열 ${a_n}$의 일반항 $a_n$을 n의 명시적인 식으로 나타내는 것을 말한다.

점화식의 예시와 시간 복잡도 계산

1. $C_N = C_{N-1} + N$

• 풀이

  $ C_N = C_{N-1} + N, N \geq2, C_1 = 1 \ C_N = C_{N-1} + N \ = C_{N-2} + (N-1) + N \ = C_{N-3} + (N-2) + (N-1) + N \ \cdots \ = C_1 + 2 + \cdots + (N-2) + (N-1) + N \ = 1 + 2 + \cdots + (N-2) + (N-1) + N \ = {N(N+1) \over 2} \ \rightarrow C_N = O(N^2) $

• 설명

  N이 1이 될 때까지 N을 1씩 줄이며 해당 항을 대입하면, 1부터 N까지 더하는 식이 완성이 된다.
  1부터 N까지의 합은 등차수열의 합 공식인 $ \displaystyle\sum_{k=1}^n{k} = {N(N+1) \over 2} $을 통해 구할 수 있다.
  따라서, 시간 복잡도는 $O(N^2)$이 된다.

2. $C_N = C_{N/2} + 1$

• 풀이

  $ C_N = C_{N/2} + 1, N \geq 2, C_1 = 0 \ N = 2^n으로 가정, \ C_{2^n} = C_{2^{n-1}} + 1 \ = C_{2^{n-2}} + 1 + 1 \ = C_{2^{n-3}} + 3 \ \cdots \ = C_{2^n} + n \ = n \ \rightarrow C_N = O(\log{N}) $

• 설명

  N이 작아질수록 이전 값에서 반씩 줄어든다. $N/2$는 $N \times 2^{-1}$과 같다.
  $N$을 $2^n$으로 치환을 하여 점화식을 계산하기 편하게 만들어 준다.
  $N$이 1이 될 때까지. 즉, $2^n = 1$이 되는 $n = 0$ 까지 식을 계산하면 n번만큼 1을 더하기 때문에 $C_{2^0} + n$이 된다.
  $C_1 = 0$ 이므로 $C_{2^n} = n$ 이 성립하며, 이를 다시 로그 변환 공식으로 원래대로 치환한다.
  $ 2^n = N \ \rightarrow \log{2^n} = \log{N} \ \rightarrow n\log{2} = \log{N} \ \rightarrow n = \log{N} $
  따라서, 시간 복잡도는 $O(\log{N})$이 된다.

3. $C_{N} = C_{N/2} + N$(2021 중간고사 1-1)

• 풀이

  $ C_N = C_{N/2} + N, N \geq 2, C_1 = 0 \ N = 2^n으로 가정, \ C_{2^n} = C_{2^{n-1}} + 2^n \ = C_{2^{n-2}} + 2^{n-1} + 2^n \ = C_{2^{n-3}} + 2^{n-2} + 2^{n-1} + 2^n \ \cdots \ = C_{2^0} + \cdots + 2^{n-2} + 2^{n-1} + 2^n \ \approx 2N \ \rightarrow C_N = O(N) $

• 설명

  치환과 n을 줄여나가는 방식은 2번 예시와 동일하다. 바뀐 점은 1씩 더하는 것이 아닌 N씩 더하는 것이다.
  이는 무한등비급수의 합 공식을 통해 계산한다.
  $ S = \frac{a}{1-r} \ 초항 a = N, 공비 r = \frac{1}{2}인 무한등비급수 \ C_N = N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + \cdots \ S = \frac{N}{1 - \frac{1}{2}} = \frac{N}{\frac{1}{2}} = 2N $
  점화식에서 $2^n$에서 계속해서 2씩 나누기 때문에 2N이라는 결과가 나온다. 따라서, 시간 복잡도는 $O(N)$이 된다.

4. $C_N = 2C_{N/2} + N$(2021 중간고사 1-2)

• 풀이

  $ C_N = 2C_{N/2} + N, N \geq 2, C_1 = 0 \ N = 2^n으로 가정, \ C_2^n = 2C_{2^{n-1}} + 2^n \ \frac{C_{2^n}}{2^n} = \frac{C_{2^{n-1}}}{2^{n-1}} + 1 \ = \frac{C_{2^{n-2}}}{2^{n-2}} + 1 + 1 \ \cdots \ = n \ C_{2^n} = 2^n \cdot n \ \rightarrow C_N = O(N\log{N}) $

• 설명

  이 문제도 치환에 대한 것은 2번 문제와 동일하다. 다만, $C_{N/2}$앞에 2가 곱해져 있는 것에 주의해야 한다.
  이전 항들과 동일한 계산을 위해 $2^n$을 양쪽 항에 모두 나누어줘야 한다.
  $2C_{2^{n-1}}$은 $\frac{2C_{2^{n-1}}}{2^n}$이 되고, 이는 $\frac{C_{2^{n-1}}}{2^{n-1}}$과 같다.
  N이 1, n이 0이 될 때 까지 계산을 하면 1이 n번 더해지기 때문에 n만 남게 된다. 하지만 관계식 자체는 $\frac{C_{2^n}}{2^n} = n$이기 때문에, 다시 양쪽에 $2^n$를 곱하여 $2^n \cdot n$이 된다.이를 로그 변환 공식을 통해 N으로 바꾸어 주면 된다. $ \log{2^n} \times \log{n} \ \rightarrow \log{N} \times N \ \rightarrow N\log{N}
  $
  따라서, 시간 복잡도는 $O(N\log{N})$이 된다.

5. 피보나치수열(DP)

• 풀이

  • 파이썬 코드

  ## 100번째 까지의 피보나치 수열
  dp = [0] * 101
  dp[0], dp[1] = 0, 1
  
  for i in range(2, 101):
      dp[i] = dp[i - 1] + dp[i - 2]

  • 점화식

    $ dp[i] = \begin{cases} i ;(i < 2) \ dp[i - 1] + dp[i - 2] ;(i \geq 2) \end{cases} $

---

알고리즘 연습문제

1.8 $C_N = 2C_{N/2} + N^2$