[알고리즘] Divaide-and-Conquer

DC : Divaide-and-Conquer

Divaide and Conquer : 분할정복식

• 분할 : 최대한 작게 문제를 분해
• 정복 : 나눈 문제를 각각 해결
• 통합 : 필요 시 해결한 문제를 합침

⇒ 재귀적 방법으로 해결 (분할-정복 반복)

⇒ top-down 접근 방법이라고도 한다 (반대는 bottom-up)

top-down (하향식) 접근

• 소프트웨어 개발 시 기능 / 구조 위주로 바라본다
• 모듈 단위의 관점
• 문제를 나누어 구체화
• 유지보수가 어렵다
• 절차지향적 프로그래밍에 사용
• 분할정복 설계

bottom-up (상향식) 접근

• 소프트웨어 개발 시 데이터를 위주로 바라본다
• 객체 단위의 관점
• 데이터들 간의 상호관계를 정의하며 해결
• 유지보수가 쉽다
• 객체지향적 프로그래밍에 사용
• 상호관계 정의 설계

 

Divaide and Conquer 코드

procedure D&C (p, q)
	int n, A(1:n);
	int m, p, q; /*1≤p≤q≤n */
	
	If SMALL(p, q) then return(G(p, q))           // 충분히 작으면 다음 함수로 넘겨준다
	else 
		{ m := DIVIDE(p, q)                         // 분해
			return COMBINE (D&C(p, m), D&C(m+1, q))   // 분해했던 값을 병합
		} 
	End if

 

시간 복잡도

• T(n) : n개의 데이터 사용 시 DC에 걸리는 시간
• g(n) :데이터 분해가 필요 없을 때의 걸리는 시간 (최선의 경우) ⇒ 즉각적으로 답을 낼 때 걸리는 시간
• f(n) : 분해와 병합에 걸리는 시간

⇒ T(n)

1 ) g(n) : 바로 답을 구할 수 있을 때

2 ) f(n) + 2T(n/2) : 재귀함수를 거칠 때

 

분할정복 예시 : 이분 탐색

index BYSRCH(index low, index high) {
	index mid;
	
	if (low > high) return 0;    // 찾지 못했을 때 0 반환
	else 
	{ mid := (low + high) / 2    // 중간 값 선택
	
	if (x == S[mid]) return mid; // x가 중간값일 때 => x를 찾았음 => 종료
	else if (x < S[mid])         // 중간 값 보다 x 가 큰지, 작은지에 따라 다음에 분해할 내용 선택
		return BYSRCH(low, mid-1); // 왼쪽 반을 선택
	else
		return BYSRCH(mid+1, high); // 오른쪽 반 선택
	}
}

예제 1.

• 오름차순 정렬 된 배열 S
• x = 82

	low	high	mid	x위치 찾기	다음 영역 선택
1단계	1	9	5	9 < 82	mid+1 ~ high
2단계	6	9	7	54 < 82	mid+1 ~ high
3단계	8	9	8	82 = 82	return 8

예제 2.

• 오름차순 정렬 된 배열 S
• x = 2

	low	high	mid	x위치 찾기	다음 영역 선택
1단계	1	9	5	2 < 82	low ~ mid-1
2단계	1	4	2	2 > -6	mid+1 ~ high
3단계	3	4	3	2 > 0	mid+1 ~ high
4단계	4	4	4	2 > 7	low ~ mid-1
5단계	4	3	-		return 0

• low > high가 되었다 ⇒ stop ⇒ return 0

 

시간 복잡도 구하기

T(n)

• if n = 1 (즉시 계산 시 ) : 1
• if n > 1 (분해 시) : T(n./2) +1

Let n = 2^k

T(n) = T(n/2) + 1

• T(n/2) = T(n/2^2) + 1
• T(n/2^2) = T(n/2^3) + 1

…

+T(n/2^k-1) = T(n/2^k) + 1

---

= T(n) = T(n/2^k) + 1+ 1+ 1+ 1+ 1+ … + 1 (+1이 k개)

= T(n/n) + k = 1+k = 1+logn ⇒ O(logn)

*T(n/n) = 1

시간복잡도 = O(logn)

 

Divaide and Conquer를 사용하면 안되는 경우

• 크기가 n인 입력이 분할 된 후의 부분의 크기가 n과 가까운 경우 (10개 → 1개/9개)
• 크기가 n인 입력이 거의 n개의 부분 문제로 분해된 경우