[알고리즘] 분할정복 알고리즘

분할정복 알고리즘은 문제를 작게 분할한 후 각각을 정복하는 알고리즘이다.

큰 문제를 작은 문제로 분할하여 각각을 해결하고, 그 결과를 이용해 전체 문제를 해결한다.

 

분할된 작은 문제를 재귀적으로 해결하고, 이를 결합하여 원래 문제를 해결한다.

이진 탐색, 병합 정렬, 퀵 정렬 등이 모두 분할 정복 알고리즘이다.

 

 

정렬 알고리즘	최대 실행 시간	최소 실행 시간	평균 실행 시간
선택 정렬	O(n^2)	O(n^2)	O(n^2)
삽입 정렬	O(n^2)	O(n)	O(n^2)
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(n^2)	O(nlogn)	O(nlogn)

 

 

<분할 정복 설계>

 

1. 나누기 (분할)

- 문제를 더 작은 하위 문제로 더 이상 쪼개질 수 없을 때까지 나눈다

 

2. 재귀적으로 해결 (정복)

- 하위 문제를 재귀적으로 해결한다.

 

3. 결합

- 문제를 통합하여 원래 문제의 답을 해결한다.

 

 

분할 정복 알고리즘의 장점

1. 전체 문제를 해결하는데 걸리는 시간을 줄일 수 있다.

2. 하위 문제를 병렬로 처리하기 쉬우므로 성능을 크게 향상시킬 수 있다.

3. 문제의 복잡도와 데이터 크기에 상관없이 적용할 수 있다.

 

 

 

분할 정복 알고리즘의 단점

1. 재귀적으로 호출되므로 많은 추가적인 메모리를 필요로 할 수 있다

2. 최악의 경우 시간복잡도가 크다.

3. 구현이 복잡할 수 있다

 

 

 

 

<퀵 정렬>

각 부분 수열의 맨 처음에 있는 수를 기준(pivot)으로 삼고, 이들보다 작은 수를 왼쪽으로, 큰 것을 오른쪽으로 가게끔 문제를 분할한다.

각 서브 배열을 재귀적으로 퀵 정렬한다.

정렬된 서브 배열들을 합친다.

 

 

분할정복 카테고리에 있는 문제 !

 

문제에서 말한대로 그대로 곱해서 출력하면 메모리 초과 오류가 뜬다.

지수법칙을 활용해서 분할정복 알고리즘을 이용해야 한다.

 

지수가 짝수일 경우

 

 

지수가 홀수일 경우

 

또한 나머지 연산을 위한 모듈러 공식을 이용해야 한다.

 

( a*b ) % c = ( a%c * b%c) % c

 

 

 

 public static long number(long a, int exponent) {
        if (exponent == 1) {
            return a;
        }

        long temp = number(a, exponent / 2);

        if (exponent % 2 == 1) {
            return temp * temp * a;
        }

        return temp * temp;
    }

 

지수 연산만 구현한 모습

나머지 연산은 ( a*b ) % c = ( a%c * b%c) % c 공식을 활용한다.

 

연산과정에서 int형의 범위를 넘길 수 있으므로 long 형으로 맞춰준다.

 

 

package 백준.분할정복;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class baekjoon_1629 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long a = Long.parseLong(st.nextToken());
        long b = Long.parseLong(st.nextToken());
        long c = Long.parseLong(st.nextToken());
        System.out.println(number(a, b, c));
    }

    public static long number(long a, long b, long c) {
        if (b == 1) {
            return a % c;
        } else {
            long temp = number(a, b / 2, c);
            if (b % 2 == 1) {
                return (temp * temp % c) * a % c;
            }
            return temp * temp % c;
        }
    }

}

 

 

풀이 참고

https://st-lab.tistory.com/237

[백준] 1629번 : 곱셈 - JAVA [자바]