[ 자바스크립트(JavaScript) ] section08 - 15 - 수들의 조합
📍 section08 - 15 - 수들의 조합 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개인지 출력하는 문제다. 예를 들면, 5개의 숫자 arr=[2, 4, 5, 8, 12]로 주어지면 3를 뽑는 조합의 합이 6의 배수인 값은 [2, 4, 12] (18), [ 4, 8, 12 ] (24)로 총 2개가 있다. 이 문제를 풀기 위해선 n개의 정수를 뽑는 모든 경우의 수(조합)를 구하고, 조합의 합을 m으로 나눈 나머지가 0인 값을 찾으면 된다. 조합을 구현하는 방법은 다음을 참고하자. 내가 문제를 풀 때는 DFS함수에 인자를 L, s만 넘기고 L===k일 때 reduce 함수를 이용하여 더했는데, 그것보단 DFS에 sum 인자를 하나 더 넘겨서 L이 ..
2021. 10. 5.
[ 논리적사고 ] - 재귀를 이용하여 부분 집합, 순열, 조합 구하기
📍 재귀를 이용하여 부분 집합, 순열, 조합 구하기 코딩테스트 문제를 풀다 보면 제목과 같이 부분집합(subSet), 순열(permutation), 조합(combination)을 구해야 하는일이 간혹 있다. 그때마다 코드를 구현하려니까 시간이 부족해서 다른 부분에 시간을 쏟지 못한 적이 있었다. 어떻게 구현해야 하는지 간단하게 알아보자. arr=[1, 2, 3, 4]로 예를 들어 나올 수 있는 경우의 수를 구해보는데, 모두 재귀(DFS)를 이용하여 구했다. 부분집합은 출력하는 모든 경우의 수를 구하고, 순열은 중복을 허용 / 허용하지 않고 일렬로 세우는 방법, 조합은 4개 중 2개를 뽑는 경우의 수로 가정해서 구했다. 이를 응용한 문제는 다음을 참고하자. 부분집합: 부분집합 구하기, 바둑이 승차, 최대점..
2021. 10. 1.
