[알고리즘] [13] 분할정복 백트래킹

1. 분할 정복 기법

• 분할 (Devide), 정복 (Conquer), 통합 (Combine)의 설계 전략을 가진다.
• 병합 정렬, 퀵 정렬이 분할 정복 정렬 방식이다.
• Top-down approach
  >> 크기가 작은 부분 문제로 정의(분할)한 후 부분문제의 해를 구한다(정복). 
  >> 필요하다면 부분 문제의 해를 결합하여 전체 문제의 해를 구한다.

거듭 제곱

C^n에서 n이 짝수인 경우와 홀수인 경우에 대해 각각 분할하여 계산한다.

// a의 n 제곱을 1000000으로 나눈 나머지 계산 함수
// 반복문을 이용한 방법
static long pow(long a, int n) {
		long result = 1;
		
		while (n > 0) {
			if (n % 2 == 1) {
				result *= a;
				result %= 1000000;
			}
			a *= a;
			a %= 1000000;
			
			n /= 2;
		}
		return result;
	}

 

2. 백트래킹 (Backtracking)

• 가능한 모든 조합을 시도하여 해를 찾는다.
• 모든 가능성은 하나의 트리처럼 구성되며, 가지 중 해답이 존재한다.
• 루트에서부터 답을 찾을 때까지 반복한다.
• 꽝 노드에 도달하면 최근의 선택으로 돌아가 반복한다.
• 일반적으로 재귀 함수로 구현한다.

백트래킹 기법

• 모든 후보를 검사하지 않는다.
• 어떤 노드의 유망성을 검사한 후 유망 (promising)하지 않다고 판단되면 노드의 부모로 되돌아가 다음 자식 노드로 이동한다.
• 유망하다 : 어떤 노드를 포함한 경로가 해답이 될 수 있는 경우
• 가지치기 (pruning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않는다.

N-Queen

9663번: N-Queen