TIL. 완전 탐색(Brute Force) 알고리즘 문제풀이

📌 완전탐색(Exhaustive Search) / 브루트포스(Brute Force)

• 컴퓨터 알고리즘 중 하나로, 가능한 모든 경우의 수를 일일이 시도해보는 방법이다. 이 방법은 단순하고 직관적이지만, 경우의 수(입력의 크기)가 많아질수록 계산 시간이 급격히 증가하여 계산 속도가 느려지는 단점이 있다.

• 대표적으로 비밀번호를 찾는 경우를 예로 들 수 있다. 비밀번호는 알파벳, 숫자, 특수문자 등의 문자로 이루어져 있기 때문에 가능한 경우의 수가 매우 많은데, 이 경우 브루트포스를 사용하면 모든 가능한 비밀번호를 차례대로 시도해보면서 정확한 비밀번호를 찾을 수 있다.

• 하지만 브루트포스는 가능한 모든 경우를 일일이 시도하기 때문에 계산 시간이 매우 오래 걸리는 경우가 있으므로, 효율적인 알고리즘을 찾는 것이 중요하다고 한다.🧐

✍️ 그냥 알고리즘 문제를 보고 기계적으로 푸는 것보다 이렇게 완전탐색은 어떤 알고리즘이고 어떤 장단점을 가지고 있고 예시로 비밀번호를 찾는 경우에 사용된다는 정보를 얻음으로써 왜 알고리즘을 알아야 하는지 알 것 같았다. 😎🔥

---

자릿수의 합

문제 설명

N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력 하는 프로그램을 작성하세요. 자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 합니다. 만약 235 와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력해야 합니다.

▣ 입력설명
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 10,000,000를 넘지 않는다.

▣ 출력설명
자릿수의 합이 최대인 자연수를 출력한다.

▣ 입출력 예

n	arr	return
8	[7 128 460 603 40 521 137 123]	137
5	[9, 99, 987, 978, 999]	999

풀이

const sumComparison = (n, arr) => {
  // 1) 배열로 받은 모든 값들을 돌려서 비교하자.
  // 2) 배열 처음부터 한 개씩 각각의 숫자 자릿수 합산을 더한다.
  // 3) 다음 자릿수 합산이 더 큰지 이전의 자릿수 합산이 큰지 비교하여 큰쪽을 저장한다.
  // 3-1) 만약 같다면 각 숫자의 기존 값이 더 큰쪽이 저장된다.
  // 4) 최종적으로 저장된 제일 큰 자릿수의 합 (혹은 같을경우 제일 큰 기존 값)을 가진 기존 숫자원본이 출력된다.

  let answer = 0;
  let max = 0;
  for (let i = 0; i < n; i++) { // 1) 
    let sum = 0;
    let str = arr[i].toString(); // 2)
    for (let j = 0; j < str.length; j++) { // 3) 
      sum += parseInt(str[j]);
    } 
    if (max <= sum) { // 4)
      max = Math.max(max, sum);
      answer = Math.max(answer, Number(str)); // 5)
    }
  }

  return answer;
};

// let arr = [7, 128, 460, 603, 40, 521, 137, 123];
// console.log('answer: ', sumComparison(8, arr)); // answer: 137

let arr = [9, 99, 987, 978, 999];
console.log('answer: ', sumComparison(5, arr)); // answer: 999

🤔 어떻게 풀어볼까?

• 1) 배열의 길이만큼 숫자를 돌린다.
• 2) 배열의 숫자를 문자로 바꾼다.
• 3) 바꾼 문자를 하나씩 돌려서 합산한 뒤(자릿수 합산) sum에 넣는다.
• 4) ✨ 만약 max보다 sum이 크다면 max에 넣는다. & 그 sum을 만든 기존 숫자가 answer안에 담긴다.
• 5) Number메서드를 사용하지 않아도 비교연산자를 이용한 처리는 잘 됐다.😀 하지만 숫자와 문자를 비교하는 것은 맞지 않을 것 같으므로 숫자 처리를 한 뒤 비교하도록 하자.

✍️ 처음 계획했던 대로 비슷하게 작성한 것 같다. 이 과정중에 toString() 메서드로 한번 문자열로 바꾼 뒤 다시 Number() 로 변환해야 하는 과정이 불필요한 것 같았다. 그리고 꼭 2중 for 문이어야 하는지도 생각해보자.
또, 자릿수를 합산하는 과정 뿐만아니라 그 값을 가진 숫자의 원본 값이 return 되어야 하므로 이 부분도 고려해야 했다. 🤔

while(x){
  sum+=(x%10);
  x=Math.floor(x/10);
}

이런식으로 숫자 형태에서 바로 자릿수 합산하는 것도 찾았던 것 같은데 다시 작성해봐야겠다.🔥

✍️ solution

for...in 문과 while 문으로도 작성할 수 있을 것 같았다.

function solution(n, arr) {
  let answer, // 1)
    max = Number.MIN_SAFE_INTEGER;
  for (let x of arr) {
    let sum = 0,
      tmp = x; // 2)
    while (tmp) { // 3)
      sum += tmp % 10;
      tmp = Math.floor(tmp / 10);
    }
    if (sum > max) { // 4)
      max = sum;
      answer = x;
    } else if (sum === max) { // 5)
      if (x > answer) answer = x;
    }
  }
  return answer;
}

let arr = [128, 460, 603, 40, 521, 137, 123];
console.log(solution(7, arr));

1) 변수 answer, max를 한번에 세팅한다.
2) tmp (temporary:임시) 변수를 만들고 arr을 돌리면서 숫자를 담는다.
3) 이 while 문이 숫자를 통해 각 자릿수의 합을 구하는 식이다.
예를들어 128의 경우 8 → 2 → 1 순으로 합산하게 된다.
4) 이렇게 각 자릿수를 구한 합이 max 보다 크게되면 max에 재할당 해준다. answer에는 기존 값을 저장한다.
5) 만약 저장해온 max값과 현재 숫자의 자릿수 합인sum이 같다면 같은 자릿수의 합 값을 가지고 있는 기존 숫자 x와 (저장해온)answer 숫자를 비교한 뒤 큰 수를 answer에 재할당 한다.

✍️ 이 방법으로 하면 숫자에서 문자로, 문자에서 숫자로 다시 바꾸거나 이중 for문을 사용하지 않아도 된다. 또 max와 sum이 같을 경우만 따로 else if로 빼두고 그 때만 비교할 수 있다. 😀

---

뒤집은 소수

문제 설명

N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요. 예를 들어 32를 뒤집으면 23이고, 23은 소수이다. 그러면 23을 출력한다. 단 910를 뒤집으면 19로 숫자화 해야 한다. 첫 자리부터의 연속된 0은 무시한다.

▣ 입력설명
첫 줄에 자연수의 개수 N(3<=N<=100)이 주어지고, 그 다음 줄에 N개의 자연수가 주어진다. 각 자연수의 크기는 100,000를 넘지 않는다.

▣ 출력설명
첫 줄에 뒤집은 소수를 출력합니다. 출력순서는 입력된 순서대로 출력합니다.

▣ 입출력 예

arr	return
[32, 55, 62, 20, 250, 370, 200, 30, 100]	[23, 2, 73, 2, 3]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]	[2, 3, 5, 7, 11, 31, 41, 61, 71, 2]

풀이

const isReversedPrimeNumber = (arr) => { // 1)
  let answer = [];
  for (let x of arr) {
    let revNum = String(x).split('').reverse().join('');
    let parsedInt = parseInt(revNum);
    let isPrime = true;

    if (parsedInt < 2) { // 2)
      isPrime = false;
      continue;
    }
    for (let i = 2; i <= parsedInt / 2; i++) { // 3)
      if (parsedInt % i === 0) {
        isPrime = false; // 4)
        break; // 4-1) 
      }
    }
    if (isPrime) { // 5)
      answer.push(parsedInt);
    }
  }
  return answer;
};

let arr1 = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log('✨return: ', isReversedPrimeNumber(arr1)); // ✨return: (5) [23, 2, 73, 2, 3]

let arr2 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 ];
console.log('✨return: ', isReversedPrimeNumber(arr2)); // ✨return: (10) [2, 3, 5, 7, 11, 31, 41, 61, 71, 2]

🤔 어떻게 풀어볼까?

• 1) 입력 받은 arr안의 숫자들을 하나하나 탐색한다.
• 2) 숫자를 뒤집는다.
• 2-1) 만약 0이 맨 앞자리에 온다면 생략한다. (숫자화 시킨다.)
• 3) 뒤집은 숫자가 소수인지 판별한다.
• 4) 뒤집어진 숫자 중 소수인 숫자들만 출력한다.

✍️ check!

• 1) 함수는 주어진 배열에서 숫자를 거꾸로 뒤집은 후, 그 수가 소수인지 판별한 다음, 소수인 경우 새로운 배열에 추가하고 반환한다.

• 2) 이 때, 1과 0은 소수가 아니기 때문에, parsedInt 가 2보다 작은 경우에는 isPrime 을 false 로 설정하고 continue 를 호출하여 다음 숫자로 이동한다.

• 3) 그리고 2부터 parsedInt 의 절반까지의 모든 수를 돌면서, 나누어 떨어지는 수가 있는지 찾아낸다.
  여기서 true 라면 소수가 아니라는 뜻이다.

• 4) 나누어 떨어지는 수가 있다면, 해당 숫자는 소수가 아니므로 isPrime 을 false 로 설정하고 루프를 종료한다.

• 4-1) 소수가 아닌 경우에는 더 이상 루프를 돌지 않도록 해주는 것이 시간 복잡도가 느는 것을 방지 할 수 있다.

• 5) 그리고 마지막으로 isPrime이 true인 경우, answer 배열에 parsedInt 를 추가한다.

❗️ 여기서 3) 조건 부분을 주의하자 🔥

• i <= parseInt 로 설정한다면 무조건 참이 되어 버리므로, 오류가 발생할 수 있다.
  ex.) 7%7은 0이다. 어떤 수를 자기 자신으로 나눈 나머지는 항상 0이 된다.

• 어떤 숫자던 1과 자기자신 빼면 약수의 가장 큰 값은 그 숫자의 절반이다.
  (16으로 예를들면 1x16, 2x8, 4x4 , 8x2, 16x1)
  심화) 제곱근 까지만 곱해도 된다. (1,2,4)

• 따라서 let i = 2; i < parsedInt; i++ 이렇게 작성해도 답이 나오지만, 소수를 판별하기 위해서는 소수의 절반 이하의 수까지만 검사해도 충분하다. 🤔
  → 이 부분의 근거를 찾아 보았다.

  ✍️ 소수의 가장 기본적인 정의는 자기 자신과 1만을 약수로 가지는 수를 소수라고 한다. 그러나 자기 자신을 제외한 가장 큰 약수는 그 수의 절반 이하이기 때문에 소수인지 아닌지를 판별하기 위해서는 그 수의 절반 이하의 수까지만 검사해도 충분하다.
  예를 들어 97이 소수인지 판별하려면 2부터 48까지의 수만 검사하면 되며, 이렇게 하면 소수를 빠르게 판별할 수 있다.

  📌 소수 & 약수
  소수: 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 자연수이다.
  약수: 어떤 수를 나누어 떨어지게 하는 수를 그 수의 약수라고 한다.

✍️ solution

// 1.
 function isPrime(num) {
   if (num === 1) return false; // 2)
   for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) { // 3)
     if (num % i === 0) return false;
   }
   return true;
 }
function solution(arr) {
  let answer = [];
  for (let x of arr) {
    let res = 0;
    while (x) { // 1) 원본이 필요하지 않으므로 이렇게 해도 된다.
      let t = x % 10; // t는 x의 1의자리이다
      res = res * 10 + t;
      x = parseInt(x / 10); // 나눈 몫은 그 앞의 숫자
    }
    if (isPrime(res)) answer.push(res);
  }
  return answer;
}

let arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log(solution(arr));


// 2.
function isPrime(num) {
  if (num === 1) return false;
  for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
    if (num % i === 0) return false;
  }
  return true;
}
function solution(arr) {
  let answer = [];
  for (let x of arr) {
    let res = Number(x.toString().split('').reverse().join('')); // 4)
    if (isPrime(res)) answer.push(res);
  }
  return answer;
}

let arr = [32, 55, 62, 20, 250, 370, 200, 30, 100];
console.log(solution(arr));

• 1) 어떤 숫자던 10으로 나눈 나머지는 1의 자리이고, 10으로 나눈 몫은 그 앞의 숫자이다. 😀

• 2) 1은 소수가 아니다. (1과 자기자신은 약수가 맞다.)
  ex. 15 가 주어진다면 15에서 1과 15는 약수이고, 2~14까지 약수가 발견되면 소수가 아닌 것이다.
  

• 3) Math.sqrt() 제곱근 까지만 본다.

• 4) 이렇게 앞에오는 '0' 처리를 Number() 로도 할 수 있다.🧐

✍️ 이렇게 소수를 판별하는 함수를 따로 분리하면 가독성에 더 도움이 될 것 같다.