[책] 누구나 자료구조와 알고리즘 - 11장 재귀적으로 작성하는 법

https://product.kyobobook.co.kr/detail/S000001834743

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

 

이번 장에서는 재귀 작성법에 대해 알아 볼 것이다.

재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미치지만, 우선은 재귀적 사고방식을 기르는 데 집중한다.

 

1. 재귀 카테고리: 반복 실행 - 상향식

재귀에는 다양한 "카테고리"가 존재한다.

어떤 카테고리에 효과적인 기법을 터득하면 같은 카테고리에 속하는 문제와 마주했을 때 같은 기법을 적용할 수 있다.

 

가장 쉬운 카테고리는 반복적으로 한 작업을 실행하는 알고리즘이다.

ex) 카운트 다운 (10, 9, ..., 2, 1, 0)

// 자바 스크립트로 작성한 재귀
function countdown(number) {
	console.log(number);
    
    if(number === 0) { // 기저 조건 (base case)
    	return;
    } else {
    	countdown(number - 1);
    }
}

 

 

재귀 트릭: 추가 인자 넘기기

예제: 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성한다.

단, 새 배열을 만드는 것이 아니라 배열 자체에서 수정.

 

제자리 수정(in-place)
1) 새로운 배열을 생성해 배열의 값을 바꿀 수도, 2) 원본 배열을 바꿔 새로운 배열은 원본을 가리키게 할 수도 있다.

 

재귀 작성하는 방법

1. 반복문으로 작성하기 - 상향식(bottom up) 방식
2. 반복문을 재귀로 대체 하기 -> ⭐️인수를 늘리기⭐️
3. 기저조건을 추가하기 (배열이 끝날 때)

 

# 파이썬 코드
# 언어에 따라 index를 다른 줄에 선언해야할 수도 있다
def double_array(array, index=0):
	# 기저 조건: 인덱스가 배열 끝을 지날 때
    if index >= len(array):
    	return
        
    array[index] *= 2
    double_array(array, index + 1)

 

 

2. 재귀 카테고리: 계산 - 하향식

계산 수행이 목적인 함수일 때는 입력을 받아 그 입력에 따른 계산 결과를 반환한다. (ex. 두 수의 합, 배열에서 최댓값 찾기)

- 하위 문제(subproblem)의 계산 결과에 기반해 계산할 수 있을 때 재귀가 유용하게 쓰인다. (ex. 10장에서 계승 문제)

 

하위 문제: 입력을 더 작게 한 똑같은 문제

 

6의 계승(factorial): 6 x 5 x 4 x 3 x 2 x 1

# 루비
def factorial(n)
	product = 1
    
    (1..n).each do |num|
    	product += num
    end
    
    return product
end

 

하위 문제에 기반해 계승을 계산하기 - 하향식(top down) 방식

factorial(6) 은 6 * factorial(5)와 같다.

# 루비
def factorial(number)
	if number == 1 # 기저조건
    	return 1
    else
    	return number * factorial(number - 1)
    end
end

 

위 문제를 상향식(bottom up) 전략으로 풀어보기 : 인자를 추가로 전달하는 비법 사용

def factorial(n, i=1, product=1)
	return product if i > n
    return factorial(n, i + 1, product * i)
end

 

3. 하향식 재귀: 새로운 사고방식

재귀는 하향식 방식을 구현하는 데 탁월하다.

하향식 사고방식은 문제를 해결하는 새로운 사고 전략(mental strategy)을 제공하기 때문이다.

 

상향식으로 풀 때: 통상적으로 고려해야 하는 문제의 본질에 세부적으로 파고들어야 한다.
하향식으로 풀 때: 문제를 뒤로 미루게 된다. 상향식으로 풀 때 고려해야하는 문제 고려하지 않아도 된다.

 

하향식 구현 핵심 줄

return number * factorial(number - 1)

factorial() 함수가 어떻게 동작하는지 코드를 작성할 때 몰라도 된다. (내부 구현 알 필요x)

늘 그 함수가 올바른 값을 반환하리라고 가정한다.

세부 사항은 하위 문제에서 다루게 두면 된다.

 

하향식 사고 절차

1. 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상한다.
2. 문제의 하위 문제를 찾는다.
3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고, 거기서 부터 시작한다.

예제: 배열 합

주어진 배열 내 모든 수를 합하는 sum 함수를 작성한다.

ex) sum([1, 2, 3, 4, 5]) -> return 15

 

1. 2. sum([1, 2, 3, 4, 5]) 는 1 + sum([2, 3, 4, 5])와 같을 것이다.

# 루비
def sum(array)
	return array[0] + sum(array[1, array.length - 1])
end

 

3. sum([5]) 였을 때의 하위 조건을 생각해보고 기저 조건을 추가한다.

# 루비
def sum(array)
	# 기저 조건, 배열에 원소가 하나만 남았을 때
    	return array[0] if array.length == 1
	return array[0] + sum(array[1, array.length - 1])
end

 

예제: 문자열 뒤집기

문자열을 받으면 뒤집는 reverse 함수를 작성한다.

ex) reverse("abcde") -> return "edcba"

 

1. 2. reverse("abcde")는 reverse("abcd") + "e" 와 같을 것이다.

# 루비
def reverse(string)
	return reverse(string[1, string.length - 1]) + string[0]
end

3. reverse("a") 였을 때의 하위 조건을 생각해보고 기저 조건을 추가한다.

def reverse(string)
	# 기저 조건, 문자열 길이가 1일 때
    	return string[0] if string.lenth == 1
	return reverse(string[1, string.length - 1]) + string[0]
end

 

예제: X 세기

주어진 문자열에서 문자 "x"의 개수를 반환하는 함수를 작성한다.

ex) count_x("axbxcxd") -> return 3

 

1. 2. count_x("axbxcxd") 는 ("a"가 "x"라면 1, 아니면 0) + count_x("xbxcxd")와 같을 것이다.

# 루비
def count_x(string)
	if string[0] == "x"
    	return 1 + count_x(string[1, string.length - 1])
    else
    	return count_x(string[1, string.length-1)
    end
end

3. count_x("d") 였을 때의 하위 조건을 생각해보고 기저 조건을 추가한다.

위와 같은 방식으로 하면 이상한 코드가 탄생한다.

def count_x(string)
# 이상한 부분 start
    if string.length == 1
	    if string[0] == "x"
    		return 1
	    else
    		return 0
        end
    end
# 이상한 부분 end   	
    if string[0] == "x"
    	return 1 + count_x(string[1, string.length - 1])
    else
    	return count_x(string[1, string.length-1)
    end
end

 

많은 언어에서 string[1, 0] 을 호출하면 빈 문자열을 반환하므로 이렇게 수정할 수 있다.

def count_x(string)
# 수정된 부분 start
    return 0 if string.length == 0
# 수정된 부분 end   	
    if string[0] == "x"
    	return 1 + count_x(string[1, string.length - 1])
    else
    	return count_x(string[1, string.length-1)
    end
end

빈 문자열은 "x"가 있을 수 없으므로 0을 반환한다.

 

4. 계단 문제

루프(반복문)로 문제를 풀 수 있는데 이 새로운 사고 전략이 왜 필요할까?

간단한 계산에는 새로운 사고 전략(재귀)이 필요 없을 수도 있다.

하지만 복잡한 함수는 재귀적인 사고 방식으로 코드를 훨씬 쉽게 작성할 수 있다.

 

예제: 계단 문제

N개짜리 계단이 있고 누군가 한번에 하나 혹은 둘, 세 계단까지 올라갈 수 있다고 한다.

계단 끝까지 올라가는 "경로"는 몇 개일까?

11개짜리 계단이면 첫 번째 하위 문제는 10개짜리 계단이다.

하지만 9번째 계단, 8번째 계단에서도 11번째 계단에 도달할 수 있다.

꼭대기(11번째 계단)까지 가는 경로 수
= 10번째 계단까지 가는 경로 수 + 9번째 계단까지 가는 경로 수 + 8번째 계단까지 가는 경로 수

다음은 기저조건을 제외하고 코드로 나타낸 것이다.

# 루비
def number_of_path(n)
	number_of_path(n - 1) + number_of_path(n - 2) + number_of_path(n - 3)
end

 

 

계단 문제 기저 조건

계단 문제의 기저 조건은 알아내기 다소 까다롭다.

음수, 0, 1, 2, 3 중 하나일 수 있기 때문이다.

ex) number_of_path(2) =  number_of_path(1) + number_of_path(0) + number_of_path(-1)

 

이에 대해 하드코딩 하면 다음과 같이 작성할 수 있다. 

def number_of_path(n)
    # 기저 조건
    return 0 if n <= 0
    return 1 if n == 1
    return 2 if n == 2
    return 3 if n == 3
                    
    return number_of_path(n - 1) + number_of_path(n - 2) + number_of_path(n - 3)
end

 

n이 음수일 때는 0, 0이나 1일 때는 1을 반환하게 하면 잘 풀린다.

def number_of_path(n)
    # 기저 조건
    return 0 if n < 0
    return 1 if n == 1 || n == 0
                    
    return number_of_path(n - 1) + number_of_path(n - 2) + number_of_path(n - 3)
end

 

애너그램 생성

가장 복잡한 재귀 문제를 풀어보자.

예제: 주어진 문자열의 모든 애너그램(anagram) 배열을 반환하는 함수를 작성하자

애너그램이란?
문자열 내 모든 문자를 재배열한 문자열이다.
ex) anagram("abc") = ["abc", "acb", "bac", "bca", "cab", "cba"]

 

"abcd"의 하위 문제는 "abc"가 될 수 있다.

"abc"의 애너그램 6개에 대해 각 애너그램 내 가능한 자리마다 "d"를 붙여 "abcd"의 모든 순열을 만들어낼 수 있다.

11장에서 다뤘던 예제 중 가장 복잡한 코드이다.

# 루비
def anagrams_of(string)
	# 기저 조건: string에 문자가 하나일 때
    # 문자 하나짜리 문자열만 포함하는 배열을 반환한다.
    return [string[0]] if string.length == 1
    
    # 모든 애너그램을 저장할 배열을 생성한다.
    collection = []
    
    # 두 번째 문자부터 마지막 문자까지의 부분 문자열에서 모든 애너그램을 찾는다.
    # 예를 들어, string 이 "abcd"면 부분 문자열은 "bcd"이니
    # "bcd"의 모든 애너그램을 찾는다.
    substring_anagrams = anagrams_of(string[1, string.length - 1])
    
    # 각 부분 문자열을 순회한다.
    substring_anagrams.each do |substring_anagram|
    	
        # 0 부터 string 끝을 하나 지난 인덱스까지
        # 부분 문자열의 각 인덱스를 순회한다.
        (0..substring_anagram.length).each do |index|
        
        	# 부분 문자열 애너그램의 복사본을 생성한다.
            copy = String.new(substring_anagram)
            
            # string의 첫 번째 문자를 부분 문자열 애너그램 복사본에 삽입한다.
            # 삽입 위치는 루프에서 접긓나고 있는 인덱스에 따라 달라진다.
            # 이어서 새 문자열을 애너그램 컬렉션에 추가한다.
            collection << copy.insert(index, string[0])
        end
    end
    
    # 전체 애너그램 컬렉션을 반환한다.
    return collection
end

재귀를 쓴다고 코드에서 루프를 전부 없애야 한다는 뜻은 아니다!

 

애너그램 생성의 효율성

문자 3개로 된 문자열이라면 각 문자로 시작하는 순열을 생성한다.

각 순열마다 나머지 두 문자 중 하나를 중간에 올 문자로,

마지막 남은 문자를 마지막 문자로 고른다.

이는 3 x 2 x 1, 즉 6개의 순열이다.

바로 계승 (factorial) 패턴이 된다!

계승을 뜻하는 수학 기호는 느낌표다. 6의 계승은 6!으로 나타낸다.

 

빅 오는 데이터 원소가 N개일 때 얼마나 많은 단계 수가 필요한가라는 핵심 질문에 대한 답이다. (N은 문자열 길이)

길이가 N인 문자열은 애너그램을 N!개 생성한다.

빅 오 표기법으로는 O(N!)으로 나타낸다. 이를 계승 시간(factorial time)이라고도 부른다.

O(N!)은 매우 느리지만 모든 애너그램을 생성해야 하는데 문자 N개로 된 단어에는 애너그램이 N!개이니 더 나은 방법이 없다.

어쨌든 재귀는 위 알고리즘에서 중추적인 역할을 하며, 복잡한 문제를 푸는 데 재귀가 어떻게 쓰이는지 보여주는 중요한 예제다.

시간 복잡도 오래 걸리는 순서: O(N!) > O(2^N) > O(N^2) 

 

마무리

재귀를 사용해 함수를 작성하는 법을 익히려면 연습은 필수이다.

재귀는 다양한 문제를 해결하는 훌륭한 도구이지만 주의깊게 사용하지 않으면 코드가 현저히 느려진다.

12장에서는 재귀를 사용하되 코드를 깔끔하고 빠르게 유지시키는 법을 배울 예정이다.