H-Log
[알고리즘] 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개의 부분 문제로 분해된 경우
반응형
'dev-log > cs' 카테고리의 다른 글
[알고리즘] Greedy 알고리즘 (0) | 2023.10.21 |
---|---|
[알고리즘] 정렬 알고리즘 (0) | 2023.10.21 |
[알고리즘] 점근적 표기 Big-Oh (0) | 2023.10.21 |
[알고리즘] 시간 복잡도 (0) | 2023.10.20 |
[알고리즘] 피보나찌 수 구하기 (0) | 2023.10.20 |
Comments