19장 동적 프로그래밍

  • 동적 프로그래밍(이하 DP)은 문제를 더 작은 부분들로 쪼개는 과정이 포함된다
  • 해시 테이블을 사용한다면 이미 계산된 피보나치 숫자를 저장할 수 있고 계산 없이 O(1)의 시간으로 그 값을 불러올 수 있기 때문에 더 빠르게 구현할 수 있다
    1
    2
    3
    4
    5
    6
    let cache = {};
    const fiboBest = n => {
      if (n <= 1) return n;
      if(cache[n]) return cache[n];
      return (cache[n] = fiboBest(n-1) + fiboBest(n-2));
    }
  • DP는 재계산을 피하기 위해 이미 계산된 값들을 저장하고 해당 값들을 사용하는 방법이다
    • 중복 부분 문제 : DP에서 보통 문제의 해결책으로 해시 테이블과 배열, 행렬에 저장하는 방식을 사용하는데, 이 방식을 메모이제이션이라고 부른다
    • 최적 부분 구조 : 문제의 부분 최적 해결책을 통해 큰 문제를 해결하는 방법
  • 배낭 문제 알고리즘은 대표적인 DP의 예로 무게와 가치를 지니는 n개의 항목이 주어졌을 때 최대 w의 무게를 담을 수 있는 배낭에 가치의 최대값을 담는 문제
  • 배열(배낭)에 담긴 n개의 항목이 최대값이 되려면
    1. n번째 항목이 제외되는 경우: n-1개의 항목에서 얻은 최대값
    2. n번째 항목을 포함하는 경우: n-1개의 항목에서 얻은 최대값 + n번째 항목의 값
  • 동적 프로그래밍의 구현은 현재 배열 인덱스와 목표치를 객체에 대한 키로 사용해 결과를 저장함 (메모이제이션 활용)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    const knapsackDP = (idx, weights, values, target, matrix) => {
      let result = 0;
      if(matrix[idx + '-' + target]) {
        return matrix[idx + '-' + target]
      }

      if(idx <= -1 || target <= 0) {
        result = 0
      } else if (weights[idx] > target) {
        result = knapsackDP(idx - 1, weights, values, target, matrix);
      } else {
        let current = knapsackDP(idx - 1, weights, values, target, matrix),
            currentPlusOther = values[idx] + knapsackDP(idx - 1, weights, values, target - weights[idx], matrix);
        result= Math.max(current, currentPlusOther);
      }
      matrix[idx + '-' + target] = result
      return result;
    }
  • 최장 공통 부분 수열 알고리즘
  • 두 개의 수열이 있을 때 두 수열의 가장 긴 공통 부분 수열의 길이를 찾는 알고리즘
  • 부분 수열 내 항목들이 연속일 필요는 없고 순서만 맞으면 됨
  • 길이 m인 문자열 str1과 길이 n인 문자열 str2가 함수 LCS를 통해 최장 공통 부분을 구한다면
    1
    2
    3
    4
    5
    6
    if (두 수열의 마지막 글자가 일치한다면) {
      result = 1 + LCS(X[0:m-2], Y[0:n-2])
    }
    if (두 수열의 마지막 글자가 일치하지 않는다면) {
      result = Math.max(LCS(X[0:m-1], Y[0:n-1]), LCS(X[0:m-2], Y[0:n-2]))
    }
  • 재귀를 기반으로 의사 코드를 구현
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    const LCSNaive = (str1, str2, str1Length, str2Length) => {
      if (str1Length === 0 || str2Length === 0) {
        return 0;
      }

      if (str1[str1Length-1] === str2[str2Length-1]) {
        return 1 + LCSNavie(str1, str2, str1Length - 1, str2Length - 1);
      } else {
        return Math.max(
          LCSNavie(str1, str2, str1Length, str2Length - 1),
          LCSNavie(str1, str2, str1Length - 1, str2Length)
          )
      }
    }

    const LCSNaiveWrapper = (str1, str2) => {
      return LCSNaive(str1, str2, str1.length, str2.length);
    }
  • DP식 접근법
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    const longestCommonSequenceLength = (str1, str2) => {
      let matrix = Array(str.length + 1).fill(Array(str2.length + 1).fill(0)), 
          rowLength = str1.length + 1,
          colLength = str2.length + 1,
          max = 0;
      for (let row = 1; row < rowLength; row++) {
        for (let col = 1; col < colLength; col++) {
          let str1Char = str1.charAt(row - 1),
              str2Char = str2.charAt(col - 1);
          
          if (str1Char === str2Char) {
            matrix[row][col] = matrix[row - 1][col - 1] + 1;
            max = Math.max(matrix[row][col], max);
          }
        }
      }
      return max;
    }
  • 동전 교환 알고리즘 : 동전의 금액 종류 M개가 들어있는 객체 S가 주어질때 금액 n을 동전으로 교환하기 위한 조합을 구하는 문제
  • 이때 이 문제의 최적 부분 구조는 (1) M번째 동전이 포함되지 않는 해결책과 (2) M번째 동전이 최소 한 개 포함되는 해결책 으로 나눌 수 있다
    coinChange(S, M, n) = coinChange(S, M-1, N) + coinChanges(S, M, N-Sm)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // coinArr의 인덱스는 [0, ..., coinIndex]
    const countCoinWays = (coinArr, coinIndex, total) => {
      if (total === 0) return 1;
      // total 값이 0에 도달한 경우에는 아무 동전도 포함하지 않는 것
      if (total < 0 || (coinIndex <= 0 && total >= 1)) return 0;
      // total값이 0 보다 작다는 것은 M번째 동전이 포함되거나 포함되지 않을 때의 해결책이 없다는 뜻
      // 남은 동전이 없을 때 (index값은 coinArr.length에서 점점 줄어드므로) total값을 채우지 못해도 해결책이 없다는 뜻

      return countCoinWays(coinArr, coinIndex - 1, total) +
            countCoinWays(coinArr, coinIndex - 1, total - coinArr[coinIndex - 1])
    }
    const countCoinWaysWrapper = (coinArr, total) => {
      return countCoinWays(coinArr, coinArr.length, total);
    }
  • 하지만 이 방법을 사용한다면 중복 부분 문제가 많다
  • 동전 교환 알고리즘을 DP로 구현하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    const countCoinWaysDP = (coinArr, coinIndex, total) => {
      let dpMatrix = [];
      // 메모이제이션용 행렬, 추후 2차원 배열이 된다
      for (let i = 0; i <= total; i++) {
        dpMatrix[i] = [];
        // 원하는 값까지 전부 배열이 들어가게 된다
        for (let j = 0; j < coinIndex; j++) {
          dpMatrix[i][j] = undefined;
          // undefined로 초기화
        }
      }

      for (let i = 0; i < coinIndex; i++) {
        // 맨 윗줄을 1로 채움 (undefined에서 기본값으로)
        dpMatrix[0][i] = 1;
      }

      for (let i = 1; i < total + 1; i++) {
        // 행렬의 세로이동
        for (let j = 0; j < coinIndex; j++) {
          // 행렬의 가로이동
          let temp1 = 0, temp2 = 0;
          // 두 가지의 부분 방법으로 나뉘므로 temp값도 두개가 필요함
          if (i - coinArr[j] >= 0) {
            temp1 = dpMatrix[i - coinArr[j]][j];
            // temp1값에 dpMatrix[0][0] 번값부터 가로줄 값을 저장
          }

          if (j >= 1) {
            temp2 = dpMatrix[i][j-1];
            // temp2값에 dpMatrix[1][0] 값부터  세로줄 값을 저장
          }
          
          // dpMatrix[1][0] 값부터 temp1(M번째 동전이 포함되지 않는 해결책)값과 
          // temp2(M번째 동전이 최소한 한 개 포함되는 해결책)값을 더해 저장
          dpMatrix[i][j] = temp1 + temp2;
        }
      }

      // 결과값이 저장되어있는 것 중에서 total값을 만족하는 행의 max값을 리턴함 
      // if()에서도 i < coinIndex 와 같이 리턴하였으므로 여기서도 -1 해주어야 함
      return dpMatrix[total][coinIndex - 1]
    }

    const countCoinWaysDPWrapper = (coinArr, coinValue) => {
      return countCoinWaysDP(coinArr, coinArr.length, coinValue);
    }
  • 편집 거리 알고리즘 (레벤슈타인 거리 알고리즘)
  • 길이 m인 문자열 str1과 길이 n인 문자열 str2가 주어졌을때 str1을 str2로 변환하기 위환 최소 편집 횟수는? (이 때, 사용가능한 연산은 삽입, 제거, 교환만 가능하다)
    1
    2
    3
    4
    5
    6
    7
    8
    if (문자가 동일하다)
      아무것도하지 않는다
    if (문자가 다르다) {
      1) m과 n-1의 삽입
      2) m-1과 n의 제거
      3) m-1과 n-1의 교환 
      세가지를 재귀적으로 고려
    }
  • Brute-force 방법으로 구현하기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    const editDistanceRecursive = (str1, str2, length1, length2) => {
      // 빈문자열이라면 나머지 한 쪽의 문자열을 그대로 복사하면 되므로 나머지 한 쪽 길이값을 리턴함 (length1 or length2번 시행해야 하므로)
      if (length1 === 0) return length2;
      if (length2 === 0) return length1;

      // 마지막 글자가 같다면 마지막 글자를 제외한 나머지 문자만큼 돌면 된다
      // 이 과정은 재귀적으로 반복되므로 맨 마지막 글자부터 첫번째 글자까지 비교를 할 것
      if (str[length1-1] === str2[length2-1]) 
        return editDistanceRecursive(str1, str2, length1-1, length2-1)

      return 1 + Math.min(
        editDistanceRecursive(str1, str2, length1, length2-1), // 삽입
        editDistanceRecursive(str1, str2, length1-1, length2), // 제거
        editDistanceRecursive(str1, str2, length1-1, length2-1) // 교환
      )
    }

    const editDistanceRecursiveWrapper = (str1, str2) => {
      return editDistanceRecursive(str1, str2, str1.length, str2.length)
    }
  • DP식 접근법
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    const editDistanceDP = (str1, str2, length1 = str1.length, length2 = str2.length2) => {
      let dpMatrix = [];
      for (let i = 0; i < length1+1; i++) {
        dpMatrix[i] = [];
        for (let j = 0; j < length2+1; j++) {
          dpMatrix[i][j] = undefined;
        }
      }
      // let dpMatrix = Array.from({length: length1+1}, 
      //           () => Array.from({length:length2+1}, () => undefined))

      for (let i = 0; i < length+1; i++) {
        for (let j = 0; j < length2+1; j++) {
          if (i === 0) {
            dpMatrix[i][j] = j;
          } else if (j === 0) {
            dpMatrix[i][j] = i;
          } else if (str1[i-1] === str2[j-1]) {
            dpMatrix[i][j] = dpMatrix[i-1][j-1];
          } else {
            let insertCost = dpMatrix[i][j-1],
                removeCost = dpMatrix[i-1][j],
                replaceCost = dpMatrix[i-1][j-1];

            dpMatrix[i][j] = 1 + Math.min(insertCost, removeCost, replaceCost)
          }
        }
      }
      return dpMatrix[length1][length2];
    }

    20장 비트 조작

  • 고성능 서버 사이드 코드를 구현하길 원한다면 비트 조작도 알아야 함
  • 자바스크립트의 비트 연산자
  • &는 AND, |는 OR, ~는 NOT, ^는 XOR에 해당하고 왼쪽 이동은 <<로, 오른쪽 이동은 >>로, >>>는 오른쪽 이동 후에 0으로 채운다는 뜻이다
  • AND 연산자(&)는 두 개의 비트가 모두 1일때 참이다
    a = 1100, b = 1010일 때, a & b = 1000이다
  • OR 연산자(|)는 두 개의 비트 중 하나만 1이어도 참이다
    a = 1100, b = 1010일 때, a & b = 1110이다
  • XOR 연산자(^)는 비트 중 하나가 1일 때만 참이 된다
    a = 1100, b = 1010일 때, a & b = 0110이다
  • NOT 연산자는 모든 비트를 뒤집는다
    a = 1100일 때 NOT a = 0011이다
  • 왼쪽 이동 연산자(<<)는 모든 비트가 왼쪽으로 이동되고 왼쪽 끝 범위를 벗어나는 비트는 버려진다
    9(1001) << 1 = 10010(2) = 18, 9 << 2 = 100100(2) = 36
  • 위 예와 같이 왼쪽 이동 연산자는 해당 항목을 두 배로 증가시킨다 (이진 연산 체계이기 때문) 하지만 왼쪽 이동으로 비트가 넘친다면 버려지므로 값이 작아질 수 있다
  • 오른쪽 이동 연산자(>>)는 모든 비트가 오른쪽으로 이동되고 오른쪽 끝 범위를 벗어나면 버려진다
    9(1001) >> 1 = 100(2) = 4
  • 오른쪽 이동 연산자는 항목을 2로 나눈 값이 된다
  • 비트 연산자를 사용해 연산해보기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    // 이진수를 더하기는  두 수를 더한 다음 10을 초과하면 1을 다음 수로 올린다 (carry)
    const BitwiseAdd = (a, b) => {
      while (b !== 0) {
        let carry = (a & b);
        a = a ^ b;
        b = carray << 1;
      }
      return a;
    }

    // 이진수에서 음의 이진수로부터 양의 이진수를 빼려면 모든 비트를 뒤집은 다음 1을 더하면 된다
    const BitwiseNegate = a => {
      return BitwiseAdd(~a, 1);
    }

    // 빼기는 음수를 더하는 것이기 때문에 음의 이진수를 구하고 더한다
    const BitwiseSubtract = (a, b) => {
      return BitwiseAdd(a, BitwiseNegate(b))
    }

    // 곱셈은 두 수를 곱하고 10이 넘어가는 수는 다음 자릿수로 올리고 다음 자릿수로 이동해 해당 자릿수의 수를 곱한다
    const BitwiseMultiply = (a, b) => {
      let m = 1, c = 0;
      if (a < 0) {
        a = BitwiseNegate(a);
        b = BitwiseNegate(b);
      }

      while (a >= m && b) {
        if (a & m) 
          c = BitwiseAdd(b, c);
        b = b << 1;
        m = m << 1;
      }
      return c;
    }

    // a나누기 b는 b를 여러번 빼는 것이라고 생각하면 쉽다
    const BitwiseDividePositive = (a, b) => {
      let c = 0;
      if (b !== 0) {
        while (a >= b) {
          a = BitwiseSubtract(a, b);
          c++
        }
      }
      return c;
    }

    // 하지만 음의 정수를 나누기한다면 while값이 무한히 반복될 것이기 때문에 부호를 저장할 값이 필요하다
    const BitwiseDivide = (a, b) => {
      let c = 0, isNegative = 0;

      if (a < 0) {
        a = BitwiseNegate(a);
        isNegative = !isNegative;
      }

      if (b < 0) {
        b = BitwiseNegate(b);
        isNegative = !isNegative;
      }

      if (b !== 0) {
        while (a >= b) {
          a = bitwiseSubstract(a, b);
          c++;
        }
      }

      if (isNegative) {
        c = BitwiseNegate(c);
      }
      return c;
    }
  • 비트연산자는 Math의 기본 함수보다 빠르다
  • 최근의 자바스크립트는 Node.js를 활용해 서버 측 프로그래밍에 진입하고 있기 때문에 비트 연산자는 효율적인 코드를 만드는데 도움이 될 것이다