완전탐색
모든 경우의 수를 고려하는 탐색 알고리즘
- 조합
- 순열
- 부분집합
- 브루트 포스
- 백 트래킹 등
1. 조합
서로 다른 경우 n개 중에 r개를 선택하는 경우의 수를 의미 한다. 조합은 순서가 없으므로 순서가 다른 조합도 하나의 조합으로 취급한다. 중복이 불가능하다.
[1,2,3] = [3,2,1] = [2,1,3] // 1개Array.forEach()
주어진 함수를 배열 요소 각각에 대해 실행함
currentValue: 현재 요소의 배열 값index: 현재 요소의 인덱스array: 전체 배열
arr.forEach( currentValue ,index , array )
Array.slice()
어떤 배열의 begin부터 end까지(end 미포함)에 대한 얕은 복사본을 새로운 배열 객체로 반환합니다. 원본 배열은 바뀌지 않습니다.
-
begin: 추출을 시작할 인덱스. 음수 인덱스는 배열의 끝에서부터의 길이를 나타냄. slice(-2) 는 배열에서 마지막 두 개의 엘리먼트를 추출. -
end: 추출을 종료 할 인덱스. end 인덱스를 제외하고 추출합니다.
예를 들어, slice(1,4)은 인덱스 1,2,3을 추출함. 음수 인덱스는 배열의 끝에서부터의 길이를 나타냄.
arr.slice ( begin, end );
- 코드
const getCombinations = function (arr, selectNumber) {
const results = [];
// 배열 중 1개를 선택하는 경우 모든 요소를 1개짜리 배열에 담아 return
if (selectNumber === 1) return arr.map((value) => [value]);
// 1) 한 요소를 fixed한 후 나머지를 조합해서 붙인다.
arr.forEach((fixed, index, origin) => {
// 2) fixed를 제외한 나머지 배열 구하기
const rest = origin.slice(index + 1);
// 3) 나머지 배열을 조합하기
const combinations = getCombinations(rest, selectNumber - 1);
// 4) fixed와 나머지 조합 합치기
const attached = combinations.map((combination) => [fixed, ...combination]);
// 합친 조합을 배열에 추가
results.push(...attached);
});
return results;
}
const example = [1,2,3,4];
const result = getCombinations(example, 3);
console.log(result); // [[1, 2, 3],[1, 2, 4],[1, 3, 4],[2, 3, 4]]- 결과 분석
입력 값 : [1,2,3,4]
1) 한 요소를 fixed => 1
2) fixed를 제외한 나머지 배열 => 2,3,4
3) 나머지 배열로 조합하기
=> [2,3],[2,4],[3,4]
4) fixed와 나머지 조합 합치기
=> [1,2,3],[1,3,4],[1,2,4]
1) 한 요소를 fixed => 2
2) fixed를 제외한 나머지 배열 => 3,4
3) 나머지 배열로 조합하기
=> [3,4]
4) fixed와 나머지 조합 합치기
=> [2,3,4]
...
1) 한 요소를 fixed => 3
...
1) 한 요소를 fixed => 4
...
2. 순열
서로 다른 경우 n개 중에 r개를 선택하는 경우의 수를 의미 한다. 조합은 순서가 없으므로 순서가 다른 조합도 하나의 조합으로 취급한다. 중복이 불가능하다.
[1,2,3] != [3,2,1] != [2,1,3] // 3개- 코드
const getPermutations= function (arr, selectNumber) {
const results = [];
// 배열 중 1개를 선택하는 경우 모든 요소를 1개짜리 배열에 담아 return
if (selectNumber === 1) return arr.map((value) => [value]);
// 1) 한 요소를 fixed한 후 나머지를 순열로 세운다.
arr.forEach((fixed, index, origin) => {
// 2) fixed를 제외한 나머지 배열 구하기
const rest = [...origin.slice(0, index), ...origin.slice(index+1)]
// 3) 나머지 배열로 순열세우기
const permutations = getPermutations(rest, selectNumber - 1);
// 4) fixed와 나머지 순열 합치기
const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
// 5) 합친 순열을 배열에 추가
results.push(...attached);
});
return results;
};
const example = [1,2,3,4];
const result = getPermutations(example, 3);
// [[1, 2, 3],[1, 2, 4],[1, 3, 2],[1, 3, 4],[1, 4, 2],[1, 4, 3],[2, 1, 3],[2, 1, 4],[2, 3, 1],[2, 3, 4],[2, 4, 1], ... [4, 3, 2]- 결과 분석
입력 값 : [1,2,3,4]
1) 한 요소를 fixed => 1
2) fixed를 제외한 나머지 배열 => 2,3,4
3) 나머지 배열로 순열세우기
=> [3,4],[4,3],[2,4],[4,2],[2,3],[3,2]
4) fixed와 나머지 순열 합치기
=> [1,3,4],[1,4,3],[1,2,4],[1,4,2],[1,2,3],[1,3,2]
1) 한 요소를 fixed => 2
...
1) 한 요소를 fixed => 3
...
1) 한 요소를 fixed => 4
...
3. 부분 집합
가능한 모든 경우의 수를 구함. 한 원소에 대해서 포함을 하거나 (선택을 하거나), 포함을 하지 않는다(선택을 하지 않는다). 즉, 한 원소 당 2가지의 경우의 수가 있다.
[1,2,3] 의 부분 집합
[1],[2],[3],[1,2],[2,3],[1,3],[1,2,3]비트연산자 << >>
<<: 왼쪽으로 시프트 하는 연산자>>: 오른쪽으로 시프트 하는 연산자
5 << 2
1) 5를 2진수로 변환 => 101
2) 왼쪽으로 2번 시프트 => 10100
3) 결과를 10진수로 변환 => 20
5 >> 2
1) 5를 2진수로 변환 => 101
2) 오른쪽으로 2번 시프트 => 1
3) 결과를 10진수로 변환 => 1- 코드
let arr = [1,2,3,4];
let result = [];
for(let i = 1; i < (1 << arr.length); i++) {
result.push([]);
for(let j = 0; j < arr.length; j++) {
if(i & (1 << j)) result[i-1].push(arr[j])
}
}
console.log(result);
// [[1],[2],[1, 2],[3],[1, 3],[2, 3],[1, 2, 3],[4],[1, 4],[2, 4],[1, 2, 4],[3, 4],[1, 3, 4],[2, 3, 4],[1, 2, 3, 4]]4. 완전탐색
[1,2,3] 의 완전탐색
[1],[2],[3],
[1,2],[2,1],[2,3],[3,2],[1,3],[3,1],
[1,2,3],[2,1,3],[2,3,1]...let set = new Set();
numOfCase([1,7],'')
function numOfCase(arr,str) {
if(arr.length) {
for(let i = 0; i <arr.length; i++) {
let copy = [...arr];
copy.splice(i,1);
numOfCase(copy,str + arr[i])
}
}
if(str > 0) set.add(Number(str))
}
console.log(Array.from(set)) // [17, 1, 71, 7]그외에도 back tracking의 개념중 유명한 알고리즘인 BFS, DFS가 있는데 그건 다음에 알아보자.
출처
연봉킹이 되고 싶은 개발자