[Algorithm] 완전탐색 - 중복조합

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다.

출처 : https://github.com/rhs0266/FastCampus

 

 

완전 탐색

문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다.

 

장점 : 부분 점수를 얻기 좋음

단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음

 

완점 탐색 종류

• N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 
• N개중 중복없이 M개를 순서 있게 나열하기 : 순열
• N개중 중복을 허용하여 M개를 고르기 : 중복조합
• N개중 중복없이 M개를 고르기 : 조합

 

완전 탐색 문제 접근 시

• 고를 수 있는 값의 종류 파악
• 중복 여부
• 순서를 따지는 지

 

N개중 중복을 허용하여 M개를 고르기 : 중복조합

 

 

백준 15652) N과 M (4) https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

 

1) 아이디어

 

중복 순열(N과 M(1)) 문제와 비슷하게 백트래킹으로 모든 경우의 수를 탐색한다.

단, 순서없이 고르기만 하는 중복 조합이므로 a, b와 b, a는 같은 케이스이므로 1부터 탐색한다고 했을 때 k+1의 자리값은 k 자리값보다 크도록 k 자리값인 prev 변수를 넘겨주어 다음 선택지에서 prev보다 큰 케이스만 고려할 수 있도록 한다.

 

 

2) 시간 복잡도 계산

 

중복 순열의 시간 복잡도 O(N^M)보다 시간복잡도가 낮으므로 가능하다

 

N과 M의 최대값이 8이니까 8^8 < 1억(10^8 )

 

 

3) 구현

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, M;
    static int[] selected;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // M개 고를건데 편의상 1부터 할거라서 M+1로 잡아둠
        selected = new int[M + 1];

        // 중복조합 구하는 재귀 호출
        rec_func(1, 1);

        bw.close();
    }

    private static void rec_func(int k, int prev) throws IOException {
        // 한 케이스에 대해서 M개 다 골랐으면
        if (k == M + 1) {
            for (int i = 1; i <= M; i++) {
                bw.write(selected[i] + " ");
            }
            bw.write("\n");
        } else {
            // k+1 자리값은 k 자리값보다 커야하니까 k 자리값을 prev로 넘겨준다
            for (int i = prev; i <= N; i++) {
                // 선택
                selected[k] = i;

                // k+1 자리 모든 경우 탐색, k자리 값 넘겨주기
                rec_func(k + 1, i);

                // 다음 케이스를 위한 초기화
                selected[k] = 0;
            }

        }
    }


}