[책] 누구나 자료구조와 알고리즘 - 12장 동적 프로그래밍

 

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

원래 8장 해시테이블 부터 읽어야됐는데 포스트잇이 잘못 붙어있어서 실수로 건너뛰고 읽었습니다..ㅎㅎ..

하지만 그래도 읽으면서 크게 이질감 드는 부분이 없어서 확실히 읽기 좋은 책이다 싶었습니다!

 

정리

1번 상황 - 배열에서 최대 값 구하기

재귀 호출 시, 불필요한 재귀 호출이 일어나는 경우가 있습니다.

def max(array)
	// 배열의 크기가 1이라면 첫번째 요소 반환
	return array[0] if array.length == 1
    
    if array[0] > max(array[1, array.length - 1])
    	return array[0]
    else
    	return max(array[1, array-length - 1])
    end
end

이 경우에서 문제점은 if 재귀에서 이미 구했던 값을 else 재귀에서 동일한 함수를 중복 호출하게 됩니다.

array가 [1, 2, 3, 4]일 경우, 재귀는 총 15번 호출 되게 됩니다.

 

이를 개선하기 위해서는 재귀 호출되는 함수 부분을 변수로 저장해서 사용할 수 있습니다.

def max(array)
	// 배열의 크기가 1이라면 첫번째 요소 반환
	return array[0] if array.length == 1
    
    max_of_remainder = max(array[1, array.length - 1])
    
    if array[0] > max_of_remainder 
    	return array[0]
    else
    	return max_of_remainder 
    end
end

 

 

	첫번째 코드	두번째 코드 (개선된 코드)
원소 개수(N)	1, 2, 3, 4 ,5	1, 2, 3, 4, 5
함수 호출 횟수	1, 3, 7, 15, 31	1, 2, 3, 4, 5
빅 오	O(2^N)	O(N)

 

2번 상황 - 피보나치 수열

피보나치 수열은 무한대로 이어지는 수학적 수열이며, 0과 1로 시작하여 이어지는 수는 수열의 앞 두 수 의 합입니다.

0, 1, 1, 2, 3, 4, 8, 13, 21, 34, 55 ... 

 

다음 함수는 피보나치 수열의 n번째 수를 반환합니다.

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

 

 

자기 자신을 두번 호출하는 함수는 O(2^N)이 되기 쉽습니다.

 

 

이를 더 효율적으로 해결하기 위해서는 앞선 문제의 해결방법으로는 해결할 수 없습니다.

한가지의 경우를 저장하는 것 만으로는 나머지의 경우를 얻을 수 없기 때문입니다. 이를 일컬어 하위 문제 중첩(overlapping subproblems)라고 부릅니다.

하위 문제: 동일한 문제를 작게 만들어 해결함으로써 어떤 문제를 풀 때 더 작은 문제. 더 작은 수를 계산하는 것.

- 피보나치 수열에서는 더 작은 수 를 먼저 계산해서 각 수를 계산합니다.

중첩: 같은 함수를 여러 번 중복해서 호출하는 것.

- 피보나치 수열에서는 fib(n-2) + fib(n-1)을 계산하는데, fib(n-1)은 fib(n-3) + fib(n-2)를 호출하므로 fib(n-2)가 중첩되게 됩니다.

 

이 문제를 해결하기 위해서 다음과 같은 두가지의 해결 방법이 존재합니다.

해결 방법 1: 메모이제이션을 통한 동적 프로그래밍

동적 프로그래밍 Dynamic Programming은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차입니다.

(Dynamic이라는 용어의 쓰임에 대한 논란이 많다고 합니다. - 다이나믹이라 부르긴 하지만 언제나 동적으로 해결하진 않는다)

메모이제이션(memoization)은 memorization의 뜻과 비슷하게 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시키는 방법입니다.

피보나치 예제에서는 해시 테이블을 사용해 모든 함수의 호출 결과를 저장할 수 있습니다.

개선된 코드는 다음과 같습니다.

def fib(n, memo): # memo는 해시테이블이 담긴 변수
	if n == 1 or n == 1:
    	return n
        
    if not memo.get(n):
    	memo[n] = fib(n-2, memo) + fib(n-1, memo)
    
    return memo[n]

원소 개수(N)	1, 2, 3, 4, 5
함수 호출 횟수	1, 3, 5, 7, 9, 11

 

N에 대해 2(N-1)번 호출 하는 것을 알 수 있습니다.

빅 오 표기법은 상수는 제외하므로 O(N) 알고리즘이라고 할 수 있습니다.

 

해결 방법 2: 상향식을 통한 동적 프로그래밍

"상향식" 메모이제이션보다 덜 세련되며 "기법"이라 부르기에도 애매하다고 합니다.

상향식은 그저 재귀 대신 루프 같은 다른 방식으로 해결한다는 뜻입니다.

이런 상향식이 동적 프로그래의 하나로 간주되는 이유는, 중첩되는 하위 문제를 중복 호출하지 않게 해주기 때문입니다.

그래서 루프 또한 이러한 방법 중 하나라고 볼 수 있습니다.

 

def fib(n):
	if n == 0:
    	return 0
    
    a = 0
    b = 1
    
    for i in range(1, n):
    	temp = a
        a = b
        b = temp + a
    
    return b

1부터 N까지의 간단한 루프이므로 N단계가 걸립니다. 메모이제이션 방식처럼 O(N)입니다.

 

 

마무리

간결하고 직관적인 해법이면 재귀 + 메모이제이션 방식을 사용할 수 있습니다.

반복적 방식도 충분히 직관적이면 반복(상향식)으로 해결할 수 있습니다.

 

메모이제이션을 쓰더라도 재귀를 사용하기 때문에 호출 스택에 모든 호출을 기록해야하므로 메모리를 소모합니다.

또한 해시 테이블을 사용하기 떄문에 마찬가지로 메모리를 사용하기 때문에 반복에 비해 오버헤드가 더 발생할 수 있습니다.

 

재귀가 매우 직관적이지 않은 이상, 일반적으로 상향식을 택하는 편이 더 낫다고 합니다.

재귀가 직관적인 경우에는 메모이제이션 추가 사용으로 더 빠르게 만들어야 합니다.