구현 능력과 기본 개념을 주로 보는 알고리즘 테스트 유형에 많이들 나온다.
단순히 모든 경우의 수를 탐색하는 모든 경우
기초 중 기초다. 이 것만 잘 구현한다면 모든 알고리즘을 풀 수 있다. 힘들긴 하겠지만..
Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등이 있다.
나머지는 깊게 파야하니 따로 정리하고 여기서는 기초인 Brute Force에 대해 기술하고 넘어가겠다.
무차별 대입, 조건/반복을 사용하여 해결
기본적인 스킬로만 구현토록하는 기초다.
우리 집에는 세 명의 아이들이 있습니다. 아이들의 식성은 까다로워, 먹기 싫은 음식과 좋아하는 음식을 철저하게 구분합니다. 먹기 싫은 음식이 식탁에 올라왔을 땐 음식 냄새가 난다며 그 주변의 음식까지 전부 먹지 않고, 좋아하는 음식이 올라왔을 땐 해당 음식을 먹어야 합니다. 세 아이의 식성은 이렇습니다.
- 첫째: (싫어하는 음식 - 미역국, 카레) (좋아하는 음식 - 소고기, 된장국, 사과)
- 둘째: (싫어하는 음식 - 참치, 카레) (좋아하는 음식 - 미역국, 된장국, 바나나)
- 셋째: (싫어하는 음식 - 소고기) (좋아하는 음식 - 돼지고기, 된장국, 참치)
100 개의 반찬이 일렬로 랜덤하게 담긴 상이 차려지고, 한 명씩 전부 먹을 수 있다고 할 때, 가장 많이 먹게 되는 아이와 가장 적게 먹게 되는 아이는 누구일까요? (단, 그 주변의 음식은 반찬의 앞, 뒤로 한정합니다.)
이 문제는 단순히 100 개의 반찬을 첫째, 둘째, 셋째의 식성에 맞게 하나씩 대입하여 풀 수 있다. 노다가
for(let i = 0; i < 100; i++) {
if(첫째 식성) {
if(싫어하는 음식이 앞뒤로 있는가) {
그냥 넘어가자;
}
좋아하는 음식 카운트;
}
if(둘째 식성) {
if(싫어하는 음식이 앞뒤로 있는가) {
그냥 넘어가자;
}
좋아하는 음식 카운트;
}
if(셋째 식성) {
if(싫어하는 음식이 앞뒤로 있는가) {
그냥 넘어가자;
}
좋아하는 음식 카운트;
}
}
return 많이 먹은 아이;
이런 식으로 조건문을 반복, 중첩하여 조건문으로만 구현했다. 걍 기초..
숫자로 이루어진 배열 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개의 숫자를 선택하고, 나머지 숫자들 중에서 가장 큰 값을 찾아서 이를 곱해 최댓값을 갱신합니다. 이때, 가장 큰 값이 중복될 수 있으므로 가장 큰 값과 같은 값을 제외하고 나머지 중에서 두 번째로 큰 값을 찾아 사용합니다.