알고리즘 특강 3일차 : 백트래킹

k개 중에 n개의 수 뽑기 

 

k개 중에 2개를 뽑는 경우의 수를 고르면 

for(int i = 0;i<n-1;i++){
   for(int j = i+1; j<n;j++){
     System.out.println("%d %d \n", i,j);
     }
 }

이렇게 하면 된다. 하지만, 문제의 조건에서 k개를 뽑는 경우의 수를 구하라고 하면 정말 복잡해진다.

이럴 때는 재귀함수를 사용하면 된다.

 

완전탐색문제는 세가지를 유의해야 한다.

• 현재 상태를 의미하는 파라미터들
• 종료조건
• 재귀호출 완성

int[] ans;// 지금까지 고른 bit들

static void func(int num){
  if(num == n){
    for(int i =0 ;i<n;i++){
       System.out.printf("%d ",ans[i]); // 이진수가 다 만들어지면 출력
       }
    }
    else{
     for(int i = 0;i<2;i++){
       ans[num] = i; // num번 인덱스에 해당 i값 넣음
       func(num+1); // 다음 인덱스를 탐색하기 위해 재귀함수 호출
       }
       
     }
     
 }

위의 func함수에 num 파라미터를 입력받는 것은 지금까지 num-1번 인덱스까지 입력받았고, 앞으로 n-(num-1)번 인덱스에 들어갈 수를 탐색하겠다는 뜻이다. 

 

위 함수에서 만약 2진수가 아닌 5진수를 출력하고 싶다면 else안의 for문의 2를 5로 바꾸면 된다. 그리고 n을 2로 설정하면 2자리 2진수가 출력이 되고, 6으로 설정하면 6자리 이진수가 된다.

 

관련 문제 풀이이다.

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 두 수가 주어지면 차례대로 순열을 만들어서 출력하는 프로그램이다.

문제의 조건에 따라 따져야 할 것이 많은데, 이 문제는 중복을 허용하고, 오름차순, 내림차순에 대한 기준이 없다. 따라서 재귀함수에서 for문을 돌 때 현재 i의 값을 넘겨주지 않아도 되고(오름, 내림 x) , 현재 탐색하고 있는 i값의 방문여부도 상관하지 않아도 된다.

 

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




public class Main {

    
static int[] arr;
static int m;
static int n;
static StringBuilder sb;

static void print(){
    for(int i = 0;i<m;i++){
        sb.append(arr[i]).append(" ");
    }
    sb.append("\n");
}

static void make(int size){
    if(size == m){
        print();
    }

    else{
        for(int i = 1;i<= n;i++){
         
                arr[size] = i;
                make(size+1);
          

      }
    }
    
}


    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];

        make(0);

        System.out.println(sb);

    }
}

 

이를 응용한 문제도 풀어보았다.

https://www.codetree.ai/missions/2/problems/beautiful-number/submissions

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

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


public class Main {
    static int n;
    static int cnt = 0;
    static int[] arr;



    static void func(int num){
        if(num == n){
            cnt++;
        }
        else{
            for(int i = 1;i<=4;i++){
                if(num+i > n){
                     return;
                }
                else{
                    for(int j = 0;j<i;j++){
                        arr[num + j] = i;
                    }
                    func(num + i);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException{
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        func(0);
        System.out.println(cnt);

        
    }
}

이 문제는 입력받은 수 길이의 아름다운 수가 얼마나 있는지 계산하는 것이다.

1은 하나씩, 2는 두개씩, 3은 3개씩, 4는 4개씩 한번에 나타나야 한다. 이 문제는 위와 같은 방식이지만, 1,2,3,4를 한 덩어리로 생각해서 배열에 넣어주었다. 이 문제에서 한 덩어리의 수를 넣었을 때 배열을 벗어나는 경우에 대한 예외처리를 해야하는 것을 주의해야 한다.

 

k개중 하나를 n번 뽑기

 

 

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition-under-constraint?utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 이제까지 배운 내용과 거의 동일하게 하면 되지만, 특정한 수가 배열에서 연속 3번 이상 나오면 안된다는 조건이 있다. 이를 충족하기 위해서 배열에 수를 넣기 전에 바로 앞 배열의 수와 그 앞 배열의 수가 현재 탐색중인 수와 같은지 판단하고, 만약 같다면 넘어가는 과정이 추가되었다.

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


public class Main {
    static int n;
    static int m;
    static int[] arr;
  


    static void func(int num){ // 배열 만드는 함수
        if(num == n){ //n까지의 배열이 다 찼다면 
            for(int i =0;i<n;i++){
                System.out.printf("%d ",arr[i]); //출력
            }
            System.out.println();
            return;
        }
        else{//num 인덱스에 넣어야 할 수가 있다면 
            for(int i = 1;i<=m;i++){
                if(num < 2 || !(arr[num-1] == i &&arr[num-2] == i)){ //num이 2보다 작거나, 앞수와 그 앞수가 현재 탐색중인 수와 다를 때 배열에 수 추가
                    arr[num] = i;
                    func(num+1);
            }
        }
    }

  
}

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

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];

        func(0);

    }
}

 

 

n개 중에 m개 고르기

 

https://www.codetree.ai/missions/2/problems/n-choose-m?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 조합을 구해야 한다. 앞선 문제에서는 전부 숫자들의 순서, 중복 여부가 크게 중요하지 않았지만, 여기서는 숫자들이 오름차순으로 정렬되어야 하고 중복 되어서는 안된다.

 

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


public class Main {
    static int n;
    static int m;
    static int[] arr;
  


    static void func(int k, int num){ //k를 파라미터로 전달해서 for문의 시작점으로 정함
        if(num == n){
            for(int i =0 ;i<n;i++){
                System.out.printf("%d ",arr[i]);//배열이 모두 차면 출력
            }
            System.out.println();
        }
        else{
            for(int i = k;i<=m;i++){// 탐색중인 배열에 수 넣기(파라미터에서 받은 수부터 시작)
                arr[num] = i; 
                func(i+1,num+1);//다음 배열이 현재 수보다 커야하니까 i+1을 k에대한 파라미터로 전달
            }
        }
    }

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

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];

        func(1,0); // 첫 배열의 for문은 1부터 시작

    }
}

여기서는 func함수의 파라미터가 하나 추가된다. 이렇게 하면 현재 탐색중인 인덱스의 앞 인덱스보다 큰 수를 배정할 수가 없게 되어 자동적으로 오름차순 정렬이 된다. 또한 i+1을 k에 대한 파라미터로 전달함으로서 중복을 방지한다.

 

또한,

4자리 이진수	1-4에서 3개 뽑아 오름차순 정렬
0001	123
0010	124
0100	134
1000	234

이렇게 이진수로 만들고, 0의 위치를 출력하는 방법도 존재한다.

 

 

크기가 n인 순열

 

https://www.codetree.ai/missions/2/problems/n-permutation?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 수들을 중복 없이 뽑아서 사전순으로 세워 출력하는 것이다. 오름차순으로 정렬하는 위와 다르게 순서는 상관이 없으니, 위와 같은 방법으로 중복처리를 하면 안된다.

 그래서 중복을 방지하기 위해 boolean형의 배열을 만들어서 방문 여부를 체크한다. 우선, for문 안에서 배열에 수를 넣기 전에 넣을 수가 배열 안에 있는지의 여부를 판단하고, 만약 없으면 배열에 해당 수가 방문했다는 것을 표시하고, 배열에 수를 넣은 후 재귀함수를 호출한다. 위의 과정이 끝나면 더이상 배열에 해당 수가 남아있지 않으므로 boolean배열에 방문표시했던 것을 취소한다.

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


public class Main {
    static int n;
    static int m;
    static int[] arr;
    static boolean[] vis;
  


    static void func( int num){ //k를 파라미터로 전달해서 for문의 시작점으로 정함
        if(num == n){
            for(int i =0 ;i<n;i++){
                System.out.printf("%d ",arr[i]);//배열이 모두 차면 출력
            }
            System.out.println();
        }
        else{
            for(int i = 1;i<=n;i++){
                if(vis[i] == false){//현재 i의 방문여부 체크
                 vis[i] = true; //현재 i의 방문표시
                 arr[num] = i; 
                 func(num+1);//다음 배열이 현재 수보다 커야하니까 i+1을 k에대한 파라미터로 전달
                 vis[i] = false;//현재 i의 방문표시 취소
                }
               
            }
        }
    }

  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());
        arr = new int[n];
        vis = new boolean[n+1];

        func(0); // 첫 배열의 for문은 1부터 시작

    }
}