수학에서 점화식은
수열에서 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식
- 두 관계식
$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의 명시적인 식으로 나타내는 것을 말한다.
-
풀이
$ 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)$ 이 된다.
-
풀이
$ 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})$ 이 된다.
-
풀이
$ 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)$ 이 된다.
-
풀이
$ 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})$ 이 된다.
-
풀이
- 파이썬 코드
## 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} $