11장 재귀적으로 작성하는 법
-
재귀 카테고리 : 반복실행
//단순히 함수를 반복적으로 호출하는 재귀 함수 function countdown(number) { console.log(number); if (number === 0) { return; } else { countdown(number - 1); } }- 추가 인자 넘기기
//index를 추가 인자로 전달하면서 배열 내의 숫자를 두배로 바꾸는 재귀 함수 function doubleArray(array, index=0) { if (index >= array.length){ return } array[index] *= 2; doubleArray(array, index + 1) }
- 추가 인자 넘기기
-
재귀 카테고리 : 계산
//팩토리얼을 구하는 재귀 함수 function factorial(num) { if (num === 1 || num === 0) return 1 return num * factorial(num-1) }factorial(6) = 6 * factorial(5)인것 처럼 호출되는 재귀 함수를 하위 문제라고 부르며 하위 문제를 호출하면 계산하는 방식을 하향식이라고 한다.//상향식 호출로 팩토리얼을 구하는 재귀 함수 function factorial(num, i=1, product=1) { if (i > num) return product return factorial(num, i+1, product*i) }상향식으로도 팩토리얼을 계산할 수 있지만 i, product 처럼 추가적인 변수가 필요하며 루프와 같은 전략으로 계산한다.
- 하향식 재귀 : 새로운 사고방식
- 하향식 사고 절차
- 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자.
- 문제의 하위 문제를 찾자.
- 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.
- 배열 합
function sum(array) { if (array.length === 1) { return array[0] } return array[0] + sum(array.slice(1)) } - 문자열 뒤집기
function reverse(string) { if (string.length === 1) { return string[0] } return reverse(string.slice(1)) + string[0] } - X 세기
책의 ruby 코드를 javaScript 코드로 변경function countX(string) { if (string.length === 0) return 0 if (string[0] === "x") { return 1 + countX(string.slice(1, string.length)) } else { return countX(string.slice(1, string.length)) } }
- 하향식 사고 절차
- 계단 문제
//한번에 계단을 한개 또는 두개 또는 세개씩 올라갈 수 있을때 계단 수에 따라 오르는 방법의 경우의 수를 리턴하는 재귀 함수 function numberOfPaths(n) { if(n < 0) return 0 if(n === 1 || n === 0) return 1 return numberOfPaths(n-1) + numberOfPaths(n-2) + numberOfPaths(n-3) }- 11번째 계단으로 오르는 경우의 수가 10번째, 9번째, 9번째 계단까지 가는 모든 경로의 수의 합으로 세가지의 하위 문제를 갖는 재귀함수이다.
- 애너그램 생성
def anagrams_of(string) return [string[0]] if string.length == 1 collection = [] substring_anagrams = anagrams_of(string[1, string.length - 1]) substring_anagrams.each do |substring_anagram| (0..substring_anagram.length).each do |index| copy = String.new(substring_anagram) collection << copy.insert(index, string[0]) end end return collection end
문자 4개: 애너그램 4 3 2 1개//위 루비로 작성된 애너그램 함수와 동일한 순열을 리턴하는 함수 function findPermutations(string) { if (string.length === 1){ return string } let permutationsArray = [] for (let i = 0; i < string.length; i++){ let char = string[i] if (string.indexOf(char) != i) continue let remainingChars = string.slice(0, i) + string.slice(i + 1, string.length) for (let permutation of findPermutations(remainingChars)){ permutationsArray.push(char + permutation) } } return permutationsArray }
문자 5개: 애너그램 5 4 3 2 1개
위와 같은 팩토리얼(factorial)과 같은 패턴으로 애너그램의 개수가 증가하며 빅오 표기법으로 O(N!)으로 나타낸다. 이를 계승 시간이라고도 부르며 매우 느린 시간복잡도 이지만 모든 애너그램을 생성하는데 N!보다 나은 방법이 없다.
12장 동적 프로그래밍
-
불필요한 재귀 호출
function max(array) { if (array.length == 1) return array[0] if (array[0] > max(array.slice(1))){ return array[0] } else { return max(array.slice(1)) } }- 배열에서 최대값을 구하는 함수로 max 함수가 조건문 안에서와 리턴문에 중복해서 쓰여져 있어 불필요하게 재귀가 호출된다.
-
빅 오를 위한 작은 개선
function max(array) { if (array.length == 1) return array[0] const maxOfRemainder = max(array.slice(1)) if (array[0] > maxOfRemainder){ return array[0] } else { return maxOfRemainder } }- 중복되어 호출되고 있던
max(array.slice(1))를 변수에 저장하여 불필요한 재귀를 개선하였다. - 개선되기 전의 함수는 시간복잡도 O(2N)으로 원소 개수가 늘어날 때마다 호출 횟수가 약 2배씩 늘어나는 반면 개선된 함수는 O(N)의 시간복잡도를 가진다.
- 중복되어 호출되고 있던
-
하위 문제 중첩
function fibonacci(n) { if (n === 0 || n === 1) return n return fibonacci(n - 2) + fibonacci(n - 1) }- 피보다치 수열은 0과 1로 시작하며 이어지는 수는 수열의 압 두수의 합인수열이다.
- 위 재귀함수에 의해 피보나치 수열의 수를 구한다면
- fibonacci(4)를 구하기 위해서
- fibonacci(2) + fibonacci(3)을 구하고
- 그 다음으로 fibonacci(0) + fibonacci(1) + fibonacci(1) + fibonacci(2)
- 이렇게 n이 0이나 1이 될때까지 재귀함수를 중복해서 호출하게 되는데 이를 하위 문제 중첩이라고 한다.
-
메모이제이션을 통한 동적 프로그래밍
function fibonacci(n) { let fibonacciArr = [0, 1]; function addFibonacci(n) { if (fibonacciArr[n] !== undefined) return fibonacciArr[n]; fibonacciArr[n] = addFibonacci(n - 1) + addFibonacci(n - 2); return fibonacciArr[n]; } return addFibonacci(n) }- 하위 문제 중첩을 해결하기 위해 배열에 피보나치 수열을 저장하여 중복 계산되지 않도록 변경하였는데 이렇게 동일한 연산을 저장하여 중복 호출되지 않도록 하는 기법을 메모이제이션(memoization)이라고 한다.
- max 함수 예제와 동일하게 시간복잡도 O(2N)에서 시간복잡도 O(N)으로 개선되었다.
-
상향식을 통한 동적 프로그래밍
function fibonacci(n) { if (n === 0) return let a = 0; let b = 1; for (let i=1; i<=n; i++) { let temp = a a = b b = temp + b } return b }- 재귀가 n번째 수를 구하기 위해 n-1 + n-2 처럼 하향식으로 재귀를 호출하는 반면 위 함수처럼 0, 1로 시작해 루프를 통해 상향식으로도 구현이 가능하며 시간복잡도는 메모이제이션된 재귀 함수와 동일한 O(N)이다.
- 재귀가 주어진 문제를 푸는 간결하고 직관적인 해법이더라도 재귀를 사용하면 컴퓨터는 호출 스택에 모든 호출을 기록해 메모리를 소모하므로 상향식을 택하는 편이 낫다.
13장 속도를 높이는 재귀 알고리즘
- 분할
- 분할을 한다는 것은 배열로부터 임의의 수를 가져와(이 수를 피벗이라 부름) 피벗보다 작은 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다.
1. 두 포인터를 사용해 하나는 배열 가장 왼쪽에 다른 하나는 피벗을 제외한 배열 가장 오른쪽에 있는 값에 할당한다.
2. 왼쪽 포인터를 한 셀씩 계속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
3. 오른쪽 포인터를 한 셀 씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 또는 배열 맨 앞에 도달해도 멈춘다.
4. 왼쪽 포인터가 오른쪽 포인터에 도달했으면 (또는 넘어섰으면) 다음 단계로 넘어가고 그렇지 않으면 2, 3, 4단계를 반복한다.
5. 왼쪽 포인터가 현재 가리키도 있는 값과 피벗을 교환한다.
- 위 과정을 마치면 피벗 왼쪽에는 피벗보다 작은 값, 오른쪽에는 피벗보다 큰 값이 위치하게 되어, 피벗이 올바른 위치에 있게 된다.- 퀵 정렬
1. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 분할 과정을 거치고 그 이후의 하위 배열에도 분할과정을 재귀적으로 반복한다.
2. 하위 배열이 원소를 0개 또는 1개를 포함하면 정렬을 마친다. //부트캠프에서 구현했던 퀵정렬 함수
//왼쪽 포인터와 오른쪽 포인터를 비교해서 위치를 바꾸는 부분이 함수와 차이가 있다.
const quickSort = function (arr) {
if (arr.length <= 1) return arr;
let pivot = arr[0];
let left = [];
let right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) left.push(arr[i]);
else right.push(arr[i]);
}
let leftArr = quickSort(left);
let rightArr = quickSort(right);
return [...leftArr, pivot, ...rightArr];
}-
퀵 정렬의 효율성
- 한번 분할할때 효율성
- 비교 : 각 값과 피벗을 비교한다.
- 교환 : 적절한 때에 왼쪽과 오른쪽 포인터가 가리키고 있는 값을 교환한다.
- 각 분할마다 배열 내 각 원소를 피벗과 비교하므로 최소 N번 비교하고 교환은 최대 N / 2번 평균적으로 N / 2번 교환한다. => 즉 데이터 원소가 N개 일때 분할 한번당 1.25N 단계 즉, O(N)의 시간복잡도를 가진다.
- 분할되는 배열이 반으로 나누어진다고 가정할때 분할이 일어나는 수(logN)와 한번 분할에서 일어나는 연산의 단계 계산해보면 O(NlogN)의 시간 복잡도를 가진다.
- 한번 분할할때 효율성
-
퀵정렬의 최악의 시나리오
- 분할이 배열을 절반으로 나눈다고 가정했을때 시간복잡도가 logN이지만 최악의 경우 한 배열에 원소 하나만 포함하도록 분할이 이루어진다고 가정하면 각 분할마다 하위 배열에 있는 원소 수만큼 비교하여 N + (N - 1) + (N - 2) + ... + 1단계로 총 N2 / 2 => O(N2)의 시간복잡도를 가진다.
-
퀵 정렬 대 삽입 정렬
최선의 경우 평균적인 경우 최악의 경우 삽입 정렬 O(N) O(N2) O(N2) 퀵 정렬 O(NlogN) O(NlogN) O(N2) 최악의 경우에는 삽입 정렬과 퀵 정렬의 시간복잡도가 동일하고 최선의 경우에는 삽입 정렬이 더 빠르지만 평균적인 경우에는 퀵 정렬이 훨씬 빠르기 때문에 내부적으로 퀵 정렬을 사용해 내장 정렬 함수를 구현하는 언어가 많다.
-
퀵 셀렉트
- 무작위로 정렬된 배열에 열 번째로 작은 값 혹은 열다섯 번째로 큰 값ㅇ르 알고 싶다고 할때 전체 배열을 정렬한 후 해당 인덱스를 찾으면 되지만 퀵 셀렉트라는 알고리즘을 사용하면 더 나은 성능을 낼 수 있다.
- 분할 단계에서 피벗이 올바른 위치에 있게 되기 때문에 찾으려는 값이 포함된 배열만 분할 단계를 거치면서 전체 재열을 정렬하지 않고도 올바른 값을 찾을 수 있다.
//퀵 셀렉트 구현 코드 function partitionStart(arr, left, right) { var pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left; var storeIdx = left, pivotVal = arr[pivotIdx] for (var i = left; i <= right; i++) { if (arr[i] < pivotVal) { swap(arr, storeIdx, i) storeIdx++ } } return storeIdx; } function quickSelectLoop(arr, k) { var pivotDist; var left = 0, right = arr.length - 1; while(right !== left) { pivotDist = partitionStart(arr, left, right) if (k < pivotDist) { right = pivotDist - 1; } else { left = pivotDist; } } return arr[k] }- 배열의 원소가 8개일때 퀵 셀렉트는 3번 분할: 8 + 4 + 2 즉, N + (N / 2) + (N / 4) + ... + 2단계로 약 2N => O(N)의 시간복잡도를 가진다.
-
다른 알고리즘의 핵심 역할을 하는 정렬
- 현재까지 가장 빠른 정렬 알고리즘의 속도는 O(NlogN)으로 정렬을 사용해서 다른 알고리즘의 효율성을 개선할 수 있다.
- 중복이 있는지 확인하는 알고리즘의 시간복잡도는 O(N2)(메모리를 소모하는 O(N)방식은 없다고 가정)였으나 정렬을 한 이후에 중복여부를 계산하면 각 원소와 다음 원소가 같은지 비교하며 한번의 루프만 돌면 되기 때문에 NlogN(정렬) + N(비교)의 단계가 걸린다.
function hasDuplicateValue(array) { array.sort((a, b) => (a < b) ? -1 : 1); for(let i = 0; i < array.length - 1; i++) { if (array[i] === array[i + 1]) { return true; } } return false; }- 빅 오 표기법으로 O(N2) => O(NlogN)으로 시간복잡도가 개선되었다.
마치며
이전에는 알고리즘을 이해해서 코드로 구현하고 응용을 통해 문제를 푸는데 집중했엇는데, 책을 통해 다시 공부하면서 효율성을 생각하고 최선, 평균의 경우를 고려하여 개선하는 방향을 생각한다는 것이 큰 차이점이였다. 코딩 테스트는 자료구조와 알고리즘을 이해하는데 도움이 되겠지만 사실 취업이나 대회에 초점을 맞춘 공부라고 생각하기 때문에 실무에서 시간복잡도를 계산하고 나은 방향을 이끌어내는데는 지금의 공부가 맞다고 느꼈다.
개발자로 성장하기