[Algorithm][Python] 동적 계획법(Dynamic Programming)과 분할정복(Divide and Conquer)

동적 계획법(Dynamic Programming) 과 분할 정복 (Divide and Conquer)

어떠한 문제를 접근할 때( 결국 알고리즘이지 뭐..) 적용할 수 있는 방법 중 하나이다. 문제를 빠르게 이해하고, 어떤 방식을 적용해야 좋은지 알아야 푸는데 걸리는 시간을 줄일 수 있다. 외운다기 보다는 이해하면 문제해결 능력이 더 올라갈 것이다. 이해하면서 , 적어보고 넘어가자.

1. 정의

• 동적 계획법 (DP 라고 많이 부름)
  • 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
  • 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
  • Memoization 기법을 사용:
    • Memoization 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
    • 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
      • 예: 피보나치 수열
• 분할 정복
  • 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
  • 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
    • 일반적으로 재귀함수로 구현
  • 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
    • 예 : 병합 정렬, 퀵 정렬 등

2. 공통점과 차이점

• 공통점
  • 문제를 잘게 쪼개서, 가장 작은 단위로 분할
• 차이점
  • 동적 계획법 - 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨 - Memoization 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용) 분할 정복 - 부분 문제는 서로 중복되지 않음 - Memoization 기법 사용 안함

3. 동적 계획법 알고리즘으로 이해해 보장.

프로그래밍 연습
피보나치 수열: n 을 입력받아서 다음과 같이 계산됨
n 을 입력받았을 때 피보나치 수열로 결과값을 출력해보자.

함수를 fibonacci 라고 하면,
fibonacci(0):0
fibonacci(1):1
fibonacci(2):1
fibonacci(3):2
fibonacci(4):3
fibonacci(5):5
fibonacci(6):8
fibonacci(7):13
fibonacci(8):21
fibonacci(9):34

밑에 사진은 Memoization 을 사용할 경우다. 이미 구해진 값을 저장해놓고 재사용 하게 될 경우, 전체 실행 속도를 빠르게 해줄 뿐만 아니라 공간 복잡도도 줄일 수 있다고 한다.

recursive call 활용

def fibo(num) :
	if num <= 1:
		return num
	if num > 1 :
		return fibo(num-1) + fibo(num-2)

동적 계획법 활용 (DP 약간 핵심인가..? 잘 몰랐던 부분이다)

def fibo_dp(num):
	cache = [ 0 for index in range(num+1)] # 0 으로 채워진 배열. index 는 num까지.
	cache[0] = 0
	cache[1] = 1

	for index in ragne(2, num + 1):
		cache[index] = cache[index - 1] + cache[index - 2]
	return cache[num]

실행 코드를 보며 이해해보기: 코드분석

• 실행 코드를 보면, 배열 index 수가 len(num) 보다 1 크다. 마지막 index 는 결과값을 위한 곳.
• 나는 항상 이런 식을 보면, range 를 어디서부터 어디까지 해야할 지가 가장 어렵다.

분할 정복 알고리즘의 예는 다른 블로깅에서 보자 . “병합 정렬” 과 “퀵 정렬” 을 통해 이해할것!