알고리즘 유형: 완전 탐색(Brute Force)

윤뿔소·2022년 12월 9일
0

Algorithm

목록 보기
2/13
post-thumbnail

구현 능력과 기본 개념을 주로 보는 알고리즘 테스트 유형에 많이들 나온다.

완전 탐색

단순히 모든 경우의 수를 탐색하는 모든 경우

기초 중 기초다. 이 것만 잘 구현한다면 모든 알고리즘을 풀 수 있다. 힘들긴 하겠지만..

Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등이 있다.
나머지는 깊게 파야하니 따로 정리하고 여기서는 기초인 Brute Force에 대해 기술하고 넘어가겠다.

Brute Force

무차별 대입, 조건/반복을 사용하여 해결

기본적인 스킬로만 구현토록하는 기초다.

예시

우리 집에는 세 명의 아이들이 있습니다. 아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분합니다. 먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고, 좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 합니다. 세 아이의 식성은 이렇습니다.

  • 첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)
  • 둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)
  • 셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)

100 개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때, 가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요? (단, 그 주변의 음식은 반찬의 앞, 뒤로 한정합니다.)

이 문제는 단순히 100 개의 반찬을 첫째, 둘째, 셋째의 식성에 맞게 하나씩 대입하여 풀 수 있다. 노다가

for(let i = 0; i < 100; i++) {
  if(첫째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(둘째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
  if(셋째 식성) {
    if(싫어하는 음식이 앞뒤로 있는가) {
      그냥 넘어가자;
    }
    좋아하는 음식 카운트;
  }
}

return 많이 먹은 아이;

이런 식으로 조건문을 반복, 중첩하여 조건문으로만 구현했다. 걍 기초..

예제

maxProduct

문제

숫자로 이루어진 배열 nums가 주어집니다. nums에서 3개의 숫자를 선택하여 곱했을 때 최댓값을 구하는 함수 maxProduct(nums)를 작성하세요. 배열 nums의 길이는 3 이상 10^4 이하이며, 배열의 각 원소는 -1000 이상 1000 이하의 정수입니다.

예를 들어, nums = [1, 2, 3, 4]이면, 2, 3, 4를 선택하여 곱한 결과인 24가 최댓값입니다.

function maxProduct(nums) {
  let maxProduct = -Infinity;

  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      const remaining = nums.slice(j + 1);
      const maxNum = Math.max(...remaining);
      const secondMaxNum = Math.max(
        ...remaining.filter((num) => num !== maxNum)
      );
      const product = nums[i] * nums[j] * Math.max(maxNum, secondMaxNum);
      if (product > maxProduct) {
        maxProduct = product;
      }
    }
  }

  return maxProduct;
}

이 함수는 배열 nums에서 3개의 숫자를 선택하여 곱했을 때 최댓값을 반환합니다. 이 함수는 완전탐색(Brute Force) 알고리즘을 사용하여 문제를 해결합니다. 우선, 최댓값을 저장할 변수 maxProduct-Infinity로 초기화합니다. 그런 다음, 3중 for 루프를 사용하여 모든 가능한 3개의 숫자 조합을 탐색합니다. 탐색한 숫자 3개의 곱셈 결과가 maxProduct보다 크면, maxProduct 값을 해당 곱셈 결과로 업데이트합니다. 마지막으로, maxProduct 값을 반환합니다. 이 알고리즘은 모든 가능한 조합을 탐색하기 때문에, 최적해를 구할 수 있지만, 입력 크기가 커질수록 계산 시간이 증가합니다.

이 코드에서는 먼저 i와 j를 이용하여 2개의 숫자를 선택하고, 나머지 숫자들 중에서 가장 큰 값을 찾아서 이를 곱해 최댓값을 갱신합니다. 이때, 가장 큰 값이 중복될 수 있으므로 가장 큰 값과 같은 값을 제외하고 나머지 중에서 두 번째로 큰 값을 찾아 사용합니다.

profile
코뿔소처럼 저돌적으로

0개의 댓글