코딩테스트 문제를 풀어보며 순열과 조합등을 이용해야하는 문제들을 자주 만났다.
그럴 때마다 구현 방법을 자주 잊어 블로그 포스팅을 통해 정리해보자.
순열 (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! = 6개의 경우의 수가 있음
어떤 배열이 주어질 때, 배열 내의 원소들의 순열조합을 반환하는 함수를 구현해보자.
먼저 순열을 나열하기 위해선 순차적으로 [a,b,c] 중 첫번째 오는 원소를 고르고, 그 이후 두번째 오는 원소를 배열 속 나머지 원소 중 골라야한다. 이후 세번째 오는 원소는 아직 선별되지 않은 원소 중 하나를 또 골라야한다.
순열을 만드는 자연스런 방법 속에서 우린 재귀적으로 한 행동이 반복되는 것을 알 수 있는데, 배열 중 한 원소를 뽑고, 그 이후 나머지 원소들이 다음 뽑힐 수 있는 후보로 넘겨주는 것이다.
그림으로 나타내면 다음과 같다.
잔여 배열에 원소를 하나씩 조회하며 선별 배열에 두고 -> 남겨진 잔여배열을 초기에 원본배열이라 생각하면, 규칙이 보이기 시작할 것이다.
빨간색으로 표시한 1, 2, 3 은 같은 로직이 반복되고 있다. 이를 재귀함수로 구현 할 수 있고, 종료조건은 잔여 배열의 길이가 0이거나, 선별배열의 길이가 원본배열과 같을 때로 한다.
순열 의사코드
- 선별배열은 빈배열, 잔여배열을 원본배열로 생각한다.
- 잔여배열 내의 원소를 하나씩 순회하며.forEach(value =>
- 선별배열에 조회된 원소(value) 를 넣는다.
- 잔여배열을 선별된 원소가 제외된 잔여배열로 재정의한다.
- 1-2 까지의 과정을 하나의 함수로 만들어 재귀함수를 호출한다. 새로운 선별배열, 잔여배열을 인자로 받도록한다!
- 만약 잔여배열이 하나도 남지 않게 된다면, 재귀호출을 종료 하고 조회가 가능하도록 외부 output 배열에 기록한다.
그대로 한 종료지점까지 따라가 보면
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] => 순열 넷 완성
......요런 방식으로 모든 순열의 조합들을 output으로 출력하는 것이 가능하다.
순열 함수 코드
//순열 구하기
const permutation = (permu, rests, output) => {
if (rests.length == 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);- 잔여 배열에 해당하는 것이 매개변수
rests이며 선별 배열에 해당하는 것이 매개변수permu이다.
console.log(output); 의 결과값
만약, 원소를 모두 나열한 것이 아닌 특정 n개 원소의 순열을 원한다면, 위 코드에서 종료조건을 수정해주면 순열에 길이를 특정할 수 있다.
종료 조건이 rests.length == 1 일 경우,
잔여배열이 1이 되면 재귀를 멈추기 때문에 전체 배열 길이 4-1에 해당하는 길이의 순열을 얻을 수 있다.
조합 (Combination) - nCm
조합에 경우 이전 순열에 코드에서 한부분만 변형 시켜주면 간단히 구현 할 수 있다.
이 둘에 차이는 잔여 배열을 남기는 방법에서 있는데,
순열에 경우 [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,d 나 b,a,c,d 를 동일하게 보기 때문에 (순서가 중요하지 않음) b를 뽑은 조합에 경우 a를 잔여배열로 남기지 않을 경우 [a,b,c,d] 와 [b,a,c,d] 등에 중복된 경우에 수를 제거할 수 있다.
조합의 의사코드
- 선별배열은 빈배열, 잔여배열을 원본배열로 생각한다.
- 잔여배열 내의 원소를 하나씩 순회하며.forEach(value =>
- 선별배열에 조회된 원소(value) 를 넣는다.
- 잔여배열을 선별된 원소의 인덱스 뒤 부분을 잔여배열로 재정의한다.
- 1-2 까지의 과정을 하나의 함수로 만들어 재귀함수를 호출한다. 새로운 선별배열, 잔여배열을 인자로 받도록한다!
- 만약 선별된 배열이 특정 length를 달성 시, 재귀호출을 종료 하고 조회가 가능하도록 외부 output 배열에 기록한다.
조합 함수 코드
const combination = (comb, rests, output) => {
if (comb.length == 0) {
return output.push(comb);
}
rests.forEach((v,idx) => {
// const rest = [...rests.slice(0,idx), ...rests.slice(idx+1)]
const rest = rests.slice(idx+1);
combination([...comb,v], rest, output);
})
}
const output = [];
combination([], ['a','b','c','d'], output);
console.log(output);