04. 완전탐색(블루투포스) - 선형 구조

완전 탐색(블루투포스)

Brute(짐승) + Force(힘) 가 합쳐져 짐승 같은 힘으로 모든 경우를 탐색하는 방법이다.
흔한 예시로 우리가 어렸을 적에 사물함 비밀번호를 까먹었을 때 하는 방법과 같다.
그렇다. 0000~9999까지 모두 대입해서 하는 방법이다.

장점

• 비교적 쉽게 구현할 수 있는 알고리즘이다.

단점

• 이름이 Brute Force로 붙여진 것과 같이 굉장히 단순한 방법이기에 자원(시간, 메모리)이 많이 소모된다.

Tip

모든 경우의 수를 만들어 내는 로직을 만들어 내는 것이 관건이다. → 다중 for문이 많이 활용됨

문제 풀이

Ch.04 - 01. 자릿수의 합

function solution(arr) {
  let cacheMaxSumNum = 0;

  return arr.reduce((acc, cur) => {
    const sumNum = `${cur}`
      .split("")
      .reduce((acc, cur) => acc + Number.parseInt(cur, 10), 0);

    if (cacheMaxSumNum <= sumNum) {
      cacheMaxSumNum = sumNum;
      return Math.max(acc, cur);
    }
    return acc;
  }, 0);
}

Ch.04 - 02. 뒤집은 소수

function solution(arr) {
  const checkPrimeNum = (num) => {
    if (num === 1) return false;

    const squareRootNum = Math.sqrt(num);

    for (let i = 2; i <= squareRootNum; i++) {
      if (num % i === 0) return false;
    }

    return true;
  };

  const answer = [];

  for (let x of arr) {
    let reverseNum = 0;

    while (x) {
      const remainNum = x % 10;

      reverseNum = reverseNum * 10 + remainNum;
      x = parseInt(x / 10, 10);
    }

    if (checkPrimeNum(reverseNum)) answer.push(reverseNum);
  }

  return answer;
}

Ch.04 - 03. 멘토링

function solution(test) {
  let answer = 0;

  let students = test[0].length;
  let testNum = test.length;

  for (let i = 1; i <= students; i++) {
    for (let j = 1; j <= students; j++) {
      if (i === j) continue;

      let count = 0;
      for (let k = 0; k < testNum; k++) {
        let mentee = 0;
        let mentor = 0;

        for (let s = 0; s < students; s++) {
          if (test[k][s] === i) mentee = s;
          if (test[k][s] === j) mentor = s;
        }

        if (mentee < mentor) count++;
      }
      if (count === testNum) answer++;
    }
  }
  return answer;
}

Ch.04 - 04. 졸업 선물

function solution(limitPrice, doubleArr) {
  let answer = 0;

  const n = doubleArr.length;
  const sortedArr = [...doubleArr].sort((a, b) => a[0] + a[1] - (b[0] + b[1]));

  for (let i = 0; i < n; i++) {
    let remainPrice = limitPrice - (sortedArr[i][0] / 2 + sortedArr[i][1]);
    let count = 1;
    for (let j = 0; j < n; j++) {
      if (i === j) continue;

      remainPrice -= sortedArr[j][0] + sortedArr[j][1];
      if (0 <= remainPrice) {
        count++;
      } else {
        answer = Math.max(answer, count);
        break;
      }
    }
  }

  return answer;
}

Ch.04 - 05. K번째 큰 수

function solution(k, arr) {
  let maxSumList = new Set(); // 총 합이 같은 값을 제거하기 위함

  const arrLength = arr.length;

  for (let i = 0; i < arrLength; i++) {
    for (let j = i + 1; j < arrLength; j++) {
      for (let m = j + 1; m < arrLength; m++) {
        maxSumList.add(arr[i] + arr[j] + arr[m]);
      }
    }
  }

  return Array.from(maxSumList).sort((a, b) => b - a)[k - 1];
}