[TIL] 211017

Lee SyongΒ·2021λ…„ 10μ›” 17일
JavaScriptTILμ•Œκ³ λ¦¬μ¦˜μžλ£Œ ꡬ쑰
0

TIL

λͺ©λ‘ 보기
60/204
post-thumbnail

πŸ“ 였늘 ν•œ 것

  1. μ±… 'λˆ„κ΅¬λ‚˜ 자료 ꡬ쑰와 μ•Œκ³ λ¦¬μ¦˜' 1 ~ 8μž₯ 볡슡

  2. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 문제 풀이


πŸ“– ν•™μŠ΅ 자료

  1. [TIL] 211009, [TIL] 211010, [TIL] 211013, [TIL] 211014, [TIL] 211015, [TIL] 211016

  2. μ±… 'λˆ„κ΅¬λ‚˜ 자료 ꡬ쑰와 μ•Œκ³ λ¦¬μ¦˜' 1 ~ 8μž₯


πŸ“š 배운 것

1. 볡슡

9μž₯λΆ€ν„° μ–΄λ €μ›Œμ§€λŠ” κ±° κ°™μ•„μ„œ(사싀상 8μž₯λΆ€ν„°...) μ΄μ „κΉŒμ§€ 배운 λ‚΄μš© λ³΅μŠ΅ν•¨
1 ~ 8μž₯의 λͺ¨λ“  μ½”λ“œλ₯Ό λ‹€μ‹œ μž‘μ„±ν•΄λ³Έ ν›„ λΈ”λ‘œκ·Έμ— 정리해둔 필기듀을 λ‹€μ‹œ λ΄„

'use strict';

/* 2μž₯. μ•Œκ³ λ¦¬μ¦˜μ΄ μ€‘μš”ν•œ κΉŒλ‹­ */

// μ •λ ¬λœ λ°°μ—΄ μ„ ν˜• 검색
{
  function linearSearch (arr, value) {
    for(let i = 0; i < arr.length; i++) {
      if (arr[i] === value) {
        return `${value}은(λŠ”) 인덱슀 ${i}에 μžˆλ‹€`;
      }
    }
    return `λ°°μ—΄ μ•ˆμ— 찾고자 ν•˜λŠ” ${value}이(κ°€) μ—†λ‹€`;
  }

  const arr1 = [2, 4, 6, 8];
  console.log(linearSearch(arr1, 6)); // 6은(λŠ”) 인덱슀 2에 μžˆλ‹€
}

// μ •λ ¬λœ λ°°μ—΄ 이진 검색
{
  function binarySearch (arr, value) {
    let upperIndex = arr.length - 1;
    let lowerIndex = 0;

    while (lowerIndex <= upperIndex) { // πŸ’‘ 이 쑰건식이 포인트! μ²˜μŒμ—” low < up μ΄μ—ˆλ‹€κ°€ 루프λ₯Ό λŒλ©΄μ„œ κ²°κ΅­ low = up이 λœλ‹€
      let midIndex = (function () {
        return Math.floor(upperIndex + lowerIndex);
      })();

      if (value < arr[midIndex]) {
        upperIndex = midIndex - 1;
      } else if (value > arr[midIndex]) {
        lowerIndex = midIndex + 1;
      } else {
        return `${value}은(λŠ”) 인덱슀 ${midIndex}에 μžˆλ‹€`;
      }
    }

    return `λ°°μ—΄ μ•ˆμ— 찾고자 ν•˜λŠ” ${value}이(κ°€) μ—†λ‹€`;
  }

  const arr1 = [1, 2, 3, 4, 5, 6, 7];
  const arr2 = [1, 2, 3, 4, 5, 6];
  console.log(binarySearch(arr1, 3)); // 3은(λŠ”) 인덱슀 2에 μžˆλ‹€
  console.log(binarySearch(arr1, 0)); // λ°°μ—΄ μ•ˆμ— 찾고자 ν•˜λŠ” 0이(κ°€) μ—†λ‹€
}



/* 3μž₯. λΉ… 였 ν‘œκΈ°λ²• */

// 주어진 μˆ˜κ°€ μ†Œμˆ˜μΈμ§€ νŒλ³„ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ β†’ O(N)
{
  function isPrimeNumber (num) {
    for (let i = 2; i < num; i++) {
      if (num % i === 0) {
        return false;
      }
    }
    return true;
  }

  console.log(isPrimeNumber(11)); // true
  console.log(isPrimeNumber(10)); // false
}



/* 4μž₯. λΉ… 였둜 μ½”λ“œ 속도 올리기 */

// 버블 μ •λ ¬ μ½”λ“œ κ΅¬ν˜„
// μ΅œμ„ μ˜ μ‹œλ‚˜λ¦¬μ˜€(ν•¨μˆ˜μ˜ 인자둜 μ• μ΄ˆμ— μ •λ ¬λœ 배열이 μ „λ‹¬λœ 경우)λ₯Ό κ³ λ €ν•˜μ§€ μ•Šμ€ μ•Œκ³ λ¦¬μ¦˜
{
  function bubbleSort (arr) {
    let unsortedUntilIndex = arr.length - 1;

    while (unsortedUntilIndex > 0) {
      for (let i = 0; i < unsortedUntilIndex; i++) {
        if (arr[i] > arr[i+1]) {
          let temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
        }
      }
      unsortedUntilIndex = unsortedUntilIndex - 1;
    }

    return arr;
  }

  const arr1 = [1, 2, 3, 4];
  console.log(bubbleSort(arr1));
}

// 버블 μ •λ ¬ μ½”λ“œ κ΅¬ν˜„
// boolean 값을 κ°€μ§€λŠ” sorted λ³€μˆ˜λ₯Ό μΆ”κ°€ν•΄ if 쑰건 뢈만쑱 μ‹œ while 문을 μ’…λ£Œν•  수 μžˆλ„λ‘ 함
{
  function bubbleSort (arr) {
    let unsortedUntilIndex = arr.length - 1;
    let sorted = false;

    while (!sorted) {
      sorted = true;

      for (let i = 0; i < unsortedUntilIndex; i++) {
        if (arr[i] > arr[i+1]) {
          let temp = arr[i];
          arr[i] = arr[i+1];
          arr[i+1] = temp;
          sorted = false;
        }
      }

      unsortedUntilIndex = unsortedUntilIndex - 1;
    }

    return arr;
  }

  const arr1 = [1, 2, 3, 4];
  console.log(bubbleSort(arr1));
}

// 배열에 쀑볡 값이 μžˆλŠ”μ§€ ν™•μΈν•˜λŠ” 방법
// 쀑첩 루프 ν™œμš© o β†’ O(N^2)
{
  function hasDuplicateValue (arr) {
    for (let i = 0; i < arr.length - 1; i++) {
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[i] === arr[j]) {
          return true;
        }
      }
    }
    return false;
  }

  const arr1 = [3, 4, 7, 3];
  console.log(hasDuplicateValue(arr1)); // true
}

// 쀑첩 루프 ν™œμš© x β†’ O(N)
{
  function hasDuplicateValue (arr) {
    const checkedValue = [];
    for (let i = 0; i < arr.length; i++) {
      if (checkedValue[arr[i]]) {
        return true;
      } else {
        checkedValue[arr[i]] = 1;
      }
    }
    return false;
  }

  const arr1 = [1, 5, 2, 5];
  console.log(hasDuplicateValue(arr1));
}



/* 5μž₯. λΉ… 였λ₯Ό μ‚¬μš©ν•˜κ±°λ‚˜ μ‚¬μš©ν•˜μ§€ μ•ŠλŠ” μ½”λ“œ μ΅œμ ν™” */

// 선택 μ •λ ¬ μ½”λ“œ κ΅¬ν˜„
// μ΅œμ„ μ˜ μ‹œλ‚˜λ¦¬μ˜€(ν•¨μˆ˜μ˜ 인자둜 μ• μ΄ˆμ— μ •λ ¬λœ 배열이 μ „λ‹¬λœ 경우)λ₯Ό κ³ λ €ν•˜μ§€ μ•Šμ€ μ•Œκ³ λ¦¬μ¦˜
{
  function selectionSort (arr) {
    for (let i = 0; i < arr.length -1; i++) {
      let minIndex = i;

      for (let j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          minIndex = j; // μ΅œμ†Ÿκ°’ 인덱슀 기둝
        }
      }

        let min = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = min;
    }

    return arr;
  }

  const arr1 = [4, 3, 2, 1];
  console.log(selectionSort(arr1)); // [1, 2, 3, 4]
}

// 선택 μ •λ ¬ μ½”λ“œ κ΅¬ν˜„
// μ΅œμ†Ÿκ°’ μΈλ±μŠ€κ°€ λ³€ν™”κ°€ μžˆμ„ λ•Œλ§Œ κ΅ν™˜μ΄ μΌμ–΄λ‚˜λ„λ‘ ν•œλ‹€
{
  function selectionSort (arr) {
    for (let i = 0; i < arr.length -1; i++) {
      let minIndex = i;

      for (let j = i + 1; j < arr.length; j++) {
        if (arr[i] > arr[j]) {
          minIndex = j; // μ΅œμ†Ÿκ°’ 인덱슀 기둝
        }
      }

      if (minIndex !== i) { // μ΅œμ†Ÿκ°’ μΈλ±μŠ€κ°€ λ³€ν–ˆλ‹€λ©΄
        let min = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = min;
      }
    }

    return arr;
  }

  const arr1 = [4, 3, 2, 1];
  console.log(selectionSort(arr1)); // [1, 2, 3, 4]
}

// '같은' λΆ„λ₯˜μ— μ†ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ νš¨μœ¨μ„± 비ꡐ
// 두 μ›μ†Œλ§ˆλ‹€ ν•˜λ‚˜ 걸러 ν•˜λ‚˜λ₯Ό 뽑아 μƒˆ λ°°μ—΄ 생성 - O(1.5N) μ•Œκ³ λ¦¬μ¦˜(결ꡭ은 O(N)이긴 함)
{
  function makeNewArr (arr) {
    const newArr = [];
    for (let i = 0; i < arr.length; i++) { // N번의 룩업
      if (i % 2 === 0) {
        newArr.push(arr[i]); // N/2번의 μ‚½μž…
      }
    }
    return newArr;
  }

  const arr1 = [5, 0, 3, 6, 2, 1];
  console.log(makeNewArr(arr1)); // [5, 3, 2]
}

// '같은' λΆ„λ₯˜μ— μ†ν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜ νš¨μœ¨μ„± 비ꡐ
// 두 μ›μ†Œλ§ˆλ‹€ ν•˜λ‚˜ 걸러 ν•˜λ‚˜λ₯Ό 뽑아 μƒˆ λ°°μ—΄ 생성 - O(N) μ•Œκ³ λ¦¬μ¦˜
{
  function makeNewArr (arr) {
    const newArr = [];
    for (let i = 0; i < arr.length; i += 2) { // N/2번의 룩업
      newArr.push(arr[i]); // N/2번의 μ‚½μž…
    }
    return newArr;
  }

  const arr1 = [5, 0, 3, 6, 2, 1];
  console.log(makeNewArr(arr1)); // [5, 3, 2]
}



/* 6μž₯. 긍정적인 μ‹œλ‚˜λ¦¬μ˜€ μ΅œμ ν™” */

// πŸ”₯ μ‚½μž… μ •λ ¬ μ½”λ“œ κ΅¬ν˜„ πŸ”₯
{
  function insertSort (arr) {
    // 패슀슀루
    for (let i = 1; i < arr.length; i++) {
      let temp_value = arr[i]; // πŸ’‘ μ‚­μ œ
      let position = i; // μž„μ‹œλ‘œ μ‚­μ œν•œ κ°’ temp_valueλ₯Ό μ‚½μž…ν•  인덱슀

      while (position > 0 && arr[position-1] > temp_value) { // πŸ’‘ 비ꡐ
        arr[position] = arr[position-1]; // πŸ’‘ μ‹œν”„νŠΈ
        position = position - 1; // temp_valueλ₯Ό μ‚½μž…ν•  인덱슀 기둝
      }

      if (position !== i) {
        arr[position] = temp_value; // μ‚½μž…
      }
    }

    return arr;
  }

  const arr1 = [5, 4, 3, 2];
  console.log(insertSort(arr1)); // [2, 3, 4, 5]
}

// 두 λ°°μ—΄μ˜ ꡐ집합 κ΅¬ν•˜κΈ°
{
  function intersection (arr1, arr2) {
    const intersection = [];
    for (let i = 0; i < arr1.length; i++) {
      for (let j = 0; j < arr2.length; j++) {
        if (arr1[i] === arr2[j]) {
          intersection.push(arr1[i]);
          break;
        }
      }
    }
    return intersection;
  }

  const firstArr = [3, 5, 1, 7];
  const secondArr = [5, 9, 2, 3];
  console.log(intersection(firstArr, secondArr)); // [3, 5]
}



/* 7μž₯. ν•΄μ‹œ ν…Œμ΄λΈ”λ‘œ 맀우 λΉ λ₯Έ 룩업 */

// μ „μž νˆ¬ν‘œ 기계 λ§Œλ“€κΈ°
// 방법 1. λ°°μ—΄ & ν•΄μ‹œ ν…Œμ΄λΈ” 이용
{
  // 배열에 νˆ¬ν‘œλ₯Ό μ €μž₯(μ‚½μž…) β†’ O(1)
  const totalVotes = [];

  function addVotes (candidate) {
    totalVotes.push(candidate);
  }

  addVotes('A');
  addVotes('B');
  addVotes('C');
  addVotes('B');

  // ν•΄μ‹œ ν…Œμ΄λΈ”λ‘œ 각 후보별 νˆ¬ν‘œ 수 μ„ΈκΈ°(읽기) β†’ O(N)
  function countVotes (votes) {
    const checkedVotes = {};
    for (let i = 0; i < votes.length; i++) { // votes μ„ ν˜• 검색
      if (checkedVotes[votes[i]]) {
        checkedVotes[votes[i]]++;
      } else {
        checkedVotes[votes[i]] = 1;
      }
    }
    return checkedVotes;
  }

  const checkedVotes = countVotes(totalVotes);
  console.log(checkedVotes['B']); // 2
}

// μ „μž νˆ¬ν‘œ 기계 λ§Œλ“€κΈ°
// 방법 2. ν•΄μ‹œ ν…Œμ΄λΈ” 이용
{
  // μ²˜μŒλΆ€ν„° νˆ¬ν‘œλ₯Ό ν•΄μ‹œ ν…Œμ΄λΈ”μ— μ €μž₯(μ‚½μž…) β†’ O(1)
  const totalVotes = {};

  function addVotes (candidate) {
    if (totalVotes[candidate]) {
      totalVotes[candidate]++;
    } else {
      totalVotes[candidate] = 1;
    }
  }

  addVotes('A');
  addVotes('B');
  addVotes('C');
  addVotes('B');

  // ν•΄μ‹œ ν…Œμ΄λΈ”λ‘œ 각 후보별 νˆ¬ν‘œ 수 μ„ΈκΈ°(읽기) β†’ O(1)
  console.log(totalVotes['B']); // 2
}

2. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 문제 풀이

1) μ •λ ¬

(1) K번째 수

πŸ”Ž λ‚΄κ°€ μž‘μ„±ν•œ 풀이

  • for 루프와 slice() 이용
function solution(array, commands) {
    var answer = [];
    
    for (let i = 0; i < commands.length; i++) {
        const subArr = commands[i];
        const unsorted = array.slice(subArr[0] - 1, subArr[1]);
        const sorted = unsorted.sort((a, b) => a - b);
        answer.push(sorted[subArr[2] - 1]);
    }
    
    return answer;
}

πŸ”Ž λ‹€λ₯Έ μ‚¬λžŒμ˜ 풀이

  • for 루프 λŒ€μ‹  map()을, slice() λŒ€μ‹  filter()λ₯Ό 이용

  • 등식 μž‘μ„± μ‹œ, λ“±ν˜Έκ°€ 항상 뒀에 μ˜¨λ‹€ ex) >=, <=, +=, -=

  • const [a, b, c] = arr; β†’ μ΄λ ‡κ²Œ μ“Έ 수 μžˆλ‹€

function solution(array, commands) {
    return commands.map(subArr => {
        const [sPosition, ePosition, position] = subArr;
        
        const newArr = array
            .filter((value, index) => index >= sPosition - 1 && index <= ePosition - 1)
            .sort((a, b) => a - b);
        
        return newArr[position - 1];
    });
}

2) μ™„μ „ 탐색

(1) λͺ¨μ˜κ³ μ‚¬

πŸ”Ž λ‚΄κ°€ μž‘μ„±ν•œ 풀이

  • κ·Έλž˜λ„ λ‚˜λž‘ λΉ„μŠ·ν•˜κ²Œ ν‘Ό μ‚¬λžŒμ΄ 있긴 ν•˜λ‹€. κ·Έλ‚˜λ§ˆ μœ„μ•ˆμ΄ 됐...
function solution(answers) {
  var answer = [];

  const first = [];
  for (let i = 0; i < answers.length / 5 + 2; i++) {
    first.push(1, 2, 3, 4, 5);
  }
  first.length = answers.length;

  let firstCount = 0;
  for (let i = 0; i < answers.length; i++) {
    if (first[i] === answers[i]) {
      firstCount++;
    }
  }

  const second = [];
  for (let i = 0; i < answers.length / 8 + 2; i++) {
    second.push(2, 1, 2, 3, 2, 4, 2, 5);
  }
  second.length = answers.length;

  let secondCount = 0;
  for (let i = 0; i < answers.length; i++) {
    if (second[i] === answers[i]) {
      secondCount++;
    }
  }

  const third = [];
  for (let i = 0; i < answers.length / 10 + 2; i++) {
    third.push(3, 3, 1, 1, 2, 2, 4, 4, 5, 5);
  }
  third.length = answers.length;

  let thirdCount = 0;
  for (let i = 0; i < answers.length; i++) {
    if (third[i] === answers[i]) {
      thirdCount++;
    }
  }

if (firstCount > secondCount && firstCount > thirdCount) {
  answer.push(1);
} else if (secondCount > firstCount && secondCount > thirdCount) {
  answer.push(2);
} else if (thirdCount > firstCount && thirdCount > secondCount) {
  answer.push(3);
} else if (firstCount === secondCount && firstCount > thirdCount) {
  answer.push(1, 2);
} else if (firstCount === thirdCount && firstCount > secondCount) {
  answer.push(1, 3);
} else if (secondCount === thirdCount && secondCount > firstCount) {
  answer.push(2, 3);
} else if (firstCount === secondCount && firstCount === thirdCount && secondCount === thirdCount) {
  answer.push(1, 2, 3);
}

  return answer;
}

πŸ”Ž λ‹€λ₯Έ μ‚¬λžŒμ˜ 풀이

  • filter()λ₯Ό μ΄μš©ν•΄ 각각의 μ‚¬λžŒλ“€μ΄ 맞힌 μ •λ‹΅λ“€λ§ŒμœΌλ‘œ 이뀄진 배열듀을 λ§Œλ“¦
    answer === first[index % first.length]
    κ·Έ κΈΈμ΄λŠ” 곧 각각의 μ‚¬λžŒλ“€μ΄ 맞힌 μ •λ‹΅μ˜ 개수λ₯Ό μ˜λ―Έν•¨

  • Math.max()둜 μ΅œλŒ“κ°’μ„ ꡬ할 수 μžˆλ‹€

function solution(answers) {
  var answer = [];

  var first = [1, 2, 3, 4, 5];
  var second = [2, 1, 2, 3, 2, 4, 2, 5];
  var thrid = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  var firstCount = answers
    .filter((answer, index) => answer === first[index % first.length])
    .length;
  
  var secondCount = answers
    .filter((answer, index) => answer === second[index % second.length])
    .length;
  
  var thirdCount = answers.
    filter((answer, index) => answer === thrid[index % thrid.length])
    .length;
  
  var max = Math.max(firstCount, secondCount, thirdCount);

  if (firstCount === max) {
    answer.push(1)
  } else if (secondCount === max) {
    answer.push(2)
  } else if (thirdCount === max) {
    answer.push(3)
  }

  return answer;
}

πŸ’‘ λ°°μ—΄μ˜ μ΅œλŒ“κ°’, μ΅œμ†Ÿκ°’ κ΅¬ν•˜κΈ°

const arr = [1, 3, 6, 4, 5];

/* μ΅œλŒ“κ°’ κ΅¬ν•˜κΈ° */
// 방법 1 : reduce() 이용
const max = arr.reduce((prev, curr) => prev > curr ? prev : curr);
// 방법 2 : reduce() & Math.max 이용
max = arr.reduce((prev, curr) => Math.max(prev, curr));
console.log(max); // 6

/* μ΅œμ†Ÿκ°’ κ΅¬ν•˜κΈ° */
// 방법 1 : reduce() 이용
const min = arr.reduce((prev, curr) => prev < curr ? prev : curr);
// 방법 2 : reduce() & Math.min 이용
min = arr.reduce((prev, curr) => Math.min(prev, curr));
console.log(min); // 1

✨ 내일 ν•  것

  1. ν”„λ‘œκ·Έλž˜λ¨ΈμŠ€ 문제 풀이
profile
Lee Syong
λŠ₯λ™μ μœΌλ‘œ μ‚΄μž, ν–‰λ³΅ν•˜κ²ŒπŸ˜
이전 포슀트

[TIL] 211016

λ‹€μŒ 포슀트

[TIL] 211018

0개의 λŒ“κΈ€