• 분할(Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.

• 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.

• 통합(Combine) : (필요하다면) 해결된 해답을 모은다.
  
  
  

단순 반복 vs 분할정복 재귀 실습코드

package 수업복습;

import java.util.Scanner;



public class DivideTest {
	
	private static int callCnt1, callCnt2;
	
	private static long exp1(long x,long n) {
		callCnt1++;
		if(n==1) return x;
		return x* exp1(x,n-1);
	}
	
	private static long exp2(long x, long n) {
		callCnt2++;
		if(n==1) return x;
		
		long y = exp2(x, n/2);
		
		return n%2==0? y*y: y*
				y*x;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int n = sc.nextInt();
		
		System.out.println(exp1(x,n));
		System.out.println(callCnt1);
		System.out.println(exp2(x, n));
		System.out.println(callCnt2);
	}
}

공간만들기 실습코드

package 수업중;

import java.util.Scanner;

public class 공간만들기 {
	static int white = 0;
	static int green = 0;
	static int[][] spaces;

	// 주어진 영역의 공간의 셀 체크하여 모두 초록색이나 하얀색으로 이루어져있는지 확인 후
	// 4개로 쪼개기.
	// 하얀색 0 , 초록색 1
	static void cut(int r, int c, int size) {

		int sum = 0;
		for (int i = r, rEnd = r + size; i < rEnd; i++) {
			for (int j = c, cEnd = c + size; j < cEnd; j++) {
				sum += spaces[i][j];
			}
		}

		if (sum == size * size) { // 모두 초록색
			green ++;
		}else if(sum == 0) { // 모두 하얀색
			white ++;
		}else { // 혼합된 상황
			//4분할 
			int half = size / 2;
			cut(r,c,half);
			cut(r,c+half,half);
			cut(r+half,c,half);
			cut(r+half,c+half,half);
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		spaces = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				spaces[i][j] = sc.nextInt();
			}
		}
		cut(0,0,n);

		System.out.println(white);
		System.out.println(green);
		sc.close();
	}
}