[신찬수 교수님] 5. 분할정복방법

분할정복법(Divide & Conquer)

큰 문제를 작은 문제로 분할해 재귀적으로 해결 -> 최종적으로 내가 원하는 출력을 얻을 수 있다.

 

예 : 가장 큰 수 구하기

# 하나를 고르고 나머지 중 제일 큰 수
A = [3, 0, -5, 7, 2, -4, 6, 9]

Max(A) = max(A[0], max(A[1:]))

T(n) = O(n)

# 반으로 나눠서 각각 가장 큰 수를 구하고 두 개 중 큰 수
A = [3, 0, -5, 7, 2, -4, 6, 9]

max(A) = max(max(A[0:4]), max(A[4:]))

T(n) = O(n)

 

예 : 입력받은 수의 제곱을 구하기

# 하나씩 차근 차근 곱해주기
power1(a, n):
  if n == 1 : return a
  return a * power1(a, n - 1)
  
T(n) = O(n)

# 반으로 나누고 각자 안에서 재귀 호출
power2(a, n):
  if n == 1 : return a
  if n == 0 : return 1
  if n % 2 == 0 : # 짝수
    return power2(a, n//2) * power(a, n//2) # (n/a**2) * (n/a**2)
  else : # 홀수
    return power2(a, n//2) * power(a, n//2) * a
    
T(n) = O(n)

# 재귀를 한번만 호출
power3(a, n):
  if n == 0 : return 1
  x = power3(a, n//2) # x = a ** n/2
  if n/2 % 2 == 0 : return x * x # 짝수
  else : return x * x * a
  
T(n) = O(logn)

 

피보나치(Fibonacci) 수

F0 = 0과 F1 = 1이 주어짐

Fn = Fn-1 + Fn-2

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

def fibo1(n) : return n
  if n == 0 or n == 1 : return n
  return fibo1(n - 1) + fibo1(n - 2)

fibo1의 시간복잡도

똑같은 값을 재사용하는게 아니라 자꾸 호출하기때문에 비효율적이다.

 

하지만 행렬 곱셈식으로 구하는 방법은 T(n) = O(logn)으로 가장 빠르게 구할 수 있는 방법이다.

 

 

큰 두 수의 곱셈 : Karatsuba's algorithm (분할정복 알고리즘)

적당한 크기의 두 수를 곱셈할 때는 O(1)시간 걸리지만 그것보다 큰 수를 곱할 때는 시간이 더 오래 걸린다.

그런 경우를 큰 두 수의 곱셈이라고 한다.

 

n자리 두 수의 곱셈은 O(n**2)의 시간에 계산 가능하다. 이 경우보다 빠르게 계산할 수 있는게 분할정복 알고리즘이다.

그래서 O(n**(log2**3))이 된다.

 

 

분할정복 알고리즘 수행시간 T(n)

이진탐색(binary search) : 대표적인 문제

A = [2, 3, 9, 10, 17, 28, 31, 45] : 오름차순으로 정렬되어있음

31을 찾으려고 할 때

1. 첫번째부터 확인해가며 찾아본다. 최악의 경우 n번의 비교가 필요하다.

 

2. 반씩 나눠가며 확인해본다.

  2-1.인덱스의 첫과 끝을 a=0, b=7라고 할 때 중간을 찾는다. (a+b)//2 = 3

  2-2. 3번 인덱스가 31보다 큰지 작은지 확인한다. 작으면 0번부터 3번 인덱스를 확인할 필요가 없다.

  2-3. 남은 부분의 중간을 구한다. a=4, b=7  (a+b)//2 = 5

  2-4. 5번 인덱스가 31보다 큰지 작은지 확인한다. 작으면 4번부터 5번 인덱스를 확인할 필요가 없다.

  2-5. 이렇게 계속 진행한다. a=6, b=7  (a+b)//2 = 6 그러면 6번 인덱스에서 31을 확인할 수 있다.

 

  만약 k 값이 40이어서 존재하지 않는다면 위의 단계까지 와서 31과 45를 비교한다.

  a=7, b=7 - a=7, b=6이 된다. a <= b가 성립하지 않는다면 찾고자하는 요소가 없다는 뜻이므로 -1을 반환한다.

def bs(A, a, b, k):
  if a > b : return -1
  m = (a + b)//2
  if A[m] == k :
    return m
  elif A[m] > k :
    return bs(A, a, m - 1, k)
  else:
    return bs(A, m + 1, b, k)

 

 

점화식에 따른 시간 복잡도

1. 이진 탐색

T(n) = O(logn)

 

2. quick select - best case

T(n) = O(n)

 

3. quick sort, merge sort - best case

T(n) = O(nlogn)

 

4. Karatsuba 알고리즘

T(n) = O(n**(log2**3))

 

---

교수님 오늘도 모르겠습니다... 죄송합니다....

k는 logn의... 어... 음..... 아.....