[알고리즘] 분할정복!(BOJ1992쿼드트리,BOJ1074Z)

다양한 순,조,부 구현방법을 배웠는데 난 오리지날 방법이 가장 좋다...비트마스킹도 좋지만 내가 게을러서인지 선뜻 쉽게 사용하기 어렵게 느껴진다. 이걸 더 연습해야하나 고민할 찰나에 분할정복 유형 진도를 나가게 되었다. 그래 그냥 순조부는 원래풀던대로 하자. 분할정복을 정복하자!

 

분할정복은 기본적으로 재귀를 사용한다. 

 

가장 간단한 예시는 거듭제곱 구하기이다. 

식만 보면 이해되려나. 지금은 되는데 나중에 다시 볼때 내가 잘 이해할지 모르겠다ㅋㅋ

이진트리를 그려서 보면 이해하기 쉽다.

2^9 = 2^4*2  두개 (여기서 9는 홀수이기에 4 4로 나누고 2를 한번 더 곱해줘야 하는게 포인트!)

2^4 = 2^2 두개

2^2 = 2^1 두개

import java.util.Scanner;

public class SquareNumberDivideTEst {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int n = sc.nextInt();
		
		System.out.println(exp(x,n)); //오버플로우 일어나는거 상관없이 일단 callCnt찍히는것만 보셈
		System.out.println(callCnt);
	}
	static int callCnt = 0;
	public static long exp(long x, long n) {
		
		callCnt++;
		if(n==1) return x;
		long y =exp(x, n/2);
		
		return (n%2==0)? y*y :y*y*x;//홀수면 자기자신 한번더 곱해야 함
	}
}

 

 

위 코드를 이해했으면 다음은 응용이다.

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

1074번: Z

package ws0215;

import java.util.Scanner;

public class BOJ1074_Z제트 {

	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int r = sc.nextInt();
		int c = sc.nextInt();
		int len = (int)Math.pow(2,N);
		
		recur(len, r, c);
		System.out.println(cnt);
	}
	static int cnt = 0;
	static void recur(int len, int r, int c) {
//		System.out.println("rec: "+cnt);
		if(len == 1) return;
		//1사분면
		if(r<len/2 && c<len/2) {
			recur(len/2, r, c);
		}
		
		//2사분면
		else if(r<len/2 && c>=len/2) {
			cnt += (len*len/4);
			recur(len/2, r, c-len/2);
		}
		
		//3사분면
		else if(r>=len/2 && c<len/2) {
			cnt += (len*len/2);
			recur(len/2, r-len/2, c);
		}
		
		//4사분면
		else if(r>=len/2 && c>=len/2) {
			cnt += (len*len*3/4);
			recur(len/2, r-len/2, c-len/2);
		}
	}
}

 

 

 

위와 마찬가지로 비슷한 유형의 분할정복이다.

이것도 비슷한 방법인데, 처음엔 못해서 결국 답을 보고 다시 풀었다. 혼자서 스스로 풀어봤으니 나중에 다시 풀 수 있을거라 믿는다.

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

1992번: 쿼드트리

package ws0216;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class BOJ1992_쿼드트리 {

	static int N;
	static char[][] mat;
	static StringBuilder sb;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		mat = new char[N][N];
		for (int i = 0; i < N; i++) {
			mat[i] = br.readLine().toCharArray();
		}
		
		sb = new StringBuilder();
		
		quadTree(N, 0, 0);
		System.out.println(sb);
	}
	
	private static void quadTree(int size, int r, int c) { //size와 체크할 시작 인덱스들
		if (size == 1) {
			sb.append(mat[r][c]);
			return;
		}
		
		boolean isDifferent = false;
		char first = mat[r][c];
		outer: for(int i=r; i<r+size; i++) {
			for(int j=c; j<c+size; j++) {
				if(first != mat[i][j]) {
					isDifferent = true; //하나라도 숫자가 다르다면
					break outer; //2중 for문 한번에 나가기
				}
			}
		}
		
		if(isDifferent) {
			sb.append("(");
			quadTree(size/2, r, c); //1사분면 체크
			quadTree(size/2, r, c + size/2); //2사분면
			quadTree(size/2, r + size/2, c); //3사분면
			quadTree(size/2, r + size/2, c + size/2); //4사분면
			sb.append(")");
		}
		else
			sb.append(first);
	}

}