[알고리즘] 순열과 조합, 재귀함수 이해하기(JavaScript)
[알고리즘] 순열과 조합, 재귀함수 이해하기(JavaScript)
순열과 조합(Permutations and Combinations)
프로그래머스 Level 2 - 소수찾기 완전탐색 알고리즘 문제를 풀기 위해 순열과 조합 개념을 공부했는데 코드가 잘 이해되지 않았다.(재귀함수, 반복문이 섞이니까 더 어려웠던 것 같다.) 알고리즘 스터디원 분들과 고민하다보니 코드를 뜯어보며 호출 스택, 헷갈리는 JS 클로저 개념에 대해서도 이 문제를 통해 정리해야겠다는 생각이 들었다. 코드의 흐름을 도식으로 직접 그려보고 디버거를 활용함으로써 코드를 이해한 과정을 기록해본다.
본 포스팅은 JavaScript로 순열과 조합 알고리즘 구현하기 문서를 이해한 것을 바탕으로 작성되었습니다.
조합(Combinations)
조합은 n개 중에 r개를 뽑는 경우의 수를 구할 때 순서를 고려하지 않는 개념이다.
4C3 = 4Combination3 은 4개 중에 3개를 선택하는데 ‘조합’으로 나올 수 있는 경우의 수를 구한다는 말이다. 코드로 생각해보면 다음과 같다.
Input: [1,2,3,4]
Output: [ [1,2,3], [1,2,4], [1,3,4], [2,3,4] ]
조합에서는 순서를 고려하지 않기 때문에 [1,2,3] = [3,2,1] 이렇게 순서가 달라도 ‘같은’ 경우의 수로 취급한다.
조합 코드 in JavaScript
조합을 자바스크립트 코드로 구현해보자. [1,2,3,4] 중에 3개를 조합으로 뽑는 위 예시를 아래와 같은 방식으로 구할 수 있다.
시작
1을 선택(고정)하고 -> 나머지 [2,3,4] 중에서 2개씩 조합을 구한다. 그리고 그 각각을 고정했던 1에 이어붙인다.
[1,2,3], [1,2,4], [1,3,4]
2를 선택(고정)하고 -> 나머지 [3,4] 중에서 2개씩 조합을 구한다. 그리고 그 각각을 고정했던 2에 이어붙인다.
[2,3,4]
3을 선택(고정)하고 -> 나머지 [4] 중에서 2개씩 조합을 구한다.
[]
4을 선택(고정)하고 -> 나머지 [] 중에서 2개씩 조합을 구한다.
[]
종료
이렇게 배열의 처음부터 하나씩 선택(고정)하면서 뒤의 나머지 배열에 대해서 조합을 구해 고정된 요소에 붙이면 된다. 나머지 배열에 대해 조합으로 경우의 수를 구할 때는 재귀(Recursion) 함수를 사용하면 된다. 왜냐하면 계속 반복될 일(조합을 구하는 일)에 재귀함수를 이용하면 들어가는 인자만 바꿔주면 되기 때문이다.
다음은 구현한 코드에 대한 자세한 설명이다.
- 재귀 종료 조건: 한 개를 선택할 땐, 모든 배열의 원소를 하나씩 선택해 배열로 리턴한다.
- forEach문으로 배열의 모든 원소를 처음부터 끝까지 한번씩 고정(fixed)되게 한다.
- 고정(fixed)된 값을 제외한 나머지 뒤 배열에 대해서 조합을 구한다. 이 때 선택하는 개수를 하나씩 줄여간다.
- 이렇게 조합을 만들어온 결과에 고정(fixed)된 값을 앞에 붙이고, 전개 구문(spread syntax)을 사용해 리턴할 배열에 넣는다.
- 1C2 처럼 배열 원소수보다 선택하려는 개수가 더 많은 경우에는 빈 배열이 리턴되기 때문에 최종 결과값에 포함되지 않는다.
const getCombinations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1); // 해당하는 fixed를 제외한 나머지 뒤
const combinations = getCombinations(rest, selectNumber - 1); // 나머지에 대해서 조합을 구한다.
const attached = combinations.map((combination) => [fixed, ...combination]); // 돌아온 조합에 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두 다 push
});
return results; // 결과가 담긴 results를 return
};
const arr = [1, 2, 3, 4];
const result = getCombinations(arr, 3);
console.log(result);
// => [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]
순열(Permutations)
순열은 n개 중에 r개를 뽑는 경우의 수를 구할 때 순서를 고려해 뽑는다. 이게 조합과의 차이점이다.
4P3 = 4Permutation3 은 4개 중에 3개를 선택하는데 ‘순열’으로 나올 수 있는 경우의 수를 구한다는 말이다. 조합에서처럼 코드로 생각해보면 다음과 같다.
Input: [1,2,3,4]
Output: [
[1,2,3],[1,2,4],[1,3,2],[1,3,4],[1,4,2],[1,4,3],
[2,1,3],[2,1,4],[2,3,1],[2,3,4],[2,4,1],[2,4,3],
[3,1,2],[3,1,4],[3,2,1],[3,2,4],[3,4,1],[3,4,2],
[4,1,2],[4,1,3],[4,2,1],[4,2,3],[4,3,1],[4,3,2]
]
순열 코드 in JavaScript
순열은 조합을 구하는 코드와 별반 다르지 않게 구현할 수 있다. [1,2,3,4] 중에 3개를 순열로 뽑는 예시를 의사코드로 생각해보자.
1(fixed) -> permutation([2,3,4]) -> 2(fixed) -> permutation(3,4) -> ...
2(fixed) -> permutation([1,3,4]) -> 1(fixed) -> permutation(3,4) -> ...
3(fixed) -> permutation([1,2,4]) -> ...
4(fixed) -> permutation([1,2,3]) -> ...
조합과 다른 점은 배열의 처음부터 선택(고정)하면서 나머지 배열을 구할 때 고정된 값 뒤에 있는 값들에 대해서 순열을 구하는게 아니라, 고정된 값을 제외한 모든 원소에 대해서 순열을 구해야 한다는 것이다.
조합 코드에서 나머지 배열을 구하는 코드만 다음과 같이 바꾸면 된다.
const rest = [...origin.slice(0, index), ...origin.slice(index+1)] // 해당하는 fixed를 제외한 나머지 배열
const getPermutations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((value) => [value]); // 1개씩 택할 때, 바로 모든 배열의 원소 return
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)]; // 해당하는 fixed를 제외한 나머지 배열
const permutations = getPermutations(rest, selectNumber - 1); // 나머지에 대해 순열을 구한다.
const attached = permutations.map((permutation) => [fixed, ...permutation]); // 돌아온 순열에 대해 떼 놓은(fixed) 값 붙이기
results.push(...attached); // 배열 spread syntax 로 모두다 push
});
return results; // 결과 담긴 results return
};
const arr = [1, 2, 3, 4];
const result = getPermutations(arr, 3);
console.log(result);
// => [
// [ 1, 2, 3 ], [ 1, 2, 4 ],
// [ 1, 3, 2 ], [ 1, 3, 4 ],
// [ 1, 4, 2 ], [ 1, 4, 3 ],
// [ 2, 1, 3 ], [ 2, 1, 4 ],
// [ 2, 3, 1 ], [ 2, 3, 4 ],
// [ 2, 4, 1 ], [ 2, 4, 3 ],
// [ 3, 1, 2 ], [ 3, 1, 4 ],
// [ 3, 2, 1 ], [ 3, 2, 4 ],
// [ 3, 4, 1 ], [ 3, 4, 2 ],
// [ 4, 1, 2 ], [ 4, 1, 3 ],
// [ 4, 2, 1 ], [ 4, 2, 3 ],
// [ 4, 3, 1 ], [ 4, 3, 2 ]
// ]
순열 코드의 이해
처음엔 순열 코드를 보고 이해를 한 줄 알았다. 그런데 코드를 따라가며 다시 살펴보니 어떻게 동작하는지 헷갈리기 시작했다. 반복되는 재귀함수와 반복문이 머리에 둥둥 떠다녔다.(…) 호출스택을 도식으로 그리고, 디버거로 변수의 값을 확인해가며 코드를 다시 살펴보기로 했다.
우선 최초에 getPermutations() 함수가 호출된 이후 forEach의 첫 번째 반복을 자세히 살펴보자.
재귀의 종료 조건은 selectNumber === 1이기 때문에 그림에서 파란 표시가된 getPermutations은 코드에서 if문을 만나 리턴된다.
그리고 여기서 리턴된 [[3],[4]]는 빨간 표시가 된 forEach문에서 permutations 변수에 담긴다. 이후 attached, results에 대한 코드가 차례로 실행된다.
빨간표시가 된 forEach문 안에는 selectNumber 변수가 없다. 그런데 재귀적으로 getPermutations()함수를 호출할 때 어떻게 selectNumber를 참조해 인자를 넘겨줄 수 있었던 걸까?
그건 자바스크립트의 스코프체인 때문이다. 자바스크립트에서는 함수가 선언될 당시를 기준으로 스코프가 정해진다.(렉시컬 스코핑) forEach()가 선언될 당시 forEach() 겉의 스코프는 forEach()를 감싸고 있는 getPermutations의 스코프이다. 자신의 스코프에 해당 변수가 없는 경우 겉의 스코프를 따라 올라가며 변수를 찾는다. 위 forEach문에서는 getPermutations([2,3,4], 2)(빨간 박스 아래 검은 박스) 스코프의 selectNumber를 참조하게 된다.(이 때 selectNumber값은 2) 따라서 forEach() 내부에서 이 값이 다음과 같이 사용된다. getPermutations([3,4], 2-1) forEach()는 selectNumber라는 이름을 가진 지역변수가 자신의 스코프에 없기 때문에 외부 변수를 참조하므로 클로저라 볼 수 있다.
이제 위 그림에서 빨간박스의 forEach문을 마저 돌아야한다.
빨갛게 표시된 forEach()의 이번 반복을 통해 results 배열에 [3,2],[3,4]가 추가되었다.
빨갛게 표시된 forEach()의 이번 반복을 통해 results 배열에 [4,2],[4,3]가 추가되었다.
드디어 위에서 봤던 forEach문이 끝나고 getPermutations 스택으로 돌아와 results를 return 한다.
이전 그림에서 return된 배열이 permutations 변수에 저장되고 attached를 거쳐 results 배열에 결과가 추가된다.
이제 그림에서 빨갛게 표시된 forEach()문의 다음 반복이 이어진다.(forEach(2,1,[1,2,3,4])) 지금까지 설명한 과정이 반복될 것이기에 설명은 생략한다. 이렇게 초기에 인자로 줬던 [1,2,3,4]를 돌며 빨갛게 표시된 forEach문은 총 네 번 반복된다.
이런식으로 반복하다가 결국 아래 그림처럼 results 변수에 순열을 이용한 모든 경우의 수가 담기게 된다.
궁금증
- ES6+ 부터는 for loop와 같은 블록도 실행 컨텍스트를 생성하기 때문에 호출 스택에 쌓이는 걸로 이해했다(확실x)
- 외부 변수를 사용하는 주체는 클로저라 볼 수 있다(확실x) MDN 클로저 문서 첫 코드를 보면 맞는 말 같기도 함(정확히 확인 필요)
- const, let은 블록 스코프를 따른다.
- 함수 선언시 스코프가 정해진다.(렉시컬 스코핑)
