💜순열(Permutation)
순서가 있는 정렬을 만드는 경우의 수
순열을 만드는 자연스런 방법 속에서 우린 재귀적으로 한 행동이 반복되는 것을 알 수 있다.
바로 배열 중 한 원소를 뽑고, 그 이후 나머지 원소들이 다음 뽑힐 수 있는 후보로 넘겨주는 것
위 그림에서 빨간색으로 표시한 1, 2, 3 은 같은 로직이 반복되고 있다.
➡ 이를 재귀함수로 구현 할 수 있다!
종료, 즉 재귀 탈출 조건은 잔여 배열의 길이가 0이거나, 선별배열의 길이가 원본배열과 같을 때로 한다.
💜함수로 나타낸 순열
const permutation = (permu, rests, output) => {
if (rests.length === 0) {
// 잔여 배열의 길이가 0이면 재귀 탈출
return output.push(permu);
}
// 잔여 배열이 남아 있으면 새로운 잔여 배열 만들어서 재귀 호출
rests.forEach((v,idx) => {
const rest = [...rests.slice(0,idx), ...rests.slice(idx+1)]
permutation([...permu,v], rest, output);
})
}
const output = [];
permutation([], ['a','b','c','d'], output);
console.log(output);만약, 원소를 모두 나열한 것이 아닌 특정 n개 원소의 순열을 원한다면,
위 코드에서 종료조건을 수정해주면 순열에 길이를 특정할 수 있다.
종료 조건이 rests.length === 1 일 경우,
잔여배열이 1이 되면 재귀를 멈추기 때문에 전체 배열 길이 - 1에 해당하는 길이의 순열을 얻을 수 있다.
💜조합 (Combination) - nCm
간단히 말하면 순열에서 지닌 요소가 같은 배열을 중복 제거한 것.
즉, 순열과 달리 순서를 중요하게 생각하지 않는 것.[a, b, c]=[b, a, c]
🔹순열의 경우
[a,b,c,d] 에서
a 를 선택하면 [b,c,d]가 잔여 배열
b를 선택하면 [a,c,d] 가 잔여 배열
🔹조합에 경우
[a,b,c,d] 에서
a를 선택하면 [b,c,d]가 잔여 배열로 남고
이 단계에서 b를 선택하면 [c,d]가 잔여배열이 된다.
마찬가지로 해당 단계에서 c를 선택할 시 [d] 만을 잔여배열로 남긴다.
즉, 순열에서 [a, b, c]와 [b, a, c] 는 다르게 인식하지만 조합에서는 동일한 배열로 본다.
💜함수로 나타낸 조합
const combination = (comb, rests, output) => {
if (comb.length == 0) {
return output.push(comb);
}
rests.forEach((v,idx) => {
// 잔여배열을 선별된 원소의 인덱스 뒤 부분을 잔여배열로 재정의
const rest = rests.slice(idx+1);
combination([...comb,v], rest, output);
})
}
const output = [];
combination([], ['a','b','c','d'], output);
console.log(output);문제에 적용해서 직접 풀어보기
Q. 소수 찾기
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
풀이
-
사실 이 문제를 처음 접했을 때는 순열 알고리즘에 대해 잘 몰랐어서 어떻게 모든 경우의 수를 구할 지 막막해서 반복문 쓰고 if문 쓰면서 끙끙대다가 결국 해답을 보고 이해하는 식으로 공부했다.
-
이 문제를 통해서 완전 탐색 시 순열을 적용해서 푸는 문제 형식을 익힐 수 있었다.
이 문제에서 순열이 쓰이는 이유
➡ 숫자가 적힌 문자열 numbers의 조각들로 만들 수 있는 모든 경우의 수를 구해서 각각의 경우가 소수인지 아닌지 판별해야하기 때문!
function solution(numbers) {
let answer = [];
let strToArr = [...numbers];
// 소수인지 판별하는 함수
const isPrime = (num) => {
// 0이거나 1이면 false 반환
if(num <= 1) return false;
// 반복문 최적화를 위해 제곱근까지만 반복
for(let i = 2; i * i <= num; i++){
if(num % i === 0){
return false
}
}
return true
}
const permutation = (fix, rest) => {
// 잔여 배열의 길이가 1이상일 때 까지만 반복
if(rest.length >= 1){
// 한개의 fix 문자에 대해 잔여 배열만큼 for문 돌면서 경우의 수 세기
for(let i = 0; i < rest.length; i++){
// 새로운 fix문자는 잔여 배열의 각각 요소
const newFix = fix + rest[i];
// 새로운 잔여 배열은 fix에 붙여준 요소 제외한 다른 요소들
const newRest = [...rest];
// i 인덱스부터 1개의 값 제거한 배열
// 즉 fix에 새로 붙여준 요소 제거한 배열!
newRest.splice(i, 1);
if(!answer.includes(+newFix) && isPrime(+newFix)){
// 만약 정답 배열에 없는 값이면서 소수면 정답 배열에 넣어주기
// 이때 + 붙여서 숫자화 해주기!
answer.push(+newFix)
}
// 새로운 fix 문자열과 잔여 배열로 재귀 실행
permutation(newFix, newRest)
}
}
}
permutation("", strToArr);
return answer.length
}참고 사이트
