알고리즘 풀이 - 백준 15650(N과 M(2), 완전 탐색)

 

관련글

 

완전 탐색 관련 포스팅은 여기를 참조
백트래킹 관련 포스팅은 여기를 참조

관련 문제인 N과 M(1)은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

자연수 N, M이 주어질 때, 1 ~ N까지 자연수 중 중복 없이 M개를 고른 것 중 오름차순의 수열만 사전 순으로 모두 출력하는 문제

 

 

2. 풀이

 

이 문제는 백트래킹 관련 문제이다.(백트래킹은 상단 링크 포스팅 참조)

 

---

N과 M(1)에서 살펴보았던 내용은 다음과 같다.

 

N, M이 주어질 때, 중복하지 않도록 수를 고르고 사전 순으로 고른다는 것은 M개의 숫자로 이루어진 모든 부분 집합을 구하라는 의미이다.

여기서 몇 가지 해결을 위한 단서를 파악할 수 있다.

① 숫자를 M개 골랐다면 그 숫자를 출력해야 한다.
② 이미 고른 숫자를 다시 선택하지 않도록 구현해야 한다.
③ 사전 순으로 출력해야 하므로 1부터 N까지의 반복문을 사용하는 것이 좋다.

 

여기서, ①에 따라 우리는 숫자를 M개 고를 때까지 저장할 별도 공간을 마련하는 것이 좋다. 그렇지 않으면 불 필요한 상황에 출력될 수 있다.

②에 따라, 논리 배열을 생성하여 현재 숫자가 이미 선택되었는지 체크해야 하며, 완료 후에는 다시 선택할 수 있음을 설정해야 한다는 것을 알 수 있다.

코드를 통해 확인하는 것이 더욱 직관적이므로 코드를 확인하자.

---

 

여기서, 추가된 내용은 출력될 수열이 오름차순으로 이루어진 경우만이어야 하므로, 이미 고른 숫자를 기반으로 새로운 반복문을 시작하도록 구성하면 더 작은 숫자가 포함될 수 없게 할 수 있다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

import java.io.*;

public class Main{
    static int n;
    static int m;
    static StringBuilder sb;
    static boolean check[]; // 현재 확인한 숫자인지 체크
    static int[] num; // 수열 저장하는 배열
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        
        check = new boolean[n];
        num = new int[m];
        
        go(0, 1);
        System.out.println(sb);
        br.close();
    }
    
    // 반복 / 재귀로 백트래킹 방식 사용
    // start 값을 줌으로 인해서 이전의 숫자보다 더 작은 것이 들어가는 경우를 막음
    private static void go(int seq, int start){
        if(seq == m){
            for(int i : num){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // start부터 시작하여야 이전에 들어간 숫자보다 작은 것이 들어가지 않는다.
        for(int i=start; i <= n; i++){
            if(check[i-1]) continue;            
            check[i-1] = true;
            num[seq] = i;
            
            // 다음 시퀀스로 이동
            go(seq+1, i+1);
            
            check[i-1] = false;
        }
    }
}

 

 

4. 다른 방법으로 풀어보기

 

위 방식은 O(N!)의 시간복잡도를 요구한다. N개의 숫자 중 하나를 고르고, 그 뒤 N-1개의 숫자 중 하나를 골라 최종적으로 선택된 숫자들을 출력하는 방식이기 때문이다.

그런데, 여기서 우리는 M개의 숫자를 중복 없이 선택한다면, 그 선택된 숫자를 출력하는 방법은 딱 1가지임을 알 수 있다.

선택된 숫자를 오름차순으로만 표기해야 하기 때문에 만약, 1~7까지의 숫자 중 3개를 선택했는데 그것이 7 6 5라면 실제 출력은 5 6 7만 하면 되는 것이다. 다른 출력은 할 필요가 없다.

 

따라서, 우리는 이전의 숫자가 선택된 뒤, 그 이후에 모든 숫자 중 하나를 또 선택하는 것이 아니라, 각 숫자를 선택할지 안할지의 관점에서만 보면 된다.

이렇게 하면, N개의 숫자를 선택하거나 하지 않거나의 2가지가 되니 2x2x2x...x2 가 되어 총 시간복잡도를 $O(2^N)$으로 해결할 수 있게 된다.

참고로, $O(N!)$ 보단 $O(2^N)$이 훨씬 빠르다. $N!$은 1~N까지 N개의 숫자를 모두 곱해야 하는데, $2^N$은 2만 N번 곱하기 때문이다.

 

그러면 어떻게 코드로 구현할 수 있을지 알아보자.

 

import java.io.*;

public class Main{
    static int n;
    static int m;
    static StringBuilder sb;
    static int[] num; // 수열 저장하는 배열
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        
        String[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        m = Integer.parseInt(line[1]);
        
        num = new int[m];
        
        go(0, 1);
        
        System.out.println(sb);
        br.close();
    }
    
    
    // seq는 몇 개의 숫자가 선택되었는지를 알아내는 부분
    // idx는 현재 몇 번째의 숫자를 선택 / 미선택할 것인지를 채택하는 부분
    private static void go(int seq, int idx){
        if(seq == m){
            for(int i : num){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        // 아래에서 반복문이 사라진 것을 알 수 있음!
        // 이를 통해 재귀만 사용하여 해결하여 더 빠른 시간복잡도를 유지
        
        // 만약 계속 재귀를 통해 넘어가면 언젠간 n을 넘어가게 되니, 그 이후에는 바로 반환시킴
        if(idx > n) return; 
        
        // 현재 숫자를 선택하는 경우의 재귀 방식
        // 이후 다음 선택할 숫자로 넘어간다. 아래 2줄은 현재 idx 숫자를 선택하는 경우임
        num[seq] = idx;
        go(seq+1, idx+1);
            
        // 현재 숫자를 선택하지 않는 경우의 재귀 방식
        num[seq] = 0;
        go(seq, idx+1);
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.