[알고리즘] 분할과 정복 + 문제풀이

1. 분할정복법(Divide Conquer)이란?

• 큰 문제를 나눌 수 없을 때까지 작은 문제로 분할해 문제의 답을 얻는 것
• Divide => Conquer => Combine
• 재귀적인 분할을 이용하며, 알고리즘 수행시간은 점화식으로 표현 가능
• ※ 재귀할 경우 바닥조건 정해주는 거 잊지 말기

 

2.  예시1) 거듭제곱 계산하기

 

2.1 선형 재귀 호출을 하는 경우 

a = int(input()) #밑
n = int(input()) #지수

def power(a,n):
  if n == 1:
    return a
  else:
    return a * power(a, n-1)

print(power(a,n)

 

2.2 선형 이중 재귀 호출을 하는 경우

a = int(input()) #밑
n = int(input()) #지수

def power(a,n):
  if n == 0:
    return 1
  if n == 1:
    return a
  if n % 2 == 0:
    return power(a, n//2) * power(a, n//2)
  else:
    return power(a, n//2) * power(a, n//2) * a

print(power(a,n))

이 경우, 홀수와 짝수가 다르기 때문에 조건부를 걸어줘야 한다.

ex) 2^7 => 2,2,2 // 2 // 2,2,2 (가운데 a가 하나 남음)

ex) 2^6 => 2,2,2 // 2,2,2

 

2.3 선형 재귀 호출을 하되, 시간복잡도를 감소시키는 경우 => O(log2N)

a = int(input()) #밑
n = int(input()) #지수

def power(a,n):
  if n == 0:
    return 1
  if n == 1:
    return a
 
  x = power(a, n//2)

  if n % 2 == 0:
    return x * x
  else:
    return x * x * a

print(power(a,n))

=> 재귀 호출되는 횟수를 줄이기 때문에 더 빠르게 수행할 수 있다.

 

 

3. 예시2) 피보나치 수

 

3.1 재귀함수를 이용하는 경우

n = int(input())

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

print(fibo(n))

=> 같은 연산을 다시 진행해야 하는 경우가 발생하는 비효율적인 코드이며, 기하급수적으로 수행시간이 증가됨

 

3.2 거듭제곱을 응용하는 경우

n = int(input())

def fibo(n):
	f1 = 0
	f2 = 1
	for i in range(2, n+1):
		f3 = f1 + f2
		f1 = f2
		f2 = f3
	return f2

print(fibo(n))

=> O(log n)

 

 

이 외에도 하노이의 탑, 이진 탐색 등으로도 응용 가능