사실 재귀는 알고리즘의 시간 복잡도에 몹시 부정적인 영향을 미친다.
이번에는 재귀적으로 작성하는 다양한 카테고리를 살펴보자.
11. 1 재귀 카테고리: 반복 실행
가장 기본적인 카테고리는 '반복적'으로 수행하는 알고리즘이다.
예를 들어 앞에서 살펴본 반복적으로 실행되는 '카운트다운 알고리즘'이 그것이다. 코드는 10에서부터 9, 8, ... , 0까지의 수를 출력한다. 함수의 출력 횟수는 매번 다르나 코드의 본질은 결국 숫자 출력 작업을 반복적으로 실행하는 것이다.
public void countdown(int number) {
System.out.println("카운트 다운 " + number);
if (number == 0) {
return;
} else {
countdown(number - 1);
}
}
여기서 "countdown(number - 1)"의 역할은 다음 재귀 호출이다.
새로운 예시를 만들어보자.
숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성한다면 어떻게 할 것인가? 명확하게 말하면 첫 번째 숫자를 두 배로 만들고, 두 번째 숫자로 넘어가 두 배로 만들고 이 과정을 반복하는 것이다. 이 알고리즘도 한 작업을 반복적으로 실행하는 카테고리에 속한다.
public static int[] doubleArray(int[] array, int index) {
if (index >= array.length) {
return array;
}
array[index] *= 2;
doubleArray(array, index + 1);
return array;
}
if 문에 지저 조건을 만들고, 마지막에 재귀를 수행한다. 메서드 매개변수에 index를 넣어서 연속적인 재귀 호출마다 인덱스를 증가시키고 기록하게 만든다.
11. 2 재귀 카테고리: 계산
이번엔 두 번째 일반적인 카테고리인 하위 문제에 기반해 계산 수행하기를 설명해보자.
두 수의 합을 반환하는 함수나 배열에서 최댓값을 찾는 함수처럼 계산 수행이 목적인 함수가 많다. 이러한 함수는 입력을 받아 그 입력에 따른 계산 결과를 반환한다. 재귀가 유용하게 쓰이는 또 하나의 영역이 바로 '하위 문제의 계산 결과에 기반해 계산할 수 있을 때'다.
계산 함수를 작성하는 방식은 두 가지다. "상향식"과 "하향식"이 그것이다.
상향식은 일반적으로 1 x 2 x 3 x 4 x 5 처럼 하나씩 올라간다. 전형적으로 루프 계산 방식은 상향식을 채택한다. 물론 상향식도 재귀가 가능한데 간결하지 못하며 특별한 장점이 없다.
반면 하향식은 5 x factorial(4) 처럼 '하위 문제'를 기반으로 작동된다. 하향식에서는 재귀를 써야 한다. 하향식 전략을 구현할 방법은 재귀뿐이며 이것이 재귀가 강력한 도구가 된 이유 중 하나다.
11. 3 하향식 재귀: 새로운 사고방식
재귀는 하향식 방식을 구현하는 데 탁월하다. 하향식 사고방식은 "문제를 해결하는 새로운 사고 전략을 제공"하기 때문이다. 즉 재귀적 하향식 방식은 문제를 완전히 다른 방식으로 생각하게 해 준다.
하향식으로 풀어 나갈 때는 머릿속에서 '문제를 뒤로 미루게' 된다.
예를 들어, 하향식 factorial 구현의 핵심 줄을 다시 보자.
return number * factorial(number - 1);
위 코드는 factorial(number - 1)의 결과를 이용해 계산한다. factorial 함수 호출 결과에 기반해 답을 계산할 때 factorial 함수가 어떻게 동작하는지 몰라도 되며 그저 올바른 결과를 반환하리라고 기대할 수 있다. 이는 자신이 바로 그 factorial 함수의 작성자가 되고, 코드 줄은 factorial 함수 내에 존재한다. 그래서 문제를 해결하는 법조차 몰라도 문제를 풀 수 있다.
따라서 하향식 전략을 "재귀적으로" 작성해서 구현할 때는 계산이 실제 어떻게 이뤄지는지 세부적인 내용은 무시해도 좋다. 그저 세부 사항은 하위 문제에서 다루게 두면 된다.
하향식으로 생각하는 절차가 있다.
(1) 작성 중인 메서드를 이미 누가 구현해 놓았다고 상상한다.
(2) 문제의 하위 문제를 찾는다.
(3) 하위 문제에 메서드를 호출하면 어떻게 되는지 보고, 거기서부터 시작한다.
다시 예시로 적용해보자.
만약 주어진 배열 내 모든 수를 합하는 sum이라는 메서드를 작성한다고 하자. 배열 [1, 2, 3, 4, 5]를 전달하면 15를 반환한다.
(1) 가장 먼저 할 일은 sum 메서드가 이미 구현되어 있다고 가정하는 것이다. 억지로 믿는 수밖에 없다. sum 메서드가 잘 동작한다고 상상하자.
(2) 다음으로 하위 문제를 찾는다. 예제의 하위 문제는 첫 번째 원소를 제외한 배열 내 모든 수, 즉 배열 [2, 3, 4, 5]다.
(3) 마지막으로 하위 문제에 sum 메서드를 적용할 때 어떻게 될까. sum 메서드는 "잘 동작"하고 있고, 하위 문제가 [2, 3, 4, 5]이면 sum([2, 3, 4, 5])를 호출할 때 당연히 2 + 3 + 4 + 5인 14가 나온다.
그렇다면 [1, 2, 3, 4, 5]의 합을 구하는 문제를 풀려면 sum([2, 3, 4, 5])의 결과에 첫 번째 수인 1만 더하면 된다.
또 다른 예제를 하나 더 살펴보자.
문자열을 뒤집는 reverse 함수를 작성하려고 한다. 메서드는 "abcde"라는 인수를 받으면 "edcba"를 반환한다.
먼저 하위 문제를 찾자. 보통은 다음으로 가장 작은 문제를 제일 먼저 시도한다. 문자열 "abcde"의 하위 문제를 "bcde"라고 가정하자. 이 하위 문제는 원래 문자열에서 첫 번째 문자를 뺀 것이다.
그리고 누군가 reverse 함수를 구현해 놓았다고 상상하자. reverse 함수를 쓸 수 있고 하위 문제가 "bcde"이니 이제 reverse("bcde")를 호출할 수 있다는 뜻이고 "edcb"가 반환된다. 여기까지 됐다면 "a"처리는 문자열 끝에 붙이기만 하면 된다.
하위 문제에 reverse를 호출하고 그 결과 끝에 첫 번째 문자를 추가하면 끝이다. 정말 간단하다!
'X 세기'라는 예제도 있다. 주어진 문자열에서 "x"의 개수를 반환하는 countX() 메서드를 작성할 것이다. 메서드에 문자열 "axbxcxd"를 전달하면 문자 "x"의 인스턴스가 3개이니 3을 반환한다.
먼저 하위 문제를 찾자. 앞선 예제처럼 하위 문제는 원래 문자열에서 첫 번째 문자를 뺀 것이다. 즉 하위 문제는 "xbxcxd"다.
다음으로 countX()가 이미 구현되어 있다고 상상하자. countX("xbxcxd")라고 하위 문제에 countX를 호출하면 3이 나온다. 만약 첫 번째 문자도 'x'면 여기에 1을 더하면 된다.
10. 4 계단 문제
하향식 재귀로 특정 계산 문제를 해결하는 법을 배웠는데, 여전히 의문이 들 수 있다. 지금까지 루프만으로도 문제를 잘 풀어 왔는데 대체 왜 이런 사고 전략이 필요한가?
간단한 계산에는 필요 없을 수도 있다. 하지만 보다 복잡한 함수라면 재귀적인 사고방식으로 코드를 훨씬 쉽게 작성할 수 있다. 가장 좋은 예시는 "계단 문제"라 불리는 유명한 질문이다.
N개짜리 계단이 있고 누군가 한 번에 하나 혹은 둘, 세 계단까지 올라갈 수 있다고 하자. 계단 끝까지 올라가는 "경로"는 몇 개일까? N개짜리 계단일 때 이를 계산하는 메서드를 작성하자.
5개짜리 계단 끝까지 올라가는 세 가지 경로를 보자.
경로는 세 개다.
우선 상향식 방식으로 풀어보면, 가장 단순한 경우부터 가장 복잡한 경우로 거슬러 올라간다.
계단 수가 하나뿐이면 당연히 가능한 경로도 하나다.
계단 수가 2개면 경로는 2개다. 한 계단씩 두 번 올라가거나, 두 계단을 한 번에 뛰어 올라갈 수 있다.
1, 1
2
계단 수가 3개면 가능한 경로는 4개다.
1, 1, 1
1, 2
2, 1
3
계단 수가 4개면 가능한 경로는 7개다.
1, 1, 1, 1
1, 1, 2
1, 2, 1
1, 3
2, 1, 1
2, 2
3, 1
더 나아가 계단 수가 5개일 때 모든 조합을 구하면 쉽지 않다. 11계단이면 더 복잡해진다.
재귀적 사고방식을 취하지 않으면 알고리즘을 이해하기 힘들다. 하지만 하향식으로 생각하면 문제는 굉장히 단순해진다.
11개짜리 계단이면 머릿속에 떠오르는 첫 번째 하위 문제는 10개짜리 계단이다. 이를 하위 문제로 규정하자. 10개짜리 계단에 오르는 경로 수를 알면 이를 기반으로 11개짜리 계단에 오르는 가능한 경로를 계산할 수 있다.
우선 11개짜리 계단에 오르려면 적어도 10개짜리 계단에 오르는 단계 수만큼은 무조건 필요하다. 즉 10번째 계단까지 오르는 모든 경로를 알면 거기서부터 꼭대기까지 한 계단 더 올라갈 수 있다.
하지만 9번째나 8번째 계단에서도 한 번에 꼭대기까지 올라올 수 있다는 점도 주의해야 한다. 10번째 계단에서 11번째 계단으로 가는 경로를 따를 경우, 9번째 계단에서 11번째 계단으로 가는 경로를 따르지 않을 것이다. 반대로 9번째 계단에서 11번째 계단으로 바로 가면 10번째 계단을 거치는 경로는 따르지 않을 것이다.
즉, 꼭대기까지 가는 경로 수는 최소한 10번째 계단까지 가는 경로 수에 9번째 계단까지 가는 경로 수를 더한 값이다. 또한 한 번에 3계단도 오를 수 있으므로 8번째 계단에서 11번째 계단으로 단번에 뛰어오르는 경로 수도 포함시켜야 한다.
결론적으로 꼭대기까지 가는 경로 수는 적어도 10번째와 9번째, 8번째 계단까지 가는 모든 경로 수의 합이다. N개짜리 계단일 때 경로 수는 다음과 같을 것이다.
numberOfPaths(n - 1) + numberOfPaths(n - 2) + numberOfPaths(n - 3)
이것이 정답이다.
11. 5 애너그램 생성
애너그램(anagram)이란, 문자열 내 모든 문자들을 재배열한 문자열이다. 예를 들어 다음은 "abc"의 애너그램이다.
["abc", "acb", "bac", "bca", "cab", "cba"]
이제 문자열 "abcd"의 모든 애너그램을 구해 보자. 이 문제를 하향식 사고방식으로 접근해 보자.
아마도 "abcd"의 하위 문제는 "abc"일 것이다. 그렇다면 모든 애너그램을 반환하는 anagram() 메서드가 있을 때 이를 사용해 어떻게 "abcd"의 모든 애너그램을 만들어낼까?
"abc"의 애너그램 6개에 대해 각 애너그램 내 가능한 자리마다 "d"를 붙여 "abcd"의 모든 순열을 만들어 낼 수 있다.
애너그램이 몇 개 생성되는지 살펴보면 흥미로운 패턴이 등장한다. 문자 3개로 된 문자열이라면 각 문자로 시작하는 순열을 생성한다. 각 순열마다 나머지 두 문자 중 하나를 중간에 올 문자로, 마지막 남은 문자를 마지막 문자로 고른다. 이는 3 x 2 x 1, 즉 6개의 순열이다. 바로 계승(factorial)이다!
즉 문자열에 문자가 6개면 애너그램 수는 6의 계승이다. 6 x 5 x 4 x 3 x 2 x 1로 계산하면 720이다. 이는 6!로 나타낸다.
빅 오는 데이터 원소가 N개일 때 얼마나 많은 단계 수가 필요한가라는 핵심 질문에 대한 답이었다. 길이가 N인 문자열은 애너그램 N! 개를 생성한다. 빅 오 표기법으로는 O(N!)으로 나타낸다. 이를 '계승 시간(factorial time)'이라고도 부른다.
O(N!)은 매우 느리지만 모든 애너그램을 생성해야 하는데 문자 N개로 된 단어에는 애너그램이 N! 개이니 더 나은 방법이 없다.
11. 6 마무리
재귀를 사용해 함수를 작성하는 법을 익히려면 연습이 필수다. 재귀는 다양한 문제를 해결하는 훌륭한 도구지만 주의 깊게 사용하지 않으면 코드가 현저히 느려진다.
다음 장에서는 재귀를 사용하되 코드를 깔끔하고 빠르게 유지시키는 법을 배워보자.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.
'자료구조 & 알고리즘' 카테고리의 다른 글
| Ch.13 노드 기반 자료 구조 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
|---|---|
| Ch.12 속도를 높이는 재귀 알고리즘 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.09 |
| Ch.10 재귀를 사용한 재귀적 반복 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.06.06 |
| Ch.09 스택과 큐로 간결한 코드 생성 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.11 |
| Ch.08 해시 테이블로 매우 빠른 룩업 (도서 요약 "누구나 자료구조와 알고리즘") (0) | 2022.05.09 |
