JavaScript
[JavaScript] 조합 알고리즘 코드 이해하기
hid1
2023. 5. 17. 19:10
const getCombinations = (arr, selectNumber) => {
const results = []
if (selectNumber === 1) return arr.map((value) => [value])
arr.forEach((fixed, index, origin) => {
const rest = origin.slice(index + 1)
const combinations = getCombinations(rest, selectNumber - 1)
const attached = combinations.map((combination) => [fixed, ...combination])
results.push(...attached)
});
return results
}
const result = getCombinations([1,2,3,4], 3)
console.log(result)
// [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]
조합을 사용할 때 검색해 본 결과 위와 같은 코드가 많이 사용되는 것 같아 가져왔다.
재귀함수를 사용하고 있어 처음 봤을 떄 한 번에 이해가 가지 않았다.
해당 함수는 조합을 뽑아낼 배열 arr와 몇 개를 택할지 넘겨주는 selectNumber를 인수로 받고 있다.
const getCombinations = (arr, selectNumber) => {
console.log("함수 시작 arr : ", arr, "selectNumber : ", selectNumber)
const results = []
if (selectNumber === 1) {
const results = arr.map((value) => [value])
console.log("selectNumber가 1: ", results)
return results
}
arr.forEach((fixed, index, origin) => {
console.log(`fixed : ${fixed}`)
const rest = origin.slice(index + 1)
const combinations = getCombinations(rest, selectNumber - 1)
const attached = combinations.map((combination) => [fixed, ...combination])
console.log("attached : ", attached)
results.push(...attached)
console.log("현재 results : ", results)
})
return results
}
const result = getCombinations([1,2,3,4], 3)
어떻게 하면 더욱 쉽게 이해할 수 있을까 고민한 결과 예시를 통해 과정을 보는 것이 좋다고 생각하였다.
콘솔로그를 찍고 결과를 비교적 보기 쉽게 정리하였다.
함수 시작 arr: [1, 2, 3, 4], selectNumber: 3
fixed : 1
함수 시작 arr : [2, 3, 4], selectNumber : 2
fixed : 2
함수 시작 arr : [3, 4], selectNumber : 1
selectNumber가 1 : [[3], [4]]
attached : [[2, 3], [2, 4]]
현재 results : [[2, 3], [2, 4]]
fixed : 3
함수 시작 arr : [4], selectNumber : 1
selectNumber가 1 : [[4]]
attached : [[3, 4]]
현재 results : [[2, 3], [2, 4], [3, 4]]
fixed : 4
함수 시작 arr : [], selectNumber : 1
selectNumber가 1 : []
attached : []
현재 results : [[2, 3], [2, 4], [3, 4]]
attached : [[1, 2, 3], [1, 2, 4], [1, 3, 4]]
현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4]]
fixed : 2
함수 시작 arr : [3, 4], selectNumber : 2
fixed : 3
함수 시작 arr : [4], selectNumber : 1
selectNumber가 1 : [[4]]
attached : [[3, 4]]
현재 results : [[3, 4]]
fixed : 4
함수 시작 arr : [], selectNumber : 1
selectNumber가 1 : []
attached : []
현재 results : [[3, 4]]
attached : [[2, 3, 4]]
현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
fixed : 3
함수 시작 arr : [4], selectNumber : 2
fixed : 4
함수 시작 arr : [], selectNumber : 1
selectNumber가 1 : []
attached : []
현재 results : []
attached : []
현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
fixed : 4
함수 시작 arr : [], selectNumber : 2
attached : []
현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
요점은 특정 값을 고정(fixed) 후 나머지 값들의 조합을 구하고 마지막에 고정된 값을 포함시키면 된다. [fixed, ...나머지 조합]
고정된 값이 제외하고 조합을 구해야하니 selectNumber를 1씩 줄이고 selectNumber가 1일 때 종료 조건을 설정한다.
fixed : 1
fixed : 2
selectNumber가 1: [[3], [4]]
attached : [[2, 3], [2, 4]] // fixed가 2 -> [2, ...[3]], [2, ...[4]]
현재 results : [[2, 3], [2, 4]]
fixed : 3
selectNumber가 1 : [[4]]
attached : [[3, 4]] // fixed가 3 -> [3, ...[4]]
현재 results : [[2, 3], [2, 4], [3, 4]]
fixed : 4
selectNumber가 1 : []
attached : []
현재 results : [[2, 3], [2, 4], [3, 4]]
attached : [[1, 2, 3], [1, 2, 4], [1, 3, 4]] // fixed가 1 -> [1, ...[2,3]] ...
현재 results : [[1, 2, 3], [1, 2, 4], [1, 3, 4]]
해당 값을 '고정한다'라는 표현보다 '무조건 포함한다'라는 표현이 이해하기엔 더 쉽다고 느꼈다.
'무조건 1을 포함시킨다'라고 가정하면 구해야할 조합의 수는 2
-> '무조건 2를 포함시킨다'라고 가정하면 남은 자릿수는 1, 남은 자릿수가 1이니 종료 조건 true
-> 2를 무조건 포함시켜야 하니 [2, ...나머지 조합] 리턴
-> 1를 무조건 포함시켜야 하니 [1,...나머지 조합] 리턴
또한 빈배열인 경우 map을 사용하면 빈배열이 리턴된다.
fixed가 4여도 배열에 아무것도 들어있지 않으니 [].map((value) => [4, ...value])의 결과는 []이다.
반응형