[AL] 조합과 순열 - JavaScript
알고리즘 문제를 풀다보면 조합과 순열을 활용해서 푸는 문제가 정말정말정말 많이 나온다. 나도 문제 풀때마다 정리해둔 순열과 조합 코드를 보면서 문제에 맞게 고치는 방식으로 풀고 있는데, 그 코드를 세세하게 정리 해보려고 한다. (조합과 순열의 정의, 이론보단 코드에 집중!)
참고 자료
조합 (Combination)
순서를 따지지 않고 가능한 모든 경우의 수를 만드는 것
순서를 따지지 않는다 ➡ 예를 들어 [1, 3, 4]
와 [4, 1, 3]
이라는 두 경우가 있을 때 각 경우의 값은 전부 같지만 순서만 다르게 배열되어 있는 것이므로 같은 경우로 친다는 뜻
구현 코드
const getCombination = (arr, cnt) => { // 1.
const results = [];
if(cnt === 1) return arr.map((v)=>[v]); // 2.
arr.forEach((fixed, index, origin) => { // 3.
const rest = origin.slice(index+1); // 4.
const combinations = getCombination(rest, cnt-1); // 5.
const final = combinations.map((c)=>[fixed, ...c]); // 6.
results.push(...final); // 7.
});
return results;
}
코드 설명
-
조합을 생성할 배열
(arr)
과 조합의 길이를 결정하는(cnt)
를 매개변수를 받는다. -
만약 생성할 조합의 길이가 1 이라면 전달받은 배열을 그대로 return 한다.
-
forEach문을 사용하여 배열의 모든 원소들이 한번씩 고정되게 한다.
⚡ forEach문의 각각이 의미하는 것 (출처)
fixed : 처리할 현재 요소
index : 처리할 현재 요소의 인덱스
origin : forEach()를 호출한 배열 -
고정된 값을 제외한 그 뒤 나머지 값들을 담은 배열
-
위에서 구한 나머지 배열을 이용하여 길이가 하나 줄어든 조합들을 구한다.
-
기존에 고정한 값 + 위에서 구한 조합들을 합쳐 최종 조합 배열을 생성한다.
-
최종 결과를 담는 배열에 push 한다.
순열 (Permutation)
순서를 따지면서 가능한 모든 경우의 수를 만드는 것
순서를 따진다 ➡ 조합과는 반대로 [1, 3, 4]
와 [4, 1, 3]
를 다르게 보아 다른 경우로 친다는 뜻
구현 코드
const getPermutations = (arr, cnt) => { // 1.
const results = [];
if(cnt === 1) return arr.map((v)=>[v]); // 2.
arr.forEach((fixed, index, origin) => { // 3.
const rest = [...origin.slice(0,index), ...origin.slice(index+1)]; // 4.
const permutations = getPermutations(rest, cnt-1); // 5.
const final = permutations.map((p)=>[fixed, ...p]); // 6.
results.push(...final); // 7.
});
return results;
}
코드 설명
거의 모든 코드가 조합의 코드와 똑같지만 딱 한줄의 코드만 다르게 구현된다.
const rest = [...origin.slice(0,index), ...origin.slice(index+1)];
조합의 경우에는 고정된 값을 제외한 그 뒤 나머지 값들을 담은 배열 을 이용하여 나머지 조합을 구하는 방식으로 구현했었지만 !
순열의 경우에는 순서를 따지기 때문에 고정된 값을 제외한 그 앞의 값들 + 그 뒤 나머지 값들을 담은 배열을 생성하게 된다.
Author And Source
이 문제에 관하여([AL] 조합과 순열 - JavaScript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jminkyoung/AL-순열과-조합-JavaScript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)