인프런 워밍업 클럽 스터디 3기 - DS/AL <3주 발자국>
알고리즘재귀(Recursion)어떠한 것을 정의할 때 자기 자신을 참조하는 것. 복잡한 문제를 간단한 하위 문제로 나누어 해결할 수 있다.재귀적으로 정의한 함수를 재귀함수라고 한다.function func(number) { console.log(number) return number+1; } func(number)콜스택의 메모리 공간만큼 찬 뒤에 종료된다.기저 조건이 없기 때문에 언제 종료될 지 모른다.재귀 함수는 기저 조건이 반드시 있어야 한다.function func(number) { if (number >= 11) { return ; } console.log(number) return number+1 }콜스택은 함수가 호출되며 올라가는 메모리 영역이다.콜스택은 filo 구조이다. 함수가 호출 될 때마다 콜스택에 쌓이고 함수가 종료되면 콜 스택에서 제거된다.콜스택의 메모리가 가득 차면 더 이상 쌓일 스택이 없어서 제거된다.재귀적으로 생각하기패턴 1단순히 반복 실행. 이 방법은 콜스택의 공간을 많이 차지 하여 단순 반복문에 비해 좋지 않다.패턴 2하위 문제의 결과를 기반으로 현재 문제를 계산(하향식 계산)하향식 계산은 주로 재귀 함수를 통해 구현가능하다.// 주어진 배열의 합을 구하는 문제 // 부분 배열에 마지막 원소를 더해 답을 도출할 것임 function sumArray(arr) { if (arr.length == 0) { return null; } if (arr.length == 1) { return arr[0]; } return sumArray(arrs.slice(0, -1)) + arr[arr.length - 1] }// 문자열의 길이를 계산하는 문제 function strLength(arr) { if (arr.length == 0) { return 0; } return strLength(arr.slice(0, -1)) + 1; }function power(x, n) { if (n <= 0) { return 1; } return power(x, n - 1) * x; }하노이의 탑재귀 함수의 하향식 계산을 보여줄 수 있는 방법function hanoi(count, from, to, temp) { if (count == 0) { return ; } hanoi(count-1, from, temp, to) console.log(`원판 ${count}를 ${from}에서 ${to}로 이동`) hanoi(count-1, temp, to, from) } hanoi(3, "A", "C", "B")정렬 - 버블정렬정렬 알고리즘은 여러 가지가 존재한다.버블정렬은 현재 숫자와 비교하는 숫자의 비교하여 위치를 바꾸는 방법이다.현재 숫자가 크다면 비교하는 숫자와 위치를 바꾸어서 제일 마지막에 가장 큰 값을 위치시킨다.이런 식으로 제일 마지막에 있는 숫자는 정렬에 초기화 하지 않고 하나 씩 줄여서 정렬을 계산시킨다.function BubbleSort(arr) { for (let i =0; i < arr.length; i++) { for (let j = 0; j < arr.length -i -1; j++) { if (arr[j] > arr[j + 1]) { let temp = arr[j] arr[j] = arr[j+1] arr[j+1] = temp } } } }n을 거칠때마다 마지막의 원소가 하나 씩 정렬된다.O(n^2 / 2)이 되는데 자연수는 제거한다. 따라서 O(n^2)이 된다.장점 : 가장 쉽게 생각할 수 있고 이해와 구현이 간단함.단점 : O(N^2)이므로 성능이 좋지 못하다.정렬-선택정렬선택정렬은 정렬 되지 않은 원소와 가장 작은값을 첫 번 째 원소로 가져온 뒤 그 부분을 치환하고 계속해서 정렬해 나간다.function SelectSort(arr) { for (let i= 0; i < arr.length - 1; i++) { let minValueIndex = i for (let j = i+1; j < arr.length; j++) { if (arr[j] < arr[minValueIndex]) { minValueIndex = j } } let temp = arr[i] arr[i] = arr[minValueIndex] arr[minValueIndex] = temp } }성능은 버블 정렬과 같이 O(n^2)이 된다.장점 : 이해와 구현이 쉽다.단점 : 성능이 좋지 못하다.정렬 - 삽입정렬삽입정렬은 정렬되지 않은 영역의 가장 앞에 있는 숫자를 하나씩 정렬된 영역에 삽입하며 진행한다.function InsertionSort(arr) { for (let i = 1; i < arr.length; i++) { let insertingData = arr[i] let j for (j = i - 1; j >= 0; j--) { if (arr[j] > insertingData) { arr[j + 1] = arr[j] } else { break; } } arr[j + 1] = inseringData } }성능은 선택정렬과 같이 O(n^2)이 된다.장점 : 이해와 구현이 쉽다.단점 : 성능이 좋지 못하다.정렬 - 병합정렬분할정복을 이용한 정렬이다.배열을 반으로 줄이고 이걸 계속 반복하여 1이 나올때까지 분할한 뒤 두 배열을 정렬하여 하나의 배열로 병합하는 것이다.function MergeSort(arr, leftIndex, rightIndex) { if (leftIndex < rightIndex) { let midIndex = parseInt((leftIndex + rightIndex) / 2) MergeSort(arr, leftIndex, midIndex) MergeSort(arr, midIndex+1, rightIndex) Merge(arr, leftIndex, midIndex, rightIndex) } } function Merge(arr, leftIndex, midIndex, rightIndex) { let leftAreaIndex = leftIndex let rightAreaIndex = midIndex + 1 let tempArr = [] tempArr.length = rightIndex + 1 tempArr.fill(0, 0, rightIndex+1) let tempArrIndex = leftIndex while(leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) { if (arr[leftAreaIndex] <= arr[rightAreaIndex]) { tempArr[tempArrIndex] = arr[leftAreaIndex++] } else { tempArr[tempArrIndex] = arr[rightAreaIndex++] } tempArrIndex++ } if(leftAreaIndex > midIndex) { for (let i = rightAreaIndex; i <= rightIndex; i++) { tempArr[tempArrIndex++] = arr[i] } } else { for (let i = leftAreaIndex; i<= midIndex; i++) { tempArr[tempArrIndex++] = arr[i] } } for (let i = leftIndex; i<= rightIndex; i++) { arr[i] = tempArr[i] } }장점 : O(nlogn)으로 성능이 좋음단점 : 이해와 구현이 어려움정렬 - 퀵정렬pivot을 설정하여 피봇을 기준으로 정렬하는 정렬방법이다.function quickSort(arr, left, right) { if (left <= right) { // 정렬된 pivot의 위치를 정렬 let pivot = devide(arr, left, right) quickSort(arr, left, pivot - 1) quickSort(arr, pivot+1, right) } } function devide(arr, left, right) { let pivot = arr[left] let leftStartIndex = left + 1 let rightStartIndex = right while (leftStartIndex <= rightStartIndex) { while (leftStartIndex <= right && pivot >= arr[leftStartIndex]) { leftStartIndex+= 1 } while (rightStartIndex >= left + 1 && pivot <= arr[rightStartIndex]) { rightStartIndex -= 1 } if (leftStartIndex <= rightStartIndex) { swap(arr, leftStartIndex, rightStartIndex) } } swap(arr, left, rightStartIndex) return rightStartIndex } function swap(arr, left, rightStartIndex) { let temp = arr[left] arr[left] = arr[rightStartIndex] arr[rightStartIndex] = temp }퀵 정렬이 더 적은 비교와 더 나은 메모리를 사용하기 때문에 퀵 정렬이 더 좋은 알고리즘으로 평가받는다.동적 프로그래밍 - 메모이제이션분할 정복을 통해 문제를 해결할 경우 저장 장치를 사용하여 시간 복잡도를 많이 줄일 수 있다.// 메모이제이션이 없을 경우 function fibo(n) { if (n == 0 || n == 1) { return n } return fibo(n-1) + fibo(n-2) }위의 코드는 중복으로 계산되는 식이 매우 많다.메모이제이션은 계산결과를 저장하여 사용하는 것이다.해시테이블을 사용하여 메모이제이션을 구현해보자.function fibo(n, memo) { if (n == 0 || n == 1) return n if (memo[n] == null) { memo[n] = fibo(n-2,memo) + fibo(n-1, memo) } return memo[n] }메모이제이션을 사용하지 않는다면 O(n^2)이고 메모이제이션을 사용하면 O(n)이 소모된다.동적 프로그래밍 - 타뷸레이션타뷸레이션은 상향식 계산방식으로 계산에 필요한 모든 값을 계산 후 테이블에 저장해둔다.function fibo(n) { if (n == 0 || n == 1) {return n} let table = [0,1] for (let i = 2; i <= n; i++) { table[i] = table[i - 2] + table[i - 1] } return table[n] }메모이제이션은 공간을 차지하고 콜 스택으로 인한 함수 호출이 걸리지만 타뷸레이션은 콜 스택 메모리를 사용하지 않는다.메모이제이션은 재귀적으로 문제를 하위문제로 나눈다. 어떤 문제의 경우에는 재귀가 직관적이지 않다. 따라서 타뷸레이션을 사용하는 것이 더 좋을 수도 있다.
