Written by JS970
on March 27, 2023

컴퓨터 알고리즘 2023-03-27 수업정리

Flow

N*N 행렬 A, B의 곱셈에 Divide & Conquer를 적용하면 아래와 같다.$$C = A\times B,\ \begin{bmatrix}C_{11}&C_{12}\C_{21}&C_{22}\ \end{bmatrix} = \begin{bmatrix}A_{11}&A_{12}\A_{21}&A_{22}\ \end{bmatrix} \times \begin{bmatrix}B_{11}&B_{12}\B_{21}&B_{22}\ \end{bmatrix},\ \ \ \begin{matrix}C_{11} = (A_{11} \times B_{11}) + (A_{12} \times B_{21})\ C_{12} = (A_{11} \times B_{12}) + (A_{12} \times B_{22})\ C_{21} = (A_{21} \times B_{11}) + (A_{22} \times B_{21})\ C_{22} = (A_{21} \times B_{12}) + (A_{22} \times B_{22})\ \end{matrix}$$
이 알고리즘에 대한 시간복잡도를 계산하면 아래와 같다.$$T(n) = 8T(n/2) + \Theta(n^2) => T(n) = \Theta(n^3)$$
- 이렇게 되는 이유$$T(n) = 8T(n/2) + \Theta(n^2) => T(n) = \Theta(n^{log_28}) = \Theta(n^3)$$
아래는 행렬 곱셈을 구현한 C++코드이다.

// implement Matrix Multiplication Algorithm

위의 행렬 곱을 구하는 알고리즘과 Divide 과정은 동일하다.
Conquer 과정에서 중복되는 연산을 따로 저장한 뒤 재사용했다.$$\begin{matrix}P_1 \leftarrow A_{11} \times (B_{12}-B_{22})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P_2 \leftarrow (A_{11}+A_{12}) \times B_{22}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P_3 \leftarrow (A_{21}+A_{22}) \times B_{11}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P_4 \leftarrow A_{22} \times (B_{21}-B_{11})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P_5 \leftarrow (A_{11}-A_{22}) \times (B_{11}+B_{22}) \ P_6 \leftarrow (A_{12}-A_{22}) \times (B_{21}+B_{22}) \ P_7 \leftarrow (A_{11}-A_{21}) \times (B_{11}+B_{12}) \ \end{matrix}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{matrix} C_{11} = P_5 + P_4-P_2+P_6 \ C_{12} = P_1 + P_2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ C_{21} = P_3 + P_4\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ C_{22} = P_1 + P_5 - P_3 - P_7 \end{matrix}$$
이렇게 행렬의 곱셈을 연산했을 경우 시간복잡도를 계산하면 아래와 같다.$$T(n) = 7T(n/2) + \Theta(n^2) => T(n) = \Theta(n^{log_27})$$
아래는 Strassen's Algorithm으로 행렬 곱셈을 연산하는 것을 구현한 C++코드이다.

// implement Matrix Multiplication with Strassen's Algorithm

Dynamic Programming은 Divide & Conquer과 마찬가지로 main problem <-> Sub Problem의 점화식을 찾아 풀이에 이용한다는 공통점이 있다.
Divide & Conquer에서는 recursion을 활용하여 Top-Down접근 방식으로 큰 문제를 작은 문제들로 쪼개어 풀 수 있었다.
하지만 Dynamic Programming은 Divide & Conquer방법과 달리, 이전 연산 단계의 결과가 다음 단계의 연산에 사용되는 Bottom-Up 방식의 문제 풀이이다.
이전 단계의 연산(쉬운 문제)값을 저장해 두었다가 다음 단계의 연산(어려운 문제)에 사용한다.
Dynamic Programming을 적용하기 위해서는 중간 결과를 저장하기 위한 배열 컨테이너와, 각 단계의 알고리즘을 표현하는 Recursive Equation이 필요하다.

Top