최근에 알고리즘 문제를 풀면서 완전탐색은 쉽다! 라고 생각했는데, 순열과 조합 그리고 DFS, BFS를 구현해야지만 풀리는 문제들을 마주하면서 안되겠다고 생각해 포스팅하는 글입니다.😭
대체적으로 제가 마주할때마다 당황스러웠던 문제들은 아래의 방식들을 구현해내는 것이 대다수였습니다.
- 하나의 배열이 주어졌을 때, [1,2,3,4,5]
- 배열의 크기 그대로 뽑힐 수 있는 모든 조합을 구한다. (예시는 5개로 뽑힐 수 있는)
- 배열의 숫자 상관 없이 1개부터 뽑힐 수 있는 모든 조합을 구한다.
그래서 오늘은 두 가지를 중점적으로 순열과 조합을 구현해해는 JavaScript에 대해 포스팅합니다.
순열 (Permutation) - nPm
순열은 쉽게 말해 순서가 있는 정렬을 만드는 경우의 수를 의미합니다.
[a,b,c] 배열 내의 요소 모두를 줄 세우는 방법은 수학시간에 배웠듯 3! 의 경우의 수가 있습니다.
[a,b,c], [a,c,b], [b,a,c], [b,c,a], [c,a,b], [c,b,a]
총 3! = 3 X 2 X 1 = 총 6가지의 경우의 수가 존재합니다.
어떤 배열이 주어졌을 때, 배열 내의 원소들을 위와 같이 순열의 방식으로 조합해 반환하는 함수를 만들어보겠습니다.
먼저, 잔여 배열에 원소를 하나씩 조회해 선별 배열에 두고 남겨진 잔여배열을 초기에 원본 배열이라고 다시 설정한다면 규칙이 어느정도 보이게 됩니다.
빨간색으로 표시된 1,2,3은 같은 로직이 반복되고 있습니다. 이를 재귀함수로 표현할 수도 있고, 종료조건은 잔여 배열의 길이가 0이거나 선별배열의 길이가 원본배열의 길이와 같을 때로 설정합니다.
순열 구현 의사코드
- 선별배열은 빈배열, 잔여배열은 원본배열로 생각한다.
- 잔여배열 내의 원소를 하나씩 순회하며,
forEach(value =>
선별배열에 조회된 원소(value) 를 넣는다. - 잔여배열을 선별된 원소가 제외된 잔여배열로 재정의한다.
- 1-2 까지의 과정을 하나의 함수로 만들어 재귀함수를 호출한다. 새로운 선별배열, 잔여배열을 인자로 받도록한다!
그대로 한 종료지점까지 따라가 보면
1. 선별 [a] 잔여 [b,c]
1-1. 선별 [a,b] 잔여 [c]
1-1-1. 선별 [a,b,c] 잔여 [] => 순열 하나 완성
1-2. 선별 [a,c] 잔여 [b]
1-2-1. 선별 [a,c,b] 잔여 [b] => 순열 둘 완성
2. 선별 [b] 잔여 [a,c]
2-1. 선별 [b,a] 잔여 [c]
2-1-1. 선별 [b,a,c] 잔여 => 순열 셋 완성
2-2. 선별 [b,c] 잔여 [a]
2-2-1. 선별 [b,c,a] => 순열 넷 완성
......순열 함수 코드
const output = [];
function permutation(arr, str, output) {
if (arr.length === 0) {
output.push(str);
}
for (let i = 0; i < arr.length; i++) {
const copy = [...arr];
copy.splice(i, 1);
permutation(copy, str + arr[i], output);
}
}
permutation(['a', 'b', 'c'], '', output);
// console.log(output);
// [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]위의 코드를 기반으로, 프로그래머스 고득점 Kit - 완전탐색 - 소수찾기 문제를 풀 수 있습니다.
문제는 아래 링크를 통해서 확인해주세요.
프로그래머스-소수찾기
이전에 이 문제를 풀이 할 때, 다른 분들의 답안을 보고 순열을 통해 풀이를 한다는 것을 알게 되었습니다.
풀이를 보았을 때, 이게 무슨 말인가 했습니다. Lv2여서 어렵다고 생각했어요...😂
이번에는 위의 순열을 구현해내는 코드를 기반으로 저만의 답안을 코드로 쳐보았습니다.
프로그래머스 소수 찾기 풀이 (순열 사용)
function solution(numbers) {
const numbersList = numbers.split('');
const output = [];
const isPrime = (num) => {
if(num === 0 || num === 1) return;
for(let i = 2; i < num; i++){
if(num % i === 0) return;
}
output.push(num);
}
const permutation = (arr, str) => {
for(let i = 0; i < arr.length; i++){
const copy = [...arr];
copy.splice(i,1);
permutation(copy, str + arr[i]);
}
if(str.length > 0) isPrime(+str);
}
permutation(numbersList, "")
const answer = [...new Set(output)]
return answer.length;
}모든 조합의 순열
만약에 그렇다면, 만들 수 있는 모든 경우의 수를 추출하는 순열은 어떻게 만들 수 있을까요?
위의 순열은 모두 뽑았을 때의 경우의 수를 구하는 식이었습니다.
예를 들어, [1,2,3,4,5]가 있다면 5가지를 모두 뽑는 경우의 수를 구하는 것이었는데요,
그게 아니라, 2가지도 뽑고, 3가지도 뽑을 수 있는 모든 경우의 순열 구현을 해보겠습니다.
function permutation(arr, str, output) {
if (arr.length === 0) {
output.push(str);
}
for (let i = 0; i < arr.length; i++) {
const copy = [...arr];
copy.splice(i, 1);
permutation(copy, str + arr[i], output);
}
// 이 부분만 추가
if (str.length > 0) output.push(str);
}
let output = [];
permutation(['a', 'b', 'c'], '', output);
output = [...new Set(output)];
// console.log(output);
// ['abc', 'ab', 'acb', 'ac', 'a','bac', 'ba', 'bca', 'bc','b', .....]이외도 만약에 2개 뽑았을 때의 순열, 3개뽑았을 때의 순열을 구하고 싶다면?
function permutation(arr, str, output) {
// 이쪽 숫자부분만 수정해주면 된다.
if (str.length === 2) {
output.push(str);
}
for (let i = 0; i < arr.length; i++) {
const copy = [...arr];
copy.splice(i, 1);
permutation(copy, str + arr[i], output);
}
}
let output = [];
permutation(['a', 'b', 'c'], '', output);
// console.log(output);
// [ 'ab', 'ac', 'ba', 'bc', 'ca', 'cb' ]const output = [];
const arr = ['a', 'b', 'c'];
function permutation(str, length){
}조합 (Combination) - nCm
순열 같은 경우는 뽑은 순서가 중요했지만, 조합에서 순서는 중요한 개념이 아닙니다.
예를 들어 순열에서는 [1,3,5], [3,1,5], [5,1,3], [1,5,3]...는 다른 가지 수로 평가하지만, 조합에서는 1가지로 평가됩니다.
Input: [1, 2, 3, 4]
Output: [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ]만약 위와 같이 4C3인 경우를 구한다면 어떻게 구해야할까요?
조합 구현 의사코드
- 4개의 선택지 중, 3개만 선택한다면
- 1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
[1, 2, 3] [1, 2, 4] [1, 3, 4] - 2를 선택(고정)하고 -> 나머지 [3, 4] 중에서 2개씩 조합을 구한다.
[2, 3, 4] - 3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다.
[ ] - 4을 선택(고정)하고 -> 나머지 [ ] 중에서 2개씩 조합을 구한다.
[ ]
- 1을 선택(고정)하고 -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구한다.
배열의 처음부터 하나씩 선택(고정)하면서 뒤의 나머지의 배열에 대해서 조합을 구해서 붙이면 됩니다.
조합 함수 코드
function combination(arr, selectNumber) {
const result = [];
if (selectNumber === 1) return arr.map(el => [el]);
// n개중에서 1개 선택할 때(nC1), 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1);
// 해당하는 fixed를 제외한 나머지 뒤
const restCombination = combination(rest, selectNumber - 1);
// 나머지에 대해서 조합을 구한다.
const attached = restCombination.map(el => [fixed, ...el]);
// 돌아온 조합에 떼 놓은(fixed) 값 붙이기
result.push(...attached);
// 배열 spread syntax 로 모두다 push
});
return result; // 결과 담긴 results return
}
// console.log(combination([1, 2, 3, 4], 3));
// [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]