본문 바로가기

divide and conquer

 (4)
60. Strassen's Algorithm 스트라센 알고리즘(Strassen's Algorithm)은 행렬 곱셈을 $\Theta(n^3)$보다 빠른 시간에 하는 알고리즘이며 카라츠바 알고리즘과 유사하게 분할 정복을 이용하여 시간복잡도를 줄인다. 크기가 $n \times n$인 두 행렬 $A$와 $B$가 존재하고, $A$와 $B$의 곱이 행렬 $C$일 때 스트라센 알고리즘의 작동 방식은 다음과 같다. 먼저 각 행렬을 $4$등분해서 다음과 같이 나눈다. $$A = \begin{bmatrix} A_{1, 1} & A_{1, 2} \\ A_{2, 1} & A_{2, 2} \end{bmatrix}, B = \begin{bmatrix} B_{1, 1} & B_{1, 2} \\ B_{2, 1} & B_{2, 2} \end{bmatrix}, C = \begin..
56. Karatsuba's Algorithm 두 정수의 곱을 구할 때, 곱한 결과가 일반적인 정수 자료형에 저장하기에는 너무 큰 경우 정수를 문자열 형태로 저장한 후 직접 곱셈을 구현해야 한다. $100\text{~}1000$자리 정도의 정수를 곱할 때는 일반적인 $\Theta(n^2)$ 곱셈을 구현해도 괜찮지만 자릿수가 $10000$ 단위가 되면 $\Theta(n^2)$ 곱셈은 속도가 많이 느려지게 된다. 이때 카라츠바 알고리즘(Karatsuba's Algorithm)을 이용하면 곱셈의 시간복잡도를 $\Theta(n^{\text{lg }3})$으로 줄일 수 있다. 카라츠바 알고리즘은 분할 정복을 이용하여 정수의 곱을 계산하는 과정에서 중복된 계산을 유도한다. 계산이 중복되면 한 번만 해도 되므로 그만큼 연산 횟수가 줄어들게 된다. 곱해야 하는 두..
43. Power by Divide and Conquer 정수론 문제를 풀기 위해서 알아 두어야 하는 두 가지 기본적인 지식이 존재하는데, 분할 정복을 이용한 거듭제곱과 유클리드 호제법이 그것이다. 분할 정복을 이용한 거듭제곱(Power by Divide and Conquer)의 기본적인 원리는 이 글에서 설명한 적이 있다. 거듭제곱 $x^y$를 구하는 두 가지 방법을 요약하면 다음과 같다.$y$를 $2$의 거듭제곱의 합으로 나타낸 다음 $x$를 제곱해 나가면서 곱을 구한다.$y$가 홀수인 경우 $x^{y-1}$과 $x$를 곱해서 답을 구하고, $y$가 짝수인 경우 $x^{y/2}$를 제곱해서 답을 구한다.두 가지 방법의 구현은 다음과 같다. 일반적인 경우 답이 커지는 것을 피하기 위해 어떤 수 $p$로 나눈 나머지를 대신 구하게 되는 경우가 많기 때문에 코드..
25. Divide and Conquer 분할 정복(Divide and Conquer)은 큰 문제를 여러 개의 작은 부분 문제로 분할한 다음 각각의 부분 문제를 해결하고, 그 결과를 바탕으로 큰 문제의 답을 구하는 문제 해결 방법이다. 동적 계획법과 설명이 비슷하지만 동적 계획법에서는 중복되는 부분 문제가 있었다. 분할 정복의 부분 문제들은 서로 중복되지 않는다. 분할 정복에도 기저 사례가 존재하며, 기저 사례는 더 작은 부분 문제로 분할하지 않고 바로 해결할 수 있다. 분할 정복 자체가 재귀함수를 이용하여 구현하는 경우가 많기 때문에 코드에 자연스럽게 추가되기도 한다. BOJ 1629. 곱셈 (Silver I) 지수가 큰 경우의 거듭제곱을 구하는 문제가 분할 정복을 사용하는 대표적인 예시이다. 지수가 크기 때문에 $B$번 반복되는 반복문을 쓰..

티스토리툴바