(이 글로 이해가 안된다면 정말 자세한 내용과 설명은 본문 하단에 링크를 달아뒀으니 해당 블로그 가서 보면 된다. 정말 정리를 잘해놨다.)
완전 탐색 알고리즘의 방식인 조합, 순열, 중복순열 알고리즘에 대해 알아보자.
왜 이 3가지 알고리즘을 동시에 다루냐면 알고리즘 구조가 비슷하기 때문이다.
전체적으로 아래와 같은 형식을 지닌다.
1. 선택하려는 개수를 확인한다. (ex 배열에서 2개의 값으로 이루어진 조합 혹은 순열)
2. 배열의 길이만큼 반복한다.
3. 배열에서 하나의 수를 선택한다. (기준 값)
4. 기준 값을 제외한 나머지 배열을 가지고 다시 1번부터 시작한다. (재귀)
위 방식을 통해 계속해서 재귀를 통해 반복하다보면 순열, 중복순열, 조합을 구할 수 있다.
각 조합, 순열, 중복순열 별 달라지는 부분은 4번부분이다.(나머지 배열의 기준이 달라진다.)
대략 어떤느낌인지 알았다면 아래 코드를 통해 다시한번 접해보고 다시와서 읽어보도록 하자.
1. 조합
우선 조합이란 뭘까?
조합은 서로 다른 n개의 원소를 가지고 순서에 상관없이 r개의 원소를 선택하는 것이다.
그래서 조합의 기호를 "nCr" 처럼 나타낸다.
만약 3C2 을 코드로 구현한다면 다음과 같은 인풋 아웃풋을 가질게 된다.
Input: [1, 2, 3]
Output: [ [1, 2], [1, 3], [2, 3] ]
이제 코드를 살펴보면 다음과 같다.
▷ 조합 알고리즘 구현
const getCombinations = (arr, num) => {
const results = [];
// nC1 이며, 1이면 의미 없기때문에 바로 반환한다.
if (num === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
// 조합에서는 값 순서에 상관없이 중복이 되면 안되기 때문에 현재값 이후의 배열들만 추출한다.
const rest = origin.slice(index + 1);
// 나머지 배열을 기준으로 다시 조합을 실시한다.
// 기준값(fixed)이 있기 때문에 선택하려는 개수에서 - 1 을 해준다.
const combinations = getCombinations(rest, num - 1);
// 기준값(fixed)에 돌아온 조합(combinations)을 붙인다.
const attached = combinations.map(v => [fixed, ...v]);
// 붙인 값을 결과 값에 넣어준다.
results.push(...attached);
});
return results;
}2. 순열
순열이란 뭘까?
순열은 서로 다른 n개의 원소를 가지고 중복 없이 순서에 상관있게 r개의 원소를 선택 혹은 나열 하는것이다.
그래서 순열의 기호를 "nPr" 처럼 나타낸다.
만약 3P2 을 코드로 구현한다면 다음과 같은 인풋 아웃풋을 가질게 된다.
Input: [1, 2, 3]
Output: [ [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2] ]
이제 코드를 살펴보면 다음과 같다.
▷ 순열 알고리즘 구현
const getPermutations = (arr, num) => {
const results = [];
// nP1 이며, 1이면 의미 없기때문에 바로 반환한다.
if (num === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
// 순열에서는 조합과 달리 순서만 바뀌면 중복이 아니기때문에 기준값을 제외한 나머지 배열을 넣어준다.
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
// 나머지 배열을 기준으로 다시 순열을 구한다.
// 기준값(fixed)이 있기 때문에 선택하려는 개수에서 - 1 을 해준다.
const permutations = getPermutations(rest, num - 1);
// 기준값(fixed)에 순열(permutations)을 붙인다.
const attached = permutations.map(v => [fixed, ...v]);
// 붙인 값을 결과 값에 넣어준다.
results.push(...attached);
});
return results;
}3. 중복순열
중복순열이란 뭘까?
중복순열은 서로 다른 n개의 원소를 가지고 중복을 허용하여 r개의 원소를 선택 혹은 나열 하는것이다.
(중복을 허용한다는건 본인 숫자의 중복을 의미한다.)
만약 중복순열을 3개의 원소를 가지고 2개의 원소를 선택하도록 구현하면 아래와 같은 인풋 아웃풋이 출력된다.
Input: [1, 2, 3]
Output: [ [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3] ]
이제 코드를 살펴보면 다음과 같다.
▷ 중복순열 알고리즘 구현
const getPermutations = (arr, num) => {
const results = [];
if (num === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
// 기준값(fixed)이 있기 때문에 선택하려는 개수에서 - 1 을 해준다.
const permutations = getPermutations(origin, num - 1);
// 기준값(fixed)에 순열(permutations)을 붙인다.
const attached = permutations.map(v => [fixed, ...v]);
// 붙인 값을 결과 값에 넣어준다.
results.push(...attached);
});
return results;
}
중복순열은 기준 배열을 잘라 쓸 필요없이 전체 배열을 대상으로 한다.
4. 순열 기준 만들 수 있는 모든 경우의 수 추출
마지막으로 별거 아닌데, 위에서 설명한 순열, 중복순열, 조합의 경우 조합하려는 개수를 지정해 놔야 돌아가기 때문에 모든 경우의 수를 찾을수는 없다.
그래서 다른 방법이 있을지는 모르겠지만 위에서 설명한 순열 코드를 기준으로 모든 경우의 수를 뽑는 방법에 대해 알아보자. (그냥 단순하게 반복문을 통해 함수를 실행시켜준것이다.)
const getPermutations = (arr, num) => {
const results = [];
if (num === 1) return arr.map(v => [v]);
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
const permutations = getPermutations(rest, num - 1);
const attached = permutations.map(v => [fixed, ...v]);
results.push(...attached);
});
return results;
}
const getAllPermutations = (arr) => {
let results = [];
arr.forEach((value, index, origin) => {
results.push(...getPermutations(origin, index + 1));
});
return results;
}
만약 3개의 원소를 가지고 만들 수 있는 모든 경우의 수를 추출하면 다음과 같이 출력된다. (일반 순열 기준)
Input: [1, 2, 3]
Output: [
[1], [2], [3],
[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
]
참고 : JavaScript로 순열과 조합 알고리즘 구현하기
JavaScript로 순열과 조합 알고리즘 구현하기
1. 조합 서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합이라 하고, 이 조합의 수를 기호로 nCr와 같이 나타낸다. 바로 예를 살펴보도록 하자. 4Com
velog.io
댓글