Dynamic Programming

1. 피보나치 Memoization

(1) Before Memoization

const fib = (n) => {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(50));

• fib(50)의 경우, 2^n으로 인해 1.12e + 15 번의 연산이 필요

(2) After Memoization

const fib = (n, memo = {}) => {
  if (n in memo) return memo[n];
  if (n <= 2) return 1;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

console.log(fib(50));

• 메모이제이션 후, 빅오는 O(n)

2. GridTraveler memoization

2D grid에서 좌측 꼭대기 코너에서 우측 아래 코너까지 가는 경우의 수

고정된 경우의 수는 (1,1) = 1 , (0,N) || (N,0) = 0 이다.

(1) Before Memoization

const grdiTraveler = (m, n) => {
  if (m === 1 && n === 1) return 1;
  if (m === 0 || n === 0) return 0;
  return grdiTraveler(m - 1, n) + grdiTraveler(m, n - 1);
}

(2) After Memoization

const grdiTraveler = (m, n, memo = {}) => {
  const key = m + "," + n;
  
  if (key in memo) return memo[key];
  if (m === 1 && n === 1) return 1;
  if (m === 0 || n === 0) return 0;

  memo[key] = grdiTraveler(m - 1, n, memo) + grdiTraveler(m, n - 1, memo);
  return memo[key];
};

(3) Memoization Tip

• 트리 구조로 시각화
• 재귀함수를 이용하여 tree 구조를 생성
• 트리 구조 속 공통 사항 혹은 규칙을 발견 후 리턴
• memo 오브젝트를 생성 후 value를 저장

3. Cansum memoization

규칙 - tree 구조 상 leaf에 0이 포함된다면 True 리턴

(1) Before Memoization

const canSum = (targetSum, numbers) => {
  if (targetSum === 0) return true;
  if (targetSum < 0) return false;
  for (let num of numbers) {
    if (canSum(remainder, numbers) === true) {
      return true;
    }
  }
  return false;
};
}

brute force 시 시간복잡도는 O(n^m)이다.

(2) After Memoization
numbers는 고정된 값이므로 true를 반환하는 targetSum을 메모에 저장

const canSum = (targetSum, numbers, memo = {}) => {
  if (targetSum in memo) return memo[targetSum];
  if (targetSum === 0) return true;
  if (targetSum < 0) return false;
  for (let num of numbers) {
    const remainder = targetSum - num;
    if (canSum(remainder, numbers, memo) === true) {
      memo[targetSum] = true;
      return true;
    }
  }
  memo[targetSum] = false;
  return false;
};

memoized후 시간복잡도는 O(m*n)이다.

4. Howsum memoization

canSum과 유사하게 leaf의 값이 0일 경우 empty array반환, < 0일 경우 null 반환 후 역으로 뺀 값(num)을 push한다.

(1) Before Memoization

const howSum = (targetSum, numbers) => {
  if (targetSum === 0) return [];
  if (targetSum < 0) return null;
  for (let num of numbers) {
    const remainder = targetSum - num;
    const remainderResult = howSum(remainder, numbers);
    if (remainderResult !== null) {
      return [...remainderResult, num];
    }
  }
  return null;
};

(2) After Memoization

const howSum = (targetSum, numbers, memo = {}) => {
  if (targetSum in memo) return memo[targetSum];
  if (targetSum === 0) return [];
  if (targetSum < 0) return null;
  for (let num of numbers) {
    const remainder = targetSum - num;
    const remainderResult = howSum(remainder, numbers, memo);
    if (remainderResult !== null) {
      memo[targetSum] = [...remainderResult, num];
      return memo[targetSum];
    }
  }
  memo[targetSum] = null;
  return null;
};

5. Bestsum memoization

[2,3,5] 배열로 8을 만들 수 있는 경우의 수 중 arr length가 가장 적은 경우 찾기

(1) Before Memoization

const bestSum = (targetSum, numbers) => {
  if (targetSum === 0) return [];
  if (targetSum < 0) return null;

  let shortestCombination = null;

  for (let num of numbers) {
    const remainder = targetSum - num;
    const remainderCombination = bestSum(remainder, numbers)
    if (remainderCombination !== null) {
      const combination = [...remainderCombination, num];
      if (shortestCombination === null || combination.length < shortestCombination.length) {
        shortestCombination = combination;
      }
    }
  }
  return shortestCombination;
}

(2) After Memoization

const bestSum = (targetSum, numbers, memo = {}) => {
  if (targetSum in memo) return memo[targetSum];
  if (targetSum === 0) return [];
  if (targetSum < 0) return null;

  let shortestCombination = null;

  for (let num of numbers) {
    const remainder = targetSum - num;
    const remainderCombination = bestSum(remainder, numbers, memo)
    if (remainderCombination !== null) {
      const combination = [...remainderCombination, num];
      if (shortestCombination === null || combination.length < shortestCombination.length) {
        shortestCombination = combination;
      }
    }
  }
  memo[targetSum] = shortestCombination;
  return shortestCombination;
}

console.log(bestSum(100, [2, 4, 10, 50, 30]))

6. canConstruct memoization

empty string일 경우 true
ex) canConstruct(abcdef, [ab, abc, cd, def, abcd])

(1) Before Memoization

const canConstruct = (target, wordBank) => {
  if (target === '') {
    return true;
  }

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const subfix = target.slice(word.length);
      if (canConstruct(subfix, wordBank) === true) {
        return true;
      }
    }
  }

  return false;
};


console.log(canConstruct('abcdef', ['ab', 'abc', 'cd', 'def', 'abcd']));

const subfix = target.slice(word.length);

subfix를 복사하고 loop과정에서 복잡도 증가하므로, memoization 사용

(2) After Memoization

const canConstruct = (target, wordBank, memo = {}) => {
  if (target in memo) return memo[target];
  if (target === '') return true;

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const subfix = target.slice(word.length);
      if (canConstruct(subfix, wordBank, memo) === true) {
        memo[target] = true;
        return true;
      }
    }
  }

  memo[target] = false;
  return false;
};


console.log(canConstruct('eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeef', [
  'e', 'eee', 'eeee', 'eeeee', 'eeeeee'
]));

7. countConstruct memoization

두번째 인자의 배열의 요소를 통해서 만들 수 있는 첫번째 문자열 가지 수

(1) Before Memoization

const countConstruct = (target, wordBank) => {
  // target이 empty string일시 count 적립
  if (target === '') return 1;

  let totalCount = 0;

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const numWaysForRest = countConstruct(target.slice(word.length), wordBank);
      totalCount += numWaysForRest;
    }
  }

  return totalCount;
};


console.log(countConstruct('perple', [
  'perp', 'p', 'ur', 'le', 'perpl'
]));

(2) After Memoization

const countConstruct = (target, wordBank, memo = {}) => {

  if (target in memo) return memo[target];
  // target이 empty string일시 count 적립
  if (target === '') return 1;

  let totalCount = 0;

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const numWaysForRest = countConstruct(target.slice(word.length), wordBank, memo);
      totalCount += numWaysForRest;
    }
  }

  memo[target] = totalCount;
  return totalCount;
};


console.log(countConstruct('perple', [
  'perp', 'p', 'ur', 'le', 'perpl'
]));

8. allConstruct memoization

두번째 인자의 배열의 요소를 통해서 만들 수 있는 첫번째 문자열 의 2차원 배열

Tip - empty string시 빈 2차원 배열을 만들고, 트리구조를 올라가면서 요소 삽입

(1) Before Memoization

const allConstruct = (target, wordBank) => {
  if (target === '') return [[]];

  const result = [];

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const subfix = target.slice(word.length);
      const subfixWays = allConstruct(subfix, wordBank);
      const targetWays = subfixWays.map(way => [word, ...way])
      result.push(...targetWays);
    }
  }
  return result;
};

console.log(allConstruct('perple', [
  'perp', 'p', 'er', 'le', 'perpl', 'ple'
]));

(2) After Memoization

const allConstruct = (target, wordBank, memo = {}) => {
  if (target in memo) return memo[target];
  if (target === '') return [[]];

  const result = [];

  for (let word of wordBank) {
    if (target.indexOf(word) === 0) {
      const subfix = target.slice(word.length);
      const subfixWays = allConstruct(subfix, wordBank, memo);
      const targetWays = subfixWays.map(way => [word, ...way]);
      result.push(...targetWays);
    }
  }

  memo[target] = result;
  return result;
};

console.log(allConstruct('aaaaaaaaaaaaaaaaf', [
  'a', 'aaa', 'aaaa', 'aaaaa', 'aaaaaa', 'aaaaaaaf'
]));