자바스크립트로 Combination (조합) 만들기 (feat.재귀함수)

중학교였는지 고등학교였는지는 기억 안나지만 수학에서 조합이라는것을 배운다.

 

값이 1,2,3 이렇게 있으면 [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] 이딴식으로 조합이 나오는데

 

개발을 하다보면 가끔씩 한번쯤은 이걸 활용할 때가 있다. (옵션 고르는 체크박스를 표현할때 등...)

 

이걸 자바스크립트로 한번 만들어보자.

 

function combination(arr, selectNum) {
	const result = [];
	if (selectNum === 1) return arr.map((el) => [el]);
	arr.forEach((el, idx, arr) => {
		const restArr = arr.slice(idx + 1);
		const combinationArr = combination(restArr, selectNum - 1);
		const combineFix = combinationArr.map((el2) => [el, ...el2]);
		result.push(...combineFix);
	});
	return result;
}

 

코드만 보면 뭔가 복잡한데 하나하나 뜯어보자.

---

function combination(arr, selectNum) {

 

일단 조합을 만들 배열(arr)과 조합요소의 수(selectNum)를 파라미터로 지정한다.

ex) combination([1,2,3], 2) => [[1,2], [1,3], [2,3]]

 

function combination(arr, selectNum) {
	const result = [];

 

그 다음 결과값을 담을 배열을 만들어주고

 

function combination(arr, selectNum) {
	const result = [];
	if (selectNum === 1) return arr.map((el) => [el]);

 

만약 조합요소의 수를 1로 설정했다면, 그대로 요소들을 각자 배열로 감싸서 반환한다. 굳이 조합만들 필요 없자너~

 

function combination(arr, selectNum) {
	const result = [];
	if (selectNum === 1) return arr.map((el) => [el]);
	arr.forEach((el, idx, arr) => {
		const restArr = arr.slice(idx + 1);

 

여기부터 잘 봐야한다.

 

주어진 배열을 forEach 함수로 순회하는데

restArr이라는 새로운 배열을 만들어서 slice() 메서드로 앞에서부터 하나씩 잘라준다.

arr.slice(idx + 1) 에서 "idx + 1" 을 하는이유는 slice()의 인수가 0이면 배열을 안자르고 그대로 반환하기 때문이다.

 

function combination(arr, selectNum) {
	const result = [];
	if (selectNum === 1) return arr.map((el) => [el]);
	arr.forEach((el, idx, arr) => {
		const restArr = arr.slice(idx + 1);
		const combinationArr = combination(restArr, selectNum - 1);

 

그 다음 combinationArr 이라는 배열을 또 만들어서 combination 함수를 호출하여 그 결과값을 저장한다....

 

Q : 엥? 지금 combination 함수를 만들고 있는거 아닌가요?

A : 맞습니다. 우리는 이걸 재귀함수라고 부르기로 했어요.

 

재귀함수란 함수 내부에서 자신을 다시 호출하는 함수를 의미한다.

 

재귀함수 실행 시 함수 내부에서 자신을 다시 호출함으로써 진행중이던 함수 실행정보를 메모리(실행 컨텍스트)에 저장하고, 재귀가 반복될 경우, 실행 컨텍스트를 실행 컨텍스트 스택이라는 곳에 보관하게 된다. 이것을 스택이 쌓인다고 표현한다.

 

이러한 재귀는 조건이 만족할 경우 종료되는데, 만약 종료조건을 지정해주지 않으면 조건 없는 while문 처럼 무한루프를 돌게 되면서 그 유명한 스택오버플로우(그 사이트 이름 맞다.)가 발생하게 된다.

 

자세한 내용은 여기에서...

 

 

아무튼 다시 combination을 호출하면 restArr(맨 앞 요소 하나를 제거한 배열)과 조합요소의 수 - 1(selectNum - 1)을 인수로 주게되는데 기존에 호출한게 combination([1,2,3], 2) 였다면 재귀함수는 combination([2,3], 1)가 되는것이다.

 

하지만 아직 return 값이 없기때문에 함수를 호출해도 아무일도 일어나지 않는다.

일단 함수를 다 작성하고 보자.

 

function combination(arr, selectNum) {
	const result = [];
	if (selectNum === 1) return arr.map((el) => [el]);
	arr.forEach((el, idx, arr) => {
		const restArr = arr.slice(idx + 1);
		const combinationArr = combination(restArr, selectNum - 1);
		const combineFix = combinationArr.map((el2) => [el, ...el2]);
		result.push(...combineFix);
    	});
	return result;
}

 

재귀함수로 받은 배열값을 map()함수를 활용하여 또또 새로운 배열로 만들어 combineFix라는 변수에 저장한다.

 

여기서 map((el2) => [el, ...el2]) 에서 "..."는 스프레드문법(전개구문)이라는 것인데, 이터러블(순회가능한) 요소를 전부 꺼내놓는거라고 생각하면 된다. (그냥 배열 펼쳐놓는거임. 객체에도 사용가능함)

 

그리고 result 변수에 combineFix 배열을 스프레드문법으로 펼쳐서 집어넣고 return 한다.

 

---

 

이쯤되면 이해하기가 어려운데 (내가 쓰면서도 이해안됨), 지금까지의 과정을 쉽게 설명하자면,

 

1. 조합을 만들 배열과 조합요소 수를 지정한다.

2. arr.slice() 로 요소 하나를 빼놓고 (이 과정에서 조합을 만들 배열 크기가 1씩 줄어든다.)

3. 빼놓은 요소를 기준으로 해서 나머지 요소와 조합을 만들고

4. result 변수에 집어넣는다.

5. forEach문이 끝날때까지 이를 반복한다. (조합요소의 수 보다 배열의 크기가 작아질때까지... 배열의 크기가 조합요소의 수보다 작으면 조합 못만드니까!)

6. 반복문이 종료되면 result값을 반환한다.

 

 

이해하기 쉽지 않다. map 함수, 스프레드문법, 재귀함수에 대한 이해도가 있어야 해당 과정을 완벽하게 이해할 수 있을것이다.

나도 완벽히 이해하지 못했다. 그러니 글을 이따구로 쓰지ㅎㅎ

 

 

나는 이 함수를 응용해서 조합요소의 수를 지정하지 않고, 모든 조합을 뽑아서 문자열로 반환하는 함수를 만들어보았다.

ex) [1,2,3] => ['1', '2', '3', '1,2', '1,3', '2,3', '1,2,3']

 

function allCombination(arr) {
	const result = [];
	for (let i = 1; i <= arr.length; i++) {
		let temp_arr = combination(arr, i);
		for (let j = 0; j < temp_arr.length; j++) {
			let string = temp_arr[j].join(', ');
			result.push(string);
		}
	}
	return result;
}

---

 

자바스크립트는 공부하면 할 수록 어렵다...

 

이걸 보는 여러분이 나보다 훨씬 똑똑하니까 제가 잘못 설명한 부분이 있을 경우 댓글로 남겨주시면 감사하겠습니다😀