분할정복(백준 알고리즘 10830번)

♣ 분할정복(divide and conquer)

하나의 문제를 작은 문제로 분할하여 해결하는 방법을 의미한다. 퀵 정렬, 합병 정렬, 이진탐색, 선택 문제, 고속푸리에 변환 문제들이 대표적으로 분할정복 알고리즘으로 해결할 수 있는 문제들이다. 

 

 

♣ 분할정복 설계

1. Divide

문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 분할이 가능할때까지 나눈다. 

 

2. Conquer

각 하위 문제를 재귀적으로 해결한다. 하위 문제가 더 이상 나눌 수 없는 단위가 되면 탈출 조건을 설정하여 해결한다. 

 

3. Combine

Conquer한 문제들을 통합하여 원래의 문제의 답을 얻어 해결한다. 

 

 

♣ 분할 정복의 특징 및 장단점

1. 분할된 작은 문제는 원래 문제와 성격이 동일하다

2. 분할된 문제는 서로 독립적이다. 

3. Top-down 재귀방식으로 구현하기 때문에 코드가 직관적이다. 

4. 재귀함수 호출로 오버헤드가 발생할 수 있다. 

5. 스텍에 다량의 데이터가 보관되는 경우 오버플로우가 발생할 수 있다. 

 

 

♣ 백준 알고리즘 10830번 문제 이해

 

 

10830번은 행렬을 거듭제곱하는 문제이다. 크기가 n*n인 행렬이 주어지고, 행렬을 제곱해야 하는 수 b가 주어진다. 

주어진 행렬을 b번만큼 제곱한 후 출력한다. 

 

b는 10**12 번까지 주어질 수 있기 때문에 무턱대고 재귀함수로 b번만큼 거듭제곱을 하면 당연히 메모리 초과가 난다. 

차근차근 해결하기 위해 문제를 아래와 같이 분할했다. 

 

1. 두 개 행렬을 곱하는 함수를 만든다. 

2. b가 매우 커졌을 경우 메모리 초과가 발생하므로 b번만큼 거듭제곱을 하지 않아도 답을 구할 수 있는 함수를 만든다. 

3. 1과 2에서 만든 함수를 모두 합쳐서 실행하기

 

 

두 개 행렬을 곱하는 함수

 

 

 

first 변수에 주어진 행렬을 담으려고 한다. 주어진 행렬이 아래과 같다면

 

이를 리스트로 나타내었을 때 [[1, 2], [3, 4]] 가 된다. 따라서 first를 n개의 빈 리스트를 가진 리스트로 정의한다. 1, 2가 주어지면 이를 first의 0번째 리스트에, 3, 4가 주어지면 이를 first의 1번째 리스트에 넣는다. 

 

multi_matrix는 두 개 행렬을 곱하는 함수이다. 행렬곱의 결과를 담기 위해 A라는 리스트를 만든다. 현재 A는 아래와 같은 형태이다. 

 

[[0, 0],

 [0, 0]]

 

먼저 이중 for문을 만든다. 행렬을 곱할 때 첫 번째 행렬의 첫 리스트의 수들과 두 번째 행렬의 각 리스트의 첫 숫자들을 곱해서 더하게 된다.

 

 

따라서 첫 번째 for문에서는 첫 행렬의 리스트를 순서대로 가져오고, 두 번째 for문에서는 for문을 또 넣어서 두 번째 행렬의 각 리스트에서의 수들을 순서대로 가져왔다. 

i = 0 일 때 c는 첫 행렬의 첫 번째 리스트인 [1, 2] 이고, j = 0 일 때 numbers는 두 번째 행렬의 각 리스트에서 0번째 숫자들을 가져와서 넣기 때문에 [1, 3] 이다. 이 c와 numbers를 zip 메소드로 묶어서 pair로 만든 뒤(pari = [[1, 1], [2, 3]] 각 pair들의 요소를 곱해서 더한다. 그리고 이 숫자들을 A[i][j] 에다가 넣는데, i=0, j=0이므로 A[0][0]은 7이 된다. 

 

그리고 답을 출력할 때 각 원소를 1000으로 나눠서 출력하므로, 미리 1000으로 출력한 수를 A에 넣는다. 이렇게 for문을 모두 돌리면 두 행렬을 곱한 A를 return 한다. 

 

 

 

행렬을 거듭제곱하는 함수(b의 횟수를 최대한 줄여서)

 

 

matrix_power는 주어진 행렬을 거듭제곱하는 함수이다. 이 함수 안에서 위에서 정의한 multi_matrix를 사용할 것이다. 

matrix_power에는 행렬과 숫자가 주어진다. 숫자만큼 행렬을 거듭제곱하는 것이다. 

 

숫자가 1인 경우는 예외 사항이 된다. 주어진 행렬을 1000으로 나누는 과정만 실행한 뒤 행렬을 return하면 된다. 

 

그 이외의 경우에는 주어진 number의 절만의 숫자로 matrix_power를 실시한다. 왜냐하면 제곱을 number//2번만 한 뒤, 이 값을 두 개 곱하면 number만큼 제곱한 값과 같기 때문이다. 이렇게 되면 number가 1이 될 때까지 matrix_power가 재귀함수로 계속해서 실시된다. number가 1이 되는 순간 matrix가 return되고 그때부터 result가 정의된다. result는 number//2번 제곱한 행렬을 multi_matrix에 넣어서 곱한 값이다. 첫 번째 재귀함수로 돌아올 때까지 result의 값은 계속해서 갱신된다. 

 

마지막으로, number가 홀수인 경우라면 행렬을 한 번 더 곱해주어야 한다. 따라서 multi_matrix(result, matrix)를 실행한다.  

 

이 함수를 사용하면 b가 아무리 커도 재귀함수를 40번 이내로 취하는 것으로 답을 구할 수 있다. 

 

 

 

전체 코드

 

 

♣ 참고 자료

https://loosie.tistory.com/237

[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)