Section3 Daily Coding

largestProductOfThree

문제

정수를 요소로 갖는 배열을 입력받아 3개의 요소를 곱해 나올 수 있는 최대값을 리턴해야 합니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 임의의 배열

출력

• number 타입을 리턴해야 합니다.

주의사항

• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
• 배열의 요소는 음수와 0을 포함하는 정수입니다.
• 배열의 길이는 3 이상입니다.

입출력 예시

1
2
3
4
5
let output = largestProductOfThree([2, 1, 3, 7]);
console.log(output); // --> 42 (= 2 * 3 * 7)

output = largestProductOfThree([-1, 2, -5, 7]);
console.log(output); // --> 35 (= -1 * -5 * 7)

• 내가 작성한 코드: (조합을 이용함 reference 코드와 비교해서 코드의 길이도 시간 복잡도 측면에서 비효율적)

const largestProductOfThree = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  const newArr=arr.slice();
  const resArr=getCombinations(newArr,3);
  let maxNum=Number.MIN_SAFE_INTEGER;
  for(let x of resArr){
    let num=1;
    for(let y of x){
      num*=y;
    }
    maxNum=Math.max(maxNum,num);
  }
  return maxNum;
};
const getCombinations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 
    // n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return

    arr.forEach((fixed, index, origin) => {
      const rest = origin.slice(index + 1); 
      // 해당하는 fixed를 제외한 나머지 뒤
      const combinations = getCombinations(rest, selectNumber - 1); 
      // 나머지에 대해서 조합을 구한다.
      const attached = combinations.map((el) => [fixed, ...el]); 
      //  돌아온 조합에 떼 놓은(fixed) 값 붙이기
      results.push(...attached); 
      // 배열 spread syntax 로 모두다 push
    });

    return results; // 결과 담긴 results return
}

• refernece code: (간단명료)

const largestProductOfThree = function (arr) {
  const sorted = arr.slice().sort((a, b) => a - b);
  const len = arr.length;
  const candi1 = sorted[len - 1] * sorted[len - 2] * sorted[len - 3];
  const candi2 = sorted[len - 1] * sorted[0] * sorted[1];
  return Math.max(candi1, candi2);
};

---

fibonacci

문제

아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴해야 합니다.

• 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입력

인자 1 : n

• number 타입의 n (n은 0 이상의 정수)

출력

• number 타입을 리턴해야합니다.

주의사항

• 재귀함수를 이용해 구현해야 합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 함수 fibonacci가 반드시 재귀함수일 필요는 없습니다.

입출력 예시

1
2
3
4
5
6
7
8
9
10
11
let output = fibonacci(0);
console.log(output); // --> 0

output = fibonacci(1);
console.log(output); // --> 1

output = fibonacci(5);
console.log(output); // --> 5

output = fibonacci(9);
console.log(output); // --> 34

• memorization:

메모이제이션은 비싼 함수 호출(expensive function calls) 결과를 저장하고 동일한 입력이 다시 제공될 때 캐시된 결과를 반환하여 응용 프로그램의 속도를 높이는 최적화 기술입니다.

• 메모이제이션은 캐싱을 사용하여 빠르고, 쉽게 엑세스할 수 있도록 함수 호출의 결과를 저장한다 

JS에서 메모이제이션의 작동

두 가지 개념으로 구성된다 

• 클로저(Closure)
• 고차함수(Hiher Order Functions)(함수에서 함수반환)

function fibonacci(n) {
  // TODO: 여기에 코드를 작성합니다.
  const memo = [0, 1]; 
  const fibo = (num) => {
    if (memo[num] !== undefined) {
      return memo[num];
    } else {
      memo[num] = fibo(num - 1) + fibo(num - 2);
    }
    return memo[num];
  };
  return fibo(n);
}

즉 위 코드를 보면, fibo라는 함수 밖에 memo를 선언함으써 클로저를 활용해 메모이제이션을 활용했음을 알 수 있다!

• reference code: 

// naive solution: O(2^N)
// let fibonacci = function (n) {
//   if (n <= 1) return n;
//   return fibonacci(n - 1) + fibonacci(n - 2);
// };

// dynamic with meoization: O(N)
// 이미 해결한 문제의 정답을 따로 기록해두고,
// 다시 해결하지 않는 기법
// fibo(10)
// = fibo(9) + fibo(8)
// = fibo(8) + fibo(7) + fibo(7) + fibo(6)
// 여기까지만 보아도 동일한 문제가 중복으로 계산되는 것을 알 수 있다.
let fibonacci = function (n) {
  const memo = [0, 1];
  const aux = (n) => {
    // 이미 해결한 적이 있으면, 메모해둔 정답을 리턴한다.
    if (memo[n] !== undefined) return memo[n];
    // 새롭게 풀어야하는 경우, 문제를 풀고 메모해둔다.
    memo[n] = aux(n - 1) + aux(n - 2);
    return memo[n];
  };
  return aux(n);
};

---

bubbleSort

문제

정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다.

버블 정렬 알고리즘은 아래와 같습니다.

1. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
2. 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
3. 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교)
4. 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다.
5. 1~3의 과정을 첫 요소부터 다시 반복합니다.
6. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 두 번째로 밀려납니다.
7. 1~3의 과정을 총 n번(배열의 크기) 반복합니다.

이 모습이 마치 '거품이 밀려 올라가는 것과 같은 모습'과 같아서 bubble sort라고 부릅니다.

입력

인자 1 : arr

• number 타입을 요소로 갖는 배열
• arr[i]는 정수
• arr[i]의 길이는 1,000 이하

출력

• number 타입을 요소로 갖는 배열을 리턴해야 합니다.
• 배열의 요소는 오름차순으로 정렬되어야 합니다.
• arr[i] <= arr[j] (i < j)

주의사항

• 위에서 설명한 알고리즘을 구현해야 합니다.
• arr.sort 사용은 금지됩니다.
• 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.

입출력 예시

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

Advanced

• 아래의 힌트를 바탕으로 (최선의 경우) 수행 시간을 단축할 수 있도록 코드를 수정해보세요.
• 위에서 설명된 알고리즘 1~3의 과정 중 어떤 요소도 위치가 바뀌지 않은 경우, 배열이 정렬된 상태라는 것을 알 수 있습니다.
• 내가 작성한 코드: 

const bubbleSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  const len=arr.length;

  let newArr=arr.slice();
  for(let i=0;i<len-1;i++){
  //교체가 발생하지 않는다면, 이미 정렬된 상태란 의미 boolean으로 체크한다!
    let alreadySorted=true;
    for(let j=0;j<len-i-1;j++){
      if(newArr[j]>newArr[j+1]){
        let temp=newArr[j]; 
        newArr[j]=newArr[j+1]; 
        newArr[j+1]=temp;
        alreadySorte=false;
      }
    }
    //만약 true이면 이미 정렬된 상태 반복문 탈출
    if(alreadySorted)break;
  }
  return newArr;
};

• reference code: 

const swap = function (idx1, idx2, arr) {
  // 두 변수를 바꾸는 방법

  // 1) 임시 변수를 활용한 방법
  // let temp = arr[idx1];
  // arr[idx1] = arr[idx2];
  // arr[idx2] = temp;

  // 2) Destructuring assignment를 활용한 방법
  // arr이 reference type이라 가능
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];

  // 3) XOR 연산을 활용한 방법
  // arr이 reference type이라 가능
  // arr[idx1] ^= arr[idx2];
  // arr[idx2] ^= arr[idx1];
  // arr[idx1] ^= arr[idx2];
};

// naive solution
// let bubbleSort = function (arr) {
//   let N = arr.length;

//   for (let i = 0; i < N - 1; i++) {
//     // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
//     // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.
//     for (let j = 0; j < N - 1 - i; j++) {
//       if (arr[j] > arr[j + 1]) {
//         swap(j, j + 1, arr);
//       }
//     }
//   }

//   return arr;
// };

// optimized solution
let bubbleSort = function (arr) {
  let N = arr.length;

  for (let i = 0; i < N; i++) {
    // swap 횟수를 기록한다.
    // 어떤 요소도 swap되지 않은 경우, 배열은 정렬된 상태이다.
    let swaps = 0;

    // 매 반복(iteration)마다 i번째로 큰 수가 마지막에서 i번째 위치하게 된다.
    // 이미 정렬된 요소는 고려할 필요가 없으므로, 'j < N - 1 - i'만 비교하면 된다.
    for (let j = 0; j < N - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swaps++;
        swap(j, j + 1, arr);
      }
    }

    if (swaps === 0) {
      break;
    }
  }

  return arr;
};

---

isSubsetOf

문제

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

입력

인자 1 : base

• number 타입을 요소로 갖는 임의의 배열
• base.length는 100 이하

인자 2 : sample

• number 타입을 요소로 갖는 임의의 배열
• sample.length는 100 이하

출력

• boolean 타입을 리턴해야 합니다.

주의사항

• base, sample 내에 중복되는 요소는 없다고 가정합니다.

입출력 예시

1
2
3
4
5
6
7
8
9
10
11
12
13
let base = [1, 2, 3, 4, 5];
let sample = [1, 3];
let output = isSubsetOf(base, sample);
console.log(output); // --> true

sample = [6, 7];
output = isSubsetOf(base, sample);
console.log(output); // --> false

base = [10, 99, 123, 7];
sample = [11, 100, 99, 123];
output = isSubsetOf(base, sample);
console.log(output); // --> false

Advanced

• 시간 복잡도를 개선하여, Advanced 테스트 케이스(base, sample의 길이가 70,000 이상)를 통과해 보세요.

const isSubsetOf = function (base, sample) {
  // TODO: 여기에 코드를 작성합니다.
  base.sort((a,b)=>a-b);
  sample.sort((a,b)=>a-b);


  const subSetorNot=(val,arr,start)=>{
    for(let i=start;i<arr.length;i++){
      if(val===arr[i]) return i;
      //이미 정렬된 배열인데 동일한 것은 없고 base에 더 큰 값만 있다는 것은
      //부분 집합이 될 수 없음을 의미함!
      else if(val<arr[i]) return -1;
    }
    //default로 -1을 return 이미 부분 집합이면 위에서 처리되기 때문에!
    return -1; 
  }
  //sample 배열의 모든 el을 확인해야 하기 때문에 sample length로 돌린다.\
  let startIdx=0; 
  for(let i=0;i<sample.length;i++){
    startIdx=subSetorNot(sample[i],base,startIdx);
    //만약에 startIdx이 -1이면 이미 부분 집합이 아님을 의미함!
    if(startIdx===-1)return false;
  }
  return true;
};

• 위 코드의 경우 N>=M (N=base, M=sample)이기 때문에 시간 복잡도는 (N * logN)이다 (logN의 계산법이 궁금하면 이링크를 참고)
• 일일이 비교하면서 진행하는 코드의 경우 (N^2)이기 때문에 시간 초과의 우려가 존재한다.

---

tiling

문제

세로 길이 2, 가로 길이 n인 2 x n 보드가 있습니다. 2 x 1 크기의 타일을 가지고 이 보드를 채우는 모든 경우의 수를 리턴해야 합니다.

입력

인자 1 : n

• number 타입의 1 이상의 자연수

출력

• number 타입을 리턴해야 합니다.

주의사항

• 타일을 가로, 세로 어느 방향으로 놓아도 상관없습니다. (입출력 예시 참고)

입출력 예시

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
let output = tiling(2);
console.log(output); // --> 2

output = tiling(4);
console.log(output); // --> 5
/* 
2 x 4 보드에 타일을 놓는 방법은 5가지
각 타일을 a, b, c, d로 구분

2 | a b c d
1 | a b c d 
------------

2 | a a c c
1 | b b d d 
------------

• 작성한 코드: 

let tiling = function (n) {
  // TODO: 여기에 코드를 작성합니다.
  //dp 사용-JS에선 DP를 적용하기 위해서는 클로저를 사용해야 한다
  //1:1가지, n=2 두 가지, n:3 3가지, n:4 
  const arr=[0,1,2];
  const dp=(num)=>{
    for(let i=3;i<=num;i++){
      arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[num];
  }
  
  return dp(n);
};

• 위에 작성된 주석을 살펴보면, n이 1일 때 나올 수 있는 경우의 수는 1가지, 2일 때는 2가지, 3일 때는 3가지 4일 때는 5가지임을 확인할 수 있다. 이는 직접 그리면서도 확인할 수 있지만, 그리면서 패턴을 찾아보면, 결국, 앞선 두 패턴의 결합이 그 다음의 패턴을 결정한다고 생각하면 된다. 따라서, 해당 문제를 풀기 위해서는  DP를 적용해서 처리하면 간단하게 해결할 수 있다. DP가 무엇인지 모른다면 해당 링크 참고
• 결국, 본 문제는 DP를 적용해서 해결했기 때문에 시간 복잡도는 O(N)으로 처리 된다! 

Reference code:

// naive solution: O(2^N)
// 2 x 4 보드에 타일을 놓는 방법은 5가지다.
// 각 타일을 a, b, c, d로 구분한다.
// 아직 타일이 놓이지 않는 부분은 -로 표기한다.
// 타일을 놓는 방법은 가장 왼쪽부터 세로로 놓거나 가로로 놓는 것으로 시작한다.
// 1) 세로로 놓는 법
//   2 | a - - -
//   1 | a - - -
//   ------------
// 2) 가로로 놓는 법
// 타일을 가로로 놓게 되면, 그 바로 아래에는 가로로 놓을 수 밖에 없다.
//   2 | a a - -
//   1 | b b - -
//   ------------
// 이때, 타일이 아직 놓이지 않은 부분은 사실 크기만 다를뿐 같은 종류의 문제라는 것을 알 수 있다.
// 즉, 2 x 4 보드에 타일을 놓는 방법은 아래 두 가지 방법을 더한 결과와 같다.
//  1) 2 x 3 보드에 타일을 놓는 방법
//  2) 2 x 2 보드에 타일을 놓는 방법
// 따라서 2 x n 타일 문제는 아래와 같이 재귀적으로 정의할 수 있다.
// 주의: 재귀적 정의에는 항상 기초(base), 즉 더 이상 재귀적으로 정의할 수 없는(쪼갤 수 없는) 문제를 별도로 정의해야 한다.
// let tiling = function (n) {
//   if (n <= 2) return n;
//   return tiling(n - 1) + tiling(n - 2);
// };

// dynamic with memoization: O(N)
let tiling = function (n) {
  // 인덱스를 직관적으로 관리하기 위해
  // 앞 부분을 의미없는 데이터(dummy)로 채운다.
  const memo = [0, 1, 2];

  // 재귀를 위한 보조 함수(auxiliary function)을 선언)
  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);
};

// dynamic with tabulation: O(N)
// tabulation은 데이터를 테이블에 정리하면서 bottom-up 방식으로 해결하는 기법을 말합니다.
// 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];
// };

// dynamic with slicing window: O(N)
// slicing window은 필요한 최소한의 데이터만을 활용하는 것을 말합니다.
// 크기 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;
//     // 다음 문제로 넘어가기 위해 필요한 2개의 데이터의 순서를 정리한다.
//     fst = snd;
//     snd = next;
//   }
//   return snd;
// };

 

 

---

출처: 

https://www.devh.kr/2020/Understanding-Memoization-In-JavaScript/

[번역] 자바스크립트 메모이제이션 | dev.h