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

재귀는 때로 O(2^N)과 같이 느린 빅오의 원인이 된다.

배열의 최댓값을 구하는 예제 코드로 재귀가 때로 얼마나 많은 비효율적인 호출을 만들어보는지 확인해볼 수 있겠다.

def get_max_value(arr):
    if len(arr) ==1 : # 만약에 인수로 들어온 배열 원소의 갯수가 1개라면
        return arr[0] # 최댓값은 해당 원소일 것이다
    if arr[0] > get_max_value(arr[1:]) : # 만약 배열의 첫 원소가 나머지 모든 원소들의 최댓값보다 크다면
        return arr[0] # 최댓값은 배열의 첫 원소일 것이다.
    else: # 만약 배열의 첫 원소가 나머지 원소들의 최댓값 보다 작다면
        return get_max_value(arr[1:]) # 나머지 원소들 중의 최댓값이 최댓값이다.

get_max_value([1,2,3,4,5]) 를 실행했을 때, 어떻게 재귀가 실행되는지 하향식으로 살펴보면 아래와 같을 것이다.

get_max_value([1,2,3,4,5]) 실행
→ (배열의 길이는 1이 아니므로) 1과 [2,3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([2,3,4,5]) 호출)
→ (배열의 길이는 1이 아니므로) 2와 [3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([3,4,5]) 호출)

→ (배열의 길이는 1이 아니므로) 3과 [4,5]의 최댓값을 비교 (이를 위해 get_max_value([4,5]) 호출)

→ (배열의 길이는 1이 아니므로) 4와 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
→ (배열의 길이는 1이므로) 5를 리턴

하지만 실제로 코드가 어떻게 실행되는지(그리고 얼마나 비효율적인지)를 정확하게 확인해보기 위해서 바닥 호출부터 호출 사슬(call chain)을 따라 올라가며 상향식으로 분석을 해보면 아래와 같다. (스압 주의하세요)

get_max_value([1,2,3,4,5])
→ (배열의 길이는 1이 아니므로) 1과 [2,3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([2,3,4,5]) 호출)

get_max_value([2,3,4,5])
→ (배열의 길이는 1이 아니므로) 2와 [3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([3,4,5]) 호출)

get_max_value([3,4,5])

→ (배열의 길이는 1이 아니므로) 3과 [4,5]의 최댓값을 비교 (이를 위해 get_max_value([4,5]) 호출)

get_max_value([4,5])

→  (배열의 길이는 1이 아니므로) 4과 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
   →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 4과 5 중 최댓값은 5이므로 get_max_value([5])를 리턴 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 5를 리턴 (get_max_value([4,5]) 의 반환값)
    → 3과 5중 최댓값은 5이므로 get_max_value([4,5])를 리턴 (이를 위해 get_max_value([4,5])호출)

get_max_value([4,5])

    →  (배열의 길이는 1이 아니므로) 1과 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 1과 5 중 최댓값은 5이므로 get_max_value([5])를 리턴 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
  →  5를 리턴 (get_max_value([5]) 의 반환값)

→ 5를 리턴 (get_max_value([3,4,5])의 반환값)

→ 2와 5중 최댓값은 5이므로 get_max_value([3,4,5])를 리턴 (이를 위해 get_max_value([3,4,5]) 호출)

get_max_value([3,4,5])

→ (배열의 길이는 1이 아니므로) 3과 [4,5]의 최댓값을 비교 (이를 위해 get_max_value([4,5]) 호출)

get_max_value([4,5])

    →  (배열의 길이는 1이 아니므로) 4과 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 4과 5 중 최댓값은 5이므로 get_max_value([5])를 리턴 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→  5를 리턴 (get_max_value([4,5]) 의 반환값)
    →  3과 5중 최댓값은 5이므로 get_max_value([4,5])를 리턴 (이를 위해 get_max_value([4,5])호출)

get_max_value([4,5])

→ 5를 리턴 (get_max_value([2,3,4,5])의 반환값)

→ 1과 5중 최댓값은 5이므로 get_max_value([2,3,4,5])을 리턴 (이를 위해 get_max_value([2,3,4,5]) 호출)

get_max_value([2,3,4,5])
→ (배열의 길이는 1이 아니므로) 2와 [3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([3,4,5]) 호출)

get_max_value([3,4,5])

→ (배열의 길이는 1이 아니므로) 3과 [4,5]의 최댓값을 비교 (이를 위해 get_max_value([4,5]) 호출)

get_max_value([4,5])

    →  (배열의 길이는 1이 아니므로) 4과 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 4과 5 중 최댓값은 5이므로 get_max_value([5])를 리턴 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→  5를 리턴 (get_max_value([4,5]) 의 반환값)
    →  3과 5중 최댓값은 5이므로 get_max_value([4,5])를 리턴 (이를 위해 get_max_value([4,5])호출)

get_max_value([4,5])

→ 5를 리턴 (get_max_value([3,4,5])의 반환값)

→ 2와 5중 최댓값은 5이므로 get_max_value([3,4,5])를 리턴 (이를 위해 get_max_value([3,4,5]) 호출)

get_max_value([3,4,5])

→ (배열의 길이는 1이 아니므로) 3과 [4,5]의 최댓값을 비교 (이를 위해 get_max_value([4,5]) 호출)

get_max_value([4,5])

    →  (배열의 길이는 1이 아니므로) 4과 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 4과 5 중 최댓값은 5이므로 get_max_value([5])를 리턴 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→  5를 리턴 (get_max_value([4,5]) 의 반환값)
    →  3과 5중 최댓값은 5이므로 get_max_value([4,5])를 리턴 (이를 위해 get_max_value([4,5])호출)

get_max_value([4,5])

→ 5를 리턴 (get_max_value([2,3,4,5])의 반환값)

.........

ㅎ

솔직히 쓰면서도 이걸 끝까지 써야 하나 ^^; 싶었지만 이토록 재귀가 비효율적일 수 있다는 사실을 잊지 않기 위해 끝까지 꾹 참고 썼다. 이런식으로 돌아가는 재귀 코드는 정말이지 피해야 한다. 결국은 조건문에서 최댓값을 비교하기 위해 재귀를 해놓고, 값을 반환하기 위해 똑같은 재귀를 굳이 똑같이 또 돌리는 게 엄청난 비효율성을 만들어내고 있다.

이렇게 원소가 5개 짜리 배열에서 재귀가 실제 몇번이나 도는지 확인해보려고 중간에 프린트 문을 하나 심어놓고 돌려봤더니 31번 돈다. 빼도박도 못하는 O(2^N) 이다.

def get_max_value(arr):
    print("비효율!!!", end=" ") ## 이렇게 재귀가 돌때마다 프린트 문이 실행되게 해봤더니..
    if len(arr) ==1 :
        return arr[0]
    if arr[0] > get_max_value(arr[1:]) :
        return arr[0]
    else: 
        return get_max_value(arr[1:])

a= [1,2,3,4,5]
print(get_max_value(a))

다행스러운 것은 아주 간단한 코드 수정으로 이 비효율적인 코드 호출을 막을 수 있다. 재귀 호출이 리턴한 값을 변수에 저장해두는 것이다. 이 작은 수정 하나로 필요하지 않은 재귀 호출이 일어나지 않는다. 어떻게 결과가 달라지는지 보자.

def get_max_value(arr):
    print("효율!!!", end=" ") ## 역시나 프린트 문을 심어놓았다. 
    if len(arr) ==1 :
        return arr[0]
    max_of_others = get_max_value(arr[1:])  #재귀 호출이 반환한 값을 저장해두고
    if arr[0] > max_of_others : # 필요한 곳에서는 변수에 저장된 값을 사용한다
        return arr[0]
    else: 
        return max_of_others # 필요한 곳에서는 변수에 저장된 값을 사용한다

a= [1,2,3,4,5]
print(get_max_value(a))

이제 다시 한 번 호출 체인을 분석해보자.

get_max_value([1,2,3,4,5])
→ (배열의 길이는 1이 아니므로) 1과 [2,3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([2,3,4,5]) 호출)

get_max_value([2,3,4,5])
→ (배열의 길이는 1이 아니므로) 2와 [3,4,5]의 최댓값을 비교 (이를 위해 get_max_value([3,4,5]) 호출)

get_max_value([3,4,5])

→ (배열의 길이는 1이 아니므로) 3과 [4,5]의 최댓값을 비교 (이를 위해 get_max_value([4,5]) 호출)

get_max_value([4,5])

    →  (배열의 길이는 1이 아니므로) 4과 [5]의 최댓값을 비교 (이를 위해 get_max_value([5]) 호출)
get_max_value([5])
       →  (배열의 길이는 1이므로) 5를 리턴 (get_max_value([5]) 의 반환값)
→ 4과 5 중 최댓값은 5이므로 get_max_value([5])인 5를 리턴 (get_max_value([4,5]) 의 반환값)
    →  3과 5중 최댓값은 5이므로 get_max_value([4,5])인 5를 리턴 (get_max_value([3,4,5])의 반환값)

→ 2와 5중 최댓값은 5이므로 get_max_value([3,4,5])인 5를 리턴 (get_max_value([2,3,4,5])의 반환값)

→ 1과 5중 최댓값은 5이므로 get_max_value([2,3,4,5])인 5를 리턴 (get_max_value([1,2,3,4,5])의 반환값)

시간복잡도를 보면 배열 내 갯수만큼 실행되기 때문에 O(N)이다. 재귀 호출의 결과를 변수에 저장함으로써 불필요한 재귀호출을 막고 O(2^N)에서 O(N)으로 성능을 개선할 수 있었다. 이러한 점을 염두에 두고, 이제 진짜로 동적 프로그래밍의 방법인 메모이제이션(memoization)과 상향식 접근방법(bottom-up approach)을 공부하러 가보자 !!

참고문헌: 제이 웬그로우, 『누구나 자료구조와 알고리즘』, 심지현, 길벗, 2011

누구나 자료 구조와 알고리즘 - YES24

사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자수학 용어와 전문 용어가 아니어도 이해한다이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거나 고등학교 수학을 잘 안다고 가

www.yes24.com

'자료구조 & 알고리즘' 카테고리의 다른 글

[📚누구나 자료구조와 알고리즘] 3. Big-O Notation : O(N), O(1), O(logN), O(N^2) (1)	2022.09.13
[📚누구나 자료구조와 알고리즘] 2. 알고리즘이 중요한 까닭 - 선형검색과 이진검색 (0)	2022.09.08
[📚누구나 자료구조와 알고리즘] 1. 자료 구조의 기본 연산과 속도 측정 (시간복잡도)의 이해 (0)	2022.09.06

[📚누구나 자료구조와 알고리즘] 12-1. 동적 프로그래밍 - 불필요한 재귀 호출 줄이기

'자료구조 & 알고리즘' 카테고리의 다른 글

댓글

티스토리툴바

[📚누구나 자료구조와 알고리즘] 12-1. 동적 프로그래밍 - 불필요한 재귀 호출 줄이기

'자료구조 & 알고리즘' 카테고리의 다른 글

관련글

댓글

티스토리툴바