분할정복, 백트래킹

---

---

분할정복

큰 문제를 작은문제들로 나누어서 각각의 해를 구한뒤 합쳐서 큰 문제의 정답을 구하는 알고리즘 설계 기법

 

설계 전략

• 분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
• 정복 : 나눈 작은 문제를 각각 해결한다.
• 통합 : (필요하다면) 해결된 해답을 모은다.

거듭제곱 문제

n의 k제곱을 구하는 문제

 

일반적인 반복문을 사용하면 O(n)

분할정복 설계기법을 사용하면 O(log2n)

 

<반복문>

int n, k;

for(int i = 0; i < k; i++){
	n *= n;
}

 

<분할정복>

재귀호출을 이용하여 작은 문제로 분할한다

k가 짝수이면 n의 k/2를 두번 곱한것과 마찬가지이다

=> 2^8 = 2^4 X 2^4

k가 홀수이면 n의 k/2를 두번곱하고 n을 한번 더 곱한것과 같다

=> 2^9 = 2^4 X 2^4 X 2

int n, k;

static int function(n, k){
	if(k == 1) return;

	if(K 이 짝수이면)
    	int t = function(n, K/2);
        return t * t;
    else
    	int t = function(n, (K/2)-1);
        return t * t * n;
}

 

---

백트래킹

백트래킹은 완전탐색을 기반으로 두고 있으며 탐색을 하면서 유망하지 않다 판단되는 경우 가지치기를 진행하여 시간복잡도를 줄인다.

 

설계전략

• 퇴각검색
• 모든 조합(선택지들의 조합(set))을 시도해서 문제를 해를 찾는다
• 해를 얻을 때까지 모든 가능성을 시도한다.
• 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지(선택지) 중에 해결책이 있다.
• 여러 가지(선택지)들이 존재하는 상황에서 하나의 가지를 선택한다.
• 선택이 이루어지면 새로운 선택지들의 집합이 생성된다.
• 이런 선택을 반복하면서 최종 상태에 도달한다.
• 보통 재귀 함수로 구현된다.

 

N-Queen문제

Queen들이 서로 위협하지 않도록 N개의 Queen을 배치하는 문제

• 어떤 두 퀸도 서로를 위협하지 않아야 한다.
• 퀸을 배치한 n개의 위치는?

체스판에 한 행 씩 탐색하여 Queen이 있을수 있는 위치를 탐색한다.

탐색을 하다 있을 수 없는 곳이면 가지치기를 진행하여 더이상 진행하지 않고

전의 상태로 되돌아 간다.

 

전의 상태를 기억해야 하기 때문에 DFS 재귀함수로 구현한다.