[Daily Coding 6]indexOf,lastIndexOf, findIndex, find/DP/재귀/join,split/GCD,LCM/식 내부에서 삼항 연산자 사용하기/이중반복문 대신 함수 나누기

1.indexOf(), lastIndexOf(), findIndex(), find()

공통점: 최초 값/인덱스 반환, 찾는 값이 없으면 -1 반환

문자열/배열.indexOf(값) -> 두 번째 매개변수로 탐색을 시작할 인덱스 지정 가능
문자열/배열.lastIndexOf(값) -> 두 번째 매개변수로 탐색을 시작할 인덱스 지정 가능
배열.findIndex(콜백)
배열.find(콜백)

2.동적 계획법(DP, Dynamic Programming)

1) dynamic with memoization: 이미 해결한 문제는 풀지 않음

// memoization -> Top-down, 재귀 활용, 계산된 모든 수 배열 저장
// O(N)
let tiling = function (n) {
  const memo = [0, 1, 2];
  const aux = (size) => {
    if (memo[size] !== undefined) return memo[size];
    if (size <= 2) return memo[n];
    memo[size] = aux(size - 1) + aux(size - 2);
    return memo[size];
  };
  return aux(n);
};

2) dynamic with tabulation: 데이터를 테이블에 정리하면서 bottom-up 방식으로 해결하는 기법

// tabulation -> Bottom-up, 반복문 활용, 계산된 모든 수 배열에 저장
// O(N)
let tiling = function (n) {
  const memo = [0, 1, 2];
  if (n <= 2) return memo[n];
  for (let size = 3; size <= n; size++) {
    memo[size] = memo[size - 1] + memo[size - 2];
  }
  return memo[n];
};

3) dynamic with sliding window: 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘. 교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신.

// O(N)
// 반복문 활용, 직전 2개의 수만 저장
let tiling = function (n) {
  let fst = 1,
    snd = 2;
  if (n <= 2) return n;
  for (let size = 3; size <= n; size++) {
    const next = fst + snd;
    fst = snd;
    snd = next;
  }
  return snd;
};

3.재귀(선언형 프로그래밍)

// Q.수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴해야 합니다.
function take(num, arr) {}

// 입출력 예시
let output = take(2, [1, -2, 1, 3]);
console.log(output); // --> [1, -2]

output = take(5, [1, -2, 1, 3]);
console.log(output); // --> [1, -2, 1, 3]

1) 작성 순서

-재귀 호출문 작성
주의1: 호출문의 재귀 함수 인자는 선언문의 인자보다 더 작아야 함
주의2: 출력값 타입 고려

// array로 출력
[arr[0]].concat(take(num - 1, arr.slice(1)))

-종료 조건
num이 0일 경우 -> return []
arr가 빈 배열일 경우 -> return []

-함수 작성

if(num === 0 || arr.length === 0) {return []};
return [arr[0]].concat(take(num - 1, arr.slice(1)))

2) 재귀함수 작성 시 필수 요소

-출력값 타입으로 반환하는 리턴문
-선언문의 인자보다 작은 인자를 가진 재귀 호출문

위의 2가지가 같이 있는 경우 -> 종료 조건에 도달 전까지 항상 재귀를 호출해야 하는 경우
위의 2가지가 따로 있는 경우 -> 조건에 따라 재귀 호출 여부가 갈리는 경우

4.join, split 기본값

join() -> 콤마

const elements = ['Fire', 'Air', 'Water'];
console.log(elements.join());// "Fire,Air,Water"

split() -> 나눠지지 않음

const str = "A happy day!";
console.log(str.split());// ["A happy day!"]

5.최대공약수, 최소공배수

1) 최대공약수(GCD, Greatest Common Divisor)

: 공통된 약수 중 가장 큰 수, 두 수 중 하나가 0이라면 0이 아닌 수

// 유클리드 호제법: a > b일 때, a, b의 최대공약수와 b, (a % b)의 최대공약수가 같다는 성질 이용
// 두번째 인수 (a % b)가 0이 될 때까지 재귀 호출, 0이 되면 그 때의 b가 최대공약수
let gcd = (a, b) => (a % b) ? gcd(b, a % b) : b

참고 동영상: https://www.youtube.com/watch?v=J5Yl2kHPAY4&ab_channel=%EC%88%98%EC%95%85%EC%A4%91%EB%8F%85

2) 최소공배수(LCM, Least Common Multiple)

: 공통된 배수 중 가장 작은 수, 두 수 중 하나가 0이라면 0
최대공약수를 구한 후 L = A × B ÷ G 이용

3) 최대공약수와 최소공배수의 관계

-> L = A × B ÷ G

-증명
A = G × a
B = G × b
L = G × a × b

A × B = (G × a) × (G × b) = G × (G × a × b) = G × L
즉, L = A × B ÷ G

6.식 내부에서 삼항 연산자 사용하기

Q. 2차원 좌표 평면에 변이 축과 평행한 직사각형이 있습니다. 직사각형 네 꼭짓점의 좌표 [[x1, y1], [x2, y2], [x3, y3], [x4, y4]]가 담겨있는 배열 dots가 매개변수로 주어질 때, 직사각형의 넓이를 return 하도록 solution 함수를 완성해보세요.

// 입출력 예시
function solution([[1, 1], [2, 1], [2, 2], [1, 2]])// 1
function solution([[-1, -1], [1, 1], [1, -1], [-1, 1]])// 4

// A.
solution = ([[a,b],[c,d],[e,f]]) => Math.abs(a-(a==c?e:c))*Math.abs(b-(b==d?f:d))

// 3개의 배열만으로 계산 가능
// 삼항 연산자를 사용하여 식 내부에서 원하는 값으로 계산

7.이중반복문 대신 함수 나누기

//Q.두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다.

// 입출력 예시
let base = [1, 2, 3, 4, 5];
let sample = [1, 3];
let output = isSubsetOf(base, sample);
console.log(output); // --> true

// 내 코드
const isSubsetOf = function (base, sample) {
  // 배열 정렬
  // sample을 돌면서
  // base의 요소와 일치하면 index 업데이트, include 변환, break
  // 아니면 return false
  base.sort((a, b) => a - b)
  sample.sort((a, b) => a - b)
  let index = 0;
  for(let i = 0; i < sample.length; i++) {
    let isInclude = false;
    for(let j = index; j < base.length; j++) {
      if(sample[i] === base[j]) {
        index = j + 1;
        isInclude = true;
        break;
      }
    }
    if(!isInclude) {return false}
  }
  return true;
};

// 레퍼런스 코드
const isSubsetOf = function (base, sample) {
  // 각 배열을 정렬: O(N * logN), O(M * logM)
  // N >= M 이므로, O(N * logN)
  base.sort((a, b) => a - b);
  sample.sort((a, b) => a - b);

  const findItemInSortedArr = (item, arr, from) => {
    for (let i = from; i < arr.length; i++) {
      if (item === arr[i]) return i;
      else if (item < arr[i]) return -1;
    }
    return -1;
  };

  let baseIdx = 0;
  for (let i = 0; i < sample.length; i++) {
    baseIdx = findItemInSortedArr(sample[i], base, baseIdx);
    if (baseIdx === -1) return false;
  }
  return true;
};