모든 경우의 수 (비트 연산)

항상 모든 경우의 수를 구할 때 어려움을 겪어왔다.

예를들어, 배열 N칸이 있는데 N칸 중 부분 배열의 합이 M 이상되는 경우를 구하라는 문제가 있다고 가정하자.

그럼 000, 001, 010, 011, 100, 101, 110, 111 를 모두 구해야 한다. (N칸을 3으로 가정)

가장 쉬운 방법으로는 반복문(for 문)을 3개를 작성하면 된다. 하지만 N의 값이 유동적이라면?

미리 반복문을 만들 수 없다. 어떻게 해결해야 할까?

해결책은 2가지가 있다.

1. 재귀를 이용한 백트래킹

2. 비트연산을 이용한 방법

나는 재귀보다 속도가 빠른 비트 연산을 방법을 이용하겠다.

import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        // Scanner sc = new Scanner(new FileInputStream("input.txt"));
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
 
        int[] arr = new int[N];
        for (int i = 0; i < 1 << N; i++) {
            int[] abc = new int[N];
            int bit = i;
            for (int j = 0; bit != 0; j++, bit >>= 1) {
                if ((1 & bit) == 0) {
                    continue;
                }
                abc[j] = 1;
 
            }
            for (int k = N - 1; k >= 0; k--) {
                System.out.print(abc[k] + " ");
            }
            System.out.println();
        }
    }
}

12라인에 있는  i < 1 <<N; 은 i< (1<<N); 이다. 즉, 1을 N 만큼 left Shift 한 결과로 2^N 이 된다.

예를 들어, 1일경우 2가 되고 2일 경우 4가 된다.

그 뒤 i 값을 bit로 받아 bit가 0이 될때 까지 right Shift 한다.

예를 들어 i가 7인경우 0111 로 나타낼 수 있는데 

0111 를 right Shift 하여 0011 --->0001 --->0000 으로 나타낼 수 있다.

여기서 (1&bit)를 하게 되면 가장 오른쪽에 있는 값과 &연산을 하여 1일 때만 나가도록 한다.

0000 일때는 나가는 값이 없고 1101 일때 1, x , 1, 1 순으로 나가게 된다.

나가는 순서가 반대이므로 abc 배열은 역방향으로 저장된다.

그렇게 떄문에 반복문을 반대로 출력한다. 

그 결과 

순으로 출력된다.

원하는 000, 001, 010, 011, 100, 101, 110, 111 값들을 얻게 되었다!.

*반대로 출력하고 싶다면 첫번째 반복문을 for (int i = (1<<N)-1; i >=0; i--) 으로 바꾸면 된다. (감소하는 순으로)