분할 정복

https://loosie.tistory.com/237

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

 

분할 정복이란 ? 

분할 정복은 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다. 

대표적으로 퀵 정렬, 합병 정렬, 이진 탐색, 선택 문제, 고속 푸리에 변환 등이 있다. 

 

선택 정렬과 삽입 정렬은 O(n^2)의 시간복잡도를 갖는다.

분할정복 방식인 합병 정렬은 O(nlogn), 퀵 정렬은 최대 O(n^2), 최선이나 평균의 경우 O(nlogn)으로 비교적 빠르다.

 

분할정복 설계

✅ Divide 

원래 문제를 분할하여 더 작은 하위 문제로 분할이 가능할 때 까지 나눈다 

Divide를 잘 해야 Conquer를 쉽게 할 수 있다. 

✅ Conquer 

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

✅ Combine

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

분할 정복을 활용한 거듭제곱 

백준 1629 곱셈

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

분할 정복을 활용해 거듭제곱을 하는 문제가 백준에 많이 보여서 대표격인 문제 하나를 정리하고자 한다. 

 

import java.util.*;
import java.io.*;

public class Main{
	
	static long c;
	
	
	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());
		c = Long.parseLong(st.nextToken());
		System.out.println(divide(a,b)%c);
		
	}
	
	public static long divide(long a, long b) {
		if (b==1) return a%c;
		long temp = divide(a,b/2);
		if (b%2==0) {
			return temp%c*temp%c;
		}
		return temp%c*temp%c*a%c;
	}

	
}

문제는 a를 b제곱한 수를 c로 나눈 나머지를 구하는 문제이다. 

단순히 a를 b제곱해서 c로 나누면 수가 너무 커져 버린다. 따라서 분할정복을 활용해야 한다. 

알아야 하는 수학적 지식은 %가 곱셈과 덧셈에 대해 분배가 된다는 것이다. 

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

 

위와 같은 이유로 성립한다. +도 마찬가지 원리로 

(a+b)%c = (a%c+b%c)%c 이다. 알아두면 유용하다.

 

(a의 b제곱)%c를 구해야 한다. 

제곱을 풀어서 생각해 보면 

(a*a*a*a* ... *a)%c가 된다. 

%c를 괄호 안으로 넣으면 

((a%c)*(a%c)*(a%c)*.......)%c가 된다. 

 

divide 함수가 풀이의 핵심적인 부분이다. 

a가 밑이고, b가 지수이다.

b가 1이면 a%c를 리턴한다. 

 

그게 아니라면 재귀를 활용해서 divide(a,b/2) 즉 a의 b/2 거듭제곱을 구한다. 

이러한 원리로 구하는 것이다. 

% 연산의 분배를 활용해 계속 %연산을 하고 나서 곱하기 때문에 long의 범위를 넘지 않고 안전하게 값을 구할 수 있다. 

 

정리하자면 위 문제의 핵심은 이 두가지이다.

 

✅ % 연산의 분배 

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

(a+b)%c = {(a%c)+(b%c)}%c

✅ 거듭제곱을 분할정복을 활용해 구하자 

a^b = a^(b/2)*a^(b/2) = a^(b/4)*a^(b/4)*a^(b/4)*a^(b/4) = ... = a*a*a*a*a*a ... *a 

 

https://www.acmicpc.net/problem/11401

11401번: 이항 계수 3

위 문제의 응용 문제인 11401번 이항 계수 3 문제도 있다.

마찬가지로 거듭제곱을 분할정복으로 해결하고 %의 분배를 해줘야 하는 문제다.

여기서 추가로 알아야 하는 것이 역원을 구하는 방법이다. 

이항계수는 유리수가 곱해져 있는데 이러면 %를 분배할 수가 없다. 따라서 역원을 구해서 푼다. 이 때 파스칼의 소정리를 사용한다. 

위 이미지의 2번째줄 -> 3번째 줄 부분이 파스칼의 소정리로 역원을 구한 것이다. 

package codingtest;

import java.util.*;
import java.io.*;

public class Main{
	
	final static long P = 1000000007L;	
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		long N = Long.parseLong(st.nextToken());
		long K = Long.parseLong(st.nextToken());

		// 분자 
		long son = facto(N);
	
		// 분모
		long mom = facto(K)*facto(N-K)%P;
		
		//분모의 역원
		long momReverse = pow(mom,P-2);
		
		System.out.println(son*momReverse%P);
		
	}
	
	public static long facto(long n) {
		long result = 1L;
		while (n>=1) {
			result=result*n%P;
			n--;
		}
		return result;
	}
	
	public static long pow(long base, long expo) {
		if (expo==1) {
			return base%P;
		}
		long temp = pow(base,expo/2);
		if (expo%2==0) {
			return temp%P*temp%P;
		}
		return temp%P*temp%P*base%P;
	}
}

facto 함수에서 팩토리얼을 구할 때도 %의 분배에 의해 %P를 해주며 구해서 값이 커지지 않도록 한다.

pow메서드는 제곱을 구하는 메서드로 앞에서 다룬 문제와 같다. 

son이 이항계수의 분자, mom이 이항계수의 분모, momReverse가 역원을 나타낸다. 

 

피보나치의 행렬 표현 

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

위 문제는 피보나치를 구해서 특정 수로 나눈 값을 구하는 문제다.

다만 일반적으로 피보나치를 구하는 재귀나 메모이제이션을 다 쓸 수 없었다. (입력의 범위 때문에)

분할 정복을 활용해야하는 문제인데, 피보나치를 분할 정복으로 구하기 위해 행렬을 사용해야 한다. 

 

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

[백준] 11444번 : 피보나치 수 6 - JAVA [자바]

위 링크를 참고했다. 

 

 

피보나치 식은 Fn+2 = Fn+1+Fn이다.

여기에 분할 정복을 사용하기 위해 행렬 형태로 바꿔준다. 

 

행렬 형태로 바꾸면 이렇게 식을 얻을 수 있다. 

행렬 제곱을 분할정복을 이용해서 해주면 된다. 

내가 참고한 풀이는 여기서 추가적으로 식을 가공하는데 나는 그것까지는 필요 없다고 생각해서 저 식으로만 진행했다. 

 

import java.util.*;
import java.io.*;

public class Main{
	
	static long[][] A = {{1,1},{1,0}};
	final static long D = 1000000007;
	
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		long up = sc.nextLong();
		long[][] result = pow(A,up);
		System.out.println(result[1][0]);
		
		
	}
	
	public static long[][] pow(long[][] arr, long up){
		if (up==1) {
			return arr;
		}
		
		long[][] half = pow(arr,up/2); 
		
		long[][] temp = multiply(half,half);
		
		if (up%2==0) {
			return temp;
		}
		return multiply(temp,A);
		
	}
	
	public static long[][] multiply(long[][] arr1, long[][] arr2){
		
		long[][] ret = new long[2][2];
		
		for (int i=0; i<2; i++) {
			for (int j=0; j<2; j++){
				for (int k=0; k<2; k++) {
					ret[i][j] += arr1[i][k]*arr2[k][j];
					ret[i][j] %= D;
				}
			}
		}
		return ret;
	}
}

내 풀이는 위와 같다. 

결국 다른 분할정복 문제인 행렬 제곱과 분할정복이 사용되는 부분은 같다. 

행렬 제곱을 분할정복을 이용해 하는 것이다. 

이 문제의 핵심은 

• 행렬로 식을 나타내기
• 행렬 제곱을 분할정복으로 풀기 

이렇게 2가지라고 할 수 있겠다.