[Java] 비트 마스킹, Next_Permutation

1. 비트연산

 

연산자	설명	예시
&	비트 AND 연산	5 & 3 = 1
^	비트 XOR(배타적 OR) 연산	5 ^ 3 = 6
~	비트 NOT 연산 (1의 보수)	~5 = -6
<<	왼쪽 시프트 연산 (비트를 왼쪽으로 이동)	5 << 2 = 20
>>	오른쪽 시프트 연산 (비트를 오른쪽으로 이동)	5 >> 2 = 1
>>>	부호 없는 오른쪽 시프트 연산	-5 >>> 2 = 1073741822

 

---

2. 비트마스킹

 

가. 순열

 

nPn → n! 이다. (보통 10!을 넘어서면 힘들다.)

 

비트마스킹을 사용해서 공간복잡도를 줄일 수 있다.

 

기존에는 boolean[] 또는 int[] 를 사용해서 방문 체크를 수행했다.

 

비트마스킹을 활용하면 int 하나에도 모두 저장할 수 있다.

 

input[] // 숫자 배열 
numbers[] // 순열 저장 배열

perm(cnt, flag)
    if cnt == N
        순열 생성 완료
    else
        for i from 0 to N-1
            if(flag & << i)!= 0 then continue
            numbers[cnt] <- input[i]
            perm(cnt+1, flag | 1<<i)
        end for
end perm()

import java.util.Arrays;
import java.util.Scanner;

//nPr
public class BitmaskingPermutationTest {

    static int N, R, input[], numbers[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // nPr의 n 
        R = sc.nextInt(); // nPr의 r
        input = new int[N]; // 입력 저장 배열
        numbers = new int[R]; // 순열 저장 배열

        for(int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }
        permutation(0, 0);
        sc.close();
    }

    public static void permutation(int cnt, int flag) {
        if(cnt == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }
        for (int i = 0; i < N; i++) {
            if((flag & 1<<i)!=0) continue; // pass
            numbers[cnt] = input[i]; //수 선택
            permutation(cnt+1, flag | 1<<i);
        }
    }

}

 

---

나. 부분집합

 

비트마스킹을 활용해서 부분집합 문제를 다루는 방법 참고.

 

[Java] 부분집합

 

---

3. Next Permutation

 

현 순열에서 사전 순으로 다음 순열 생성.

 

nPn만 된다. nPr은 안된다.

 

1. 배열을 오름차순으로 정렬한다.
2. 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성 (가장 큰 내림차순 순열을 만들 때까지 반복한다.)
   1. 뒤쪽부터 탐색하며 교환위치(i-1) 찾기 (i: 가장 큰 값)
   2. 뒤쪽부터 탐색하며 교환위치(i-1)와 교환할 큰 값 위치(j) 찾기 (i-1보다 큰 값 중 최솟값)
   3. 두 위치 값(i-1, j) 교환
   4. 꼭대기위치(i)부터 맨 뒤까지 오름차순 정렬

 

 

---

가. 순열 응용

import java.util.Arrays;
import java.util.Scanner;

// 오직 nPn만 가능
public class NextPermutationTest {

    static int N, input[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        input = new int[N]; // 입력 저장 배열

        for(int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }

        // 0. 오름차순 정렬
        Arrays.sort(input);

        do {
            System.out.println(Arrays.toString(input));
        }while(next_Permutation(input));

        sc.close();
    }

    // 현 순열의 사전순으로 다음 순열 생성
    public static boolean next_Permutation(int[] p) {
        final int last = p.length - 1;
        // 1. 가장 큰 값의 위치 i 찾기
        int i = last;
        while(i>0 && p[i-1] >= p[i]) --i;

        if(i==0) return false; // 현 순열의 상태가 가장 큰 순열이라 np가 없음.

        // 2. 교환위치(i-1)에 넣을 값 뒤쪽부터 찾기. 큰 값 중 최소.
        int j = last;
        while(p[i-1]>=p[j]) --j;

        // 3. 교환위치(i-1) 값과 찾은 위치(j) 값 교환
        swap(p, i-1, j);

        // 4. 교환위치(i-1) 뒤(i)부터 맨 뒤까지 오름차순 정렬
        int k = last;
        while(i<k) swap(p, i++, k--);

        return true;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

---

나. 조합 응용

 

nCr 구하기.

1. 원소 크기(n)와 같은 크기의 0으로 초기화된 int 배열 P를 생성한다.
2. 뒤에서부터 r개 만큼 0이 아닌 숫자로 초기화한다.
3. next_Permutation 알고리즘을 활용해서 순열을 생성한다.
4. P에서 0인 값은 선택하지 않은 것이고 0이 아닌 값은 선택한 경우다.

 

 

import java.util.Arrays;
import java.util.Scanner;

//nCr
public class NPCombinationTest {

    static int N, R, input[], P[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("N : ");
        N = sc.nextInt();
        System.out.print("R : ");
        R = sc.nextInt();
        System.out.print("집합 : ");
        input = new int[N]; // 입력 저장 배열
        P = new int[N]; // 조합 생성 배열

        for(int i=0; i<N; i++) {
            input[i] = sc.nextInt();
        }
        // 뒤에서부터 r개 만큼 0이 아닌 숫자로 초기화한다.
        for(int i=0; i<R; i++) {
            P[N-1-i] = 1;
        }
        //System.out.println(Arrays.toString(P));

        StringBuffer sb = new StringBuffer();
        do {
            for(int i=0; i<N; i++) {
                if(P[i]!=0) sb.append(input[i]).append(" ");
            }
            sb.append("\n");
        }while(next_Permutation(P));
        System.out.println(sb.toString());

        sc.close();
    }

    // 현 순열의 사전순으로 다음 순열 생성
    public static boolean next_Permutation(int[] p) {
        final int last = p.length - 1;
        // 1. 가장 큰 값의 위치 i 찾기
        int i = last;
        while(i>0 && p[i-1] >= p[i]) --i;

        if(i==0) return false; // 현 순열의 상태가 가장 큰 순열이라 np가 없음.

        // 2. 교환위치(i-1)에 넣을 값 뒤쪽부터 찾기. 큰 값 중 최소.
        int j = last;
        while(p[i-1]>=p[j]) --j;

        // 3. 교환위치(i-1) 값과 찾은 위치(j) 값 교환
        swap(p, i-1, j);

        // 4. 교환위치(i-1) 뒤(i)부터 맨 뒤까지 오름차순 정렬
        int k = last;
        while(i<k) swap(p, i++, k--);

        return true;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

---