2022/04/26) 14. 조합 구하기 [재귀함수와 완전탐색(DFS:깊이우선탐색)]

굥굥이·2022년 4월 26일
0

1. 문제

<조합 구하기>
: 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성한다.
(첫 번째 줄에 자연수 N과 M이 주어진다.)

2. 해결 방법

  1. 조합은 말 그대로 조합이다!! 순서를 신경쓰는 순열과 다르다! 순열에서 1,3과 3,1는 서로 다르지만, 조합에선 같다.
    그러므로 1,2 / 1,3 / 1,4 를 뽑았으면 2,3 / 2,4 그리고 3,4 이런 식으로 뽑아야 한다.
    여기서 규칙을 찾아보자. 1일 땐 1+1(2)부터 시작[2,3,4], 2일 땐 2+1(3)부터 시작[3,4], 3일 땐 3+1(4)부터 시작[4]한다. 그렇다면 for문에서 다시 함수(DFS)를 호출 시 L+1, i+1을 넘겨주면 되겠다는 걸 알 수 있다.
    D(L,s)에서 L은 level + tmp의 인덱스 위치, s는 for문을 어디서부터 돌릴지 시작점이다.
    i(for문)가 움직인다. i로 인해 값도 정해지고 시작점도 정해진다.

3. 정답

        <script>
            function solution(n, m){         
                let answer = [];
                let tmp = Array.from({length:m}, ()=>0);
                function DFS(L, s){ //D(1,2)가 들어옴
                    if(L===m){
                        answer.push(tmp.slice());
                    }else{
                        for(let i = s; i <= n; i ++){ //for문의 시작점이 정해지면 안됨. 그래서 s로 시작! i로 s의 값을 바꿀거다.
                            tmp[L] = i; 
                            DFS(L+1, i+1);
                        }
                    }
                }
                DFS(0, 1);
                return answer;
            }
            console.log(solution(4, 2));
        </script>
profile
아자아자 파이띵굥!

0개의 댓글