알고리즘

재귀(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]
}

메모이제이션은 공간을 차지하고 콜 스택으로 인한 함수 호출이 걸리지만 타뷸레이션은 콜 스택 메모리를 사용하지 않는다.

메모이제이션은 재귀적으로 문제를 하위문제로 나눈다. 어떤 문제의 경우에는 재귀가 직관적이지 않다. 따라서 타뷸레이션을 사용하는 것이 더 좋을 수도 있다.