[Algorithm] 완전 탐색 - 중복순열

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

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

 

 

완전 탐색

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

 

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

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

 

완점 탐색 종류

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

 

완전 탐색 문제 접근 시

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

 

N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 

 

백준 15651) N과 M (3)  https://www.acmicpc.net/problem/15651

15651번: N과 M (3)

1부터 N까지 자연수 중에서 중복을 허용하여 M개를 골라 순서 있게 나열하기

 

1) 아이디어

N = 3, M = 2일 때 매 자릿 수마다 재귀호출로 모든 경우의 수를 탐색한다

 

2) 시간 복잡도 계산

N = 3, M = 2일 때 

 

        ___ ___    2 자리를 중복 없이 고르는 거니까 3 * 3 = 9

 

시간 복잡도 : O(N^M)

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

 

3) 구현

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[] selected;

    // 만약 M개를 전부 고름 -> 조건에 맞는 탐색을 한 가지 성공한 것!
    // 아직 M개를 고르지 않음 -> k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법 시도
    static void rec_func(int k) {
        if (k == M + 1) { // M개수만큼 다 고르면 등록
            for (int i = 1; i <= M; i++) {
                sb.append(selected[i]).append(' ');
            }
            sb.append('\n');
        } else {

            // 1~N 까지를 k번 원소로 한번씩 정하고,
            // 매번 k+1 번부터 M번 원소로 재귀호출 해주기
            for (int cand = 1; cand <= N; cand++) {
                selected[k] = cand;

                rec_func(k + 1);
                selected[k] = 0;
            }
        }
    }

    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());

        selected = new int[M + 1];

        rec_func(1);
        System.out.println(sb.toString());
    }

}

 

N = 3, M = 2일 때