분할 정복(Divide and Conquer)

👉 주어진 문제를 n개의 부분 문제들로 나눈 후, 각 부분 문제들의 해를 구하여 원래 문제의 해답으로 결합하는 방법이다.

👉 부분 문제들은 원래의 문제와 같은 유형이며, 처리해야 할 데이터의 크기만 작다.

👉 보통 순환 호출을 사용하여 해결한다.

if(문제의 크기가 충분히 작으면) return 해답
else{
  문제를 더 작은 n개의 부분 문제들로 나눈다
  나눈 부분 문제들에 대해서 다시 순환호출
  return 부분 문제들의 해답 결합
}

 

1. 이진 탐색(이분탐색)

1.1 문제 : 정렬된 상태의 리스트에서 x의 값이 존재한다면, 그 위치를 결정하라

👉 분할 정복 기법 적용
n=1이면(원소가 1개 있을 때) {
  x=원소 return 해
  x!=원소 return -1
}
n>1이면 {
  기준 원소보다 앞의 원소들 집합, 뒤의 원소들 집합으로 나눈다.
  x가 기준 원소보다 작으면 앞 집합만 해결(→순환호출)
  x가 기준 원소보다 크면 뒤 집합만 해결(→순환호출)
  x가 기준 원소와 같으면 return
  이 때, combine하는 부분은 필요하지 않다.
}

1.2 순환관계식 : O(log n)

1.3 반복적 구조를 갖는 이진 탐색

while(범위 내에 1개 이상의 원소가 있을 때) {
  mid  = (오른쪽 원소+왼쪽 원소) / 2
  if(x가 mid보다 작으면) 오른쪽 원소 = mid-1
  else if(x가 mid보다 크면) 왼쪽 원소 = mid+1
  else return mid
}

👉 반복당 if를 한 번만 사용, 범위를 계속 좁혀 나감
while(범위에 1개의 원소가 남을 때 까지) {
  mid
  if(x가 mid보다 작으면) 오른쪽 원소 = mid
  else 왼쪽 원소 = mid
}
if(x = 왼쪽 원소) return 왼쪽 원소
else return -1

 

2. 합병 정렬(Merge sort)

2.1 시간 복잡도 : O(n log n)

2.2 MergeSort1

if(2개 이상의 원소가 있을 때) {
  mid 위치 계산
  low~mid 순환호출
  mid+1~high 순환호출
  (low, mid, high) Combine
}

2.3 Combine 함수

👉 low~mid, mid+1~hith 병합 시 합병 결과를 저장하기 위한 임시 배열이 필요하다
while(두 리스트에 유효한 원소가 있을 동안){
  a의 두 리스트 중 작은 리스트가 b로 복사
}
if(뒤의 리스트가 남아있으면) 뒤의 리스트 b로 넣는다
else 앞의 리스트 b로 넣는다

 

2.4 MergeSort2

👉 링크 값을 이용하여 시간, 공간 효율적 사용
👉 하나의 리스트의 링크의 시작은 가장 작은 값을 가진 index
👉 그 index가 가진 링크값을 따라 가면서 정렬한다
if(범위에 한개 이상의 원소 존재시) {
  mid
  q = low, mid로 순환호출(그 중 값이 가장 작은 원소의 index)
  r = mid+1, high로 순환호출(그 중 값이 가장 작은 원소의 index)
  return (q, r) Combine
}
else return (1개 있는 원소 index)

2.4 Combine2

while(두 개의 리스트가 다 원소가 있는 경우) {
  if(a[i] < a[j]) {
    link[k] = i; k = i; i = link[i];
  }
  else {
    link[k] = j; k = j; j = link[j];
  }
i와 j중 남아있는 쪽을 link[k]에 넣어준다

 

3. 퀵 정렬(Quick sort)

👉 분할된 두 부분의 배열이 나중에 합병될 필요가 없다.

👉 a[1]~a[k-1] / a[k] / a[k+1]~a[n]

👉 이 때, a[k]는 분할 원소(또는 중추키)라 하며, 정렬 후에도 위치 변동이 없다.

👉 i는 오른쪽으로 이동하며 기준키보다 큰 것 찾고, j는 왼쪽으로 이동하며 기준키보다 작은 것 찾는다.

3.1 QuickSort1

if(원소가 2개 이상 있으면) {
  Partition //a의 제일 왼쪽 원소가 k 위치에 들어가고 분할, 기준키=a[k], a의 앞뒤 리스트
  p~k-1 순환호출
  k+1~q 순환호출
}

3.2 Partition

데이터 들어있는 배열, 제일 왼쪽 원소, 제일 오른쪽 원소+1 를 가지고 수행
i가 기준키보다 작을 동안 i++
j가 기준키보다 클 동안 j--
i가 j보다 작으면 둘의 값 서로 교환
반복문 계속 수행하다가
i가 j보다 크거나 같아지면 반복문 종료

3.3 시간 복잡도 : O(n^2)

3.4 중간값 규칙

👉 정렬하고자 하는 것 중 제일 앞 원소, 가운데 원소, 마지막 원소 중 중간 크기의 값을 기준키로 사용(맨 앞으로)

👉 퀵 정렬에서 최악의 경우를 피하기 위해 사용

 

4. 선택(Selection)

4.1 문제 : 리스트와 k가 주어질 때 k번째 작은 원소를 결정하여 k위치에 두고, k위치 앞에는 k보다 작거나 같은 원소들이 오고, k위치 뒤에는 k보다 크거나 같은 원소들이 오도록 배치하라.

4.2 퀵 정렬과의 공통점과 차이점

👉 퀵 정렬처럼 분할을 사용한다. (분할 정복 기법 사용)

👉 한번의 분할로 인해서 기준키 a[k]와, a[1]~a[k-1], a[k+1]~a[n]으로 구성된다.

👉 a[k]가 k번째 작은 원소라면 멈춘다. 더 이상 분할 하지 않는다.

👉 k보다 기준키보다 작으면 앞쪽, 크면 뒤쪽에서 분할 계속한다.

👉 퀵 정렬은 기준키의 앞, 뒤 리스트에 대해 "모두" 분할을 수행한다.

👉 선택 문제는 앞, 뒤 리스트 중 하나만 분할을 수행한다. 결합도 하지 않는다.

4.3 Select

분할할 범위 선언
Partition 수행, 기준키를 k위치에 두고 재배치
k가 기준키와 같아지면 끝, return
k가 기준키보다 작으면 왼쪽 범위
k가 기준키보다 크면 오른쪽 범위

4.4 시간복잡도 : O(n^2)

 

5. Strassen의 행렬 곱셈

5.1 시간복잡도 : O(n^3)