오늘은 코테준비 스터디 팀원들과 함께 "분할정복" 알고리즘을 주제로 풀어본 2번째 문제인 "백준 10830 행렬제곱" 문제에 대해 고찰해보았다.

분할정복은 학교 알고리즘 수업시간에 배운 퀵정렬, 병합정렬 등등 아주 기본적인 알고리즘에 대한 틀만 알고있어서 헷갈린 내용이 조금 있어 그 내용을 정리해보려고 한다.

1트 - 시간초과

우선 내가 "행렬제곱" 문제에 대해 처음 접근한 방식이다.
접근 방식 자체는 퀵정렬과 병합정렬과 동일하게 문제를 1/2 한 subproblem을 계속만들어 이진트리를 쭉쭉 뻗어나가는 식으로 구성했다.

public class DayProb28 {

    private static int[][] matrix;
    private static int N;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());

        matrix = new int[N][N];

        for (int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++){
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] result = divideConquer(B);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                sb.append(result[i][j] % 1000).append(" ");
            }
            sb.append("\n");
        }

        System.out.print(sb.toString());

    }

    private static int[][] divideConquer(long n){
        if (n == 1) {
            return matrix;
        } else {
            return square(divideConquer(n/2), divideConquer(n-n/2));
        }

    }

    private static int[][] square(int[][] a, int[][] b){
        int[][] midResult = new int[N][N];
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                for (int k = 0; k < N; k++){
                    midResult[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return midResult;
    }

}

내가 푼 방식에는 몇가지 문제점이 있었다.

1. long으로 선언해야되는 걸 int로 선언해서 런타임에러(numberFormatException Error) 가 떴었다.
   -> int는 약 -21억 ~ 21억인데, 이 문제에서 입력값이 최대 1000억으로 주어졌으므로 long을 선언해야 한다. 입력 범위와 자료형에 대한 경각심을 다시 가지게 되었다.
2. 다음으로 "시간초과"가 떴다. 분명 분할정복은 잘 구현한 것 같고, 퀵정렬, 병합정렬과 분할정복 구조도 완전히 동일한데 왜 문제가 뜨는지 생각해보았다.
   -> 행렬곱 계산시에 매번 %1000을 해줘야되는 문제인가 했는데 이렇게 해도 해결되지 않았다.

분할정복에 대한 고찰

🤔 선형으로 풀면 O(n) 번 계산하는건데, 이렇게 분할해서 이진트리를 만들면 O(logn)번 계산하는거 아닌가?

우선 처음 들었던 이 생각은 얼마 안가서 완전히 잘못됐다는것을 금방 깨달았다. 사실 이진트리를 만들면 그 깊이만큼 계산하는 것이 아니라, 노드의 개수만큼 계산하는 것이기 때문에 분할을 했다고 해서 연산회수가 n -> logn (깊이) 만큼 줄어드는 것은 아니다. 오히려 노드의 개수가 2n-1개가 되어서 계산 회수자체는 늘어난다.

그렇다면 분할정복은 왜 메리트가 있는것일까? 라는 질문에 대한 정답이 내 오해를 풀어줄 것이라고 생각했다.

이 밑에 내가 고찰한 내용을 정리해보았다.

우선 내가 착각한 부분은 :

퀵정렬, 병합정렬이랑 똑같은 방식으로 큰 문제를 반으로 쪼개서 두개로 나누고 그렇게 계속해서 리프노드가 나올 때까지 이진트리 가지를 만들어나가는 방식인데 왜 퀵, 병합정렬은 시간복잡도가 개선이 되고 이 문제의 경우에는 개선 되지 않는가?

⇒ 그냥 “분할” 후 “정복” 한다고 해서 알고리즘의 효율, 시간복잡도가 개선되는 것이 아니다!

이진트리로 계속해서 분할하게 되면 결국 이진트리의 노드의 수는 2n -1 개임. 2n -1 번 계산하게 되는것임. 이 문제의 경우, 선형으로 계산했을 때 n 번 계산하면 될거를 분할정복하게 되면 오히려 2n-1번 계산해야 되는것임.

🤔 그렇다면 퀵정렬, 병합정렬은 트리의 노드의 개수가 2n -1임에도 불구하고 왜 성능이 개선되었고, 왜 이문제만 그렇게 하면 안되지?

이유는 크게 2가지가 있었다.

1. 이 문제의 경우, 분할정복으로 나누었을 때 subproblem에 중복이 존재한다.

   • 내가 푼 방식대로 풀면, 두개의 subproblem으로 나누어지게 되는데, 짝수일 경우 완전 똑같은 subproblem이 생기고, 홀수일 경우에도 연산 한번만 제외하고는 똑같은 subproblem이 생긴다.

2. 큰 문제를 subproblem으로 나누었다고 해서 subproblem을 푸는데 걸리는 시간이 줄어들지 않는다.

   • 분할정복에서, 분할을 하면 결국에 트리의 노드의 수는 2n - 1 개로, 기존 n 개 보다 더 많아지기 때문에, “분할” 했을 때 생기는 메리트가 있어야함.
   • 큉정렬과 병합정렬은 “정렬” 문제로, 정렬하려는 배열의 “길이”가 줄어든다면, 정렬에 걸리는 cost가 감소함. 따라서 분할 했을 시에 cost의 메리트가 생김. → 정렬 cost가 n에 관련된 식임.
   • 이 문제의 경우 “행렬계산 cost” 자체는 분할 했을 떄와 분할 하지 않았을 때와 동일함. 행렬의 B제곱을 계산하는데 걸리는 cost와 행렬의 B/2 제곱을 계산하는데 걸리는 cost는 동일함. 따라서 퀵정렬, 병합정렬처럼 단순히 B/2 로 나누는 방식의 분할정복은 효과가 없고 오히려 트리노드 개수만큼 계산의 회수만 늘림 → 행렬계싼 cost가 B와 관계 없이 고정임 O(n^3)

   [ 마스터 방정식 ]

   • 퀵정렬, 병합정렬의 점화식 : T(n) = 2T(n/2) + O(n)
     $T(n) = 2T(n/2) + O(n) ⇒ T(n) = O(n \log n)$
   • 내가 푼 행렬제곱의 점화식 : T(B) = 2T(B/2) + O(n^3) → n^3은 B 에 대해서는 상수이므로,
     $T(B) = 2T(B/2) + O(n^3) ⇒ T(B) = O(n^3*B)$

2트 - 맞았습니다!

결국 분할정복에 대한 함수를 아래와 같이 바꿨을 때 문제가 풀렸다.

    private static int[][] divideConquer(long n){
        if (n == 1) {
            return matrix;
        } else {
            int[][] half = divideConquer(n/2);
            int[][] squared = square(half, half);
            if (n%2==0) {
                return squared;
            } else {
                return square(squared, matrix);
            }
        }
    }

• 어차피 제곱 연산을 해야되는거라 곱해야되는 제곱수가 똑같거나 1만 차이남.
• 한번 더 다시 계산할 필요가 없음. 재사용하자고

⇒ 메모이제이션 하는 방법도 있긴 함. 모든 지수에 대해 다 제곱을 구하는게 아니고, 재귀 경로에 등장하는 지수에 대해서만 저장하면 되니깐 $logB$개의 원소만 메모이제이션 하면 되긴 함.