알고리즘

Next Permutation

개념

순열을 구할 때, 현재 얻은 순열에서 사전순으로 다음에 오는 순열을 생성하면서 단계적으로 모든 순열을 구하는 방식입니다.
코드의 진행과정은 다음과 같습니다.

0. 순열을 구할 요소들을 오름차순으로 정렬합니다.
1. 뒤에서부터 탐색해 교환위치(i-1)을 찾습니다.
2. 뒤에서부터 탐색해 교환이치(i-1)와 교환할 큰 값 위치(j)를 찾습니다.
3. 두 위치 값(i-1,j)를 교환합니다.
4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순으로 정렬합니다.
   가장 큰 내림차순 순열이 만들어질 때까지 1-4를 반복합니다.

왜 이렇게 구해야하는지를 처음에는 이해할 수 없었지만, 손으로 직접 수열의 모든 경우의 수를 써보는 시행을 해본 결과 빼먹지 않으려면 이와 같이해야함을 알 수 있었습니다.
직접 하나하나 다 카운팅할 때, 숫자를 오름차순으로 정렬하고 맨 뒤에서부터 하나씩 자리를 바꿔보면서 만들어진 숫자를 10진수로 봤을 때, 오름차순으로 나열되도록 세주면 빼먹는 부분없이 셀 수 있었습니다.

1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 5 2 3 4
1 5 2 4 3
1 5 3 2 4//꼭대기를 비교하지않으면 1 5 2 3 4 같은 결과가 나올 수 있다.
1 5 3 4 2
1 5 4 2 3
1 5 4 3 2
(2 5 4 3 1) -> 2 1 3 4 5
...

그림으로 표현하면 다음과 같습니다.

주의할 점

Next Permutation은 n개의 원소를 나열할 수 있는 방법을 모두 구하는 방법입니다. 따라서 nPr과 같이 n개 중 r개를 뽑아서 구하는 방법을 사용하고싶다면, n개 중 r개를 뽑을 수 있는 조합을 이용해 Next Permutation을 구해야합니다.

구현

static boolean nextPerm(int[] numbers){
        //일단 뒤에서부터 찾는다.
        int N = numbers.length;
        //1. 꼭대기 찾기
        int i = N-1;
        while(i>0 && numbers[i-1]>=numbers[i])i--;
        if(i==0) return false;

        //2. 꼭대기를 찾았으면 다시 맨 뒤부터찾으면서
        int j = N-1;
        while(numbers[i-1]>=numbers[j])j--;

        //3. 찾았으면 둘이 위치 바꾸기
        swap(numbers,i-1,j);
        //4. 그 다음 뒤에 정렬
        int k = N-1;
        while(i<k){
            swap(numbers,i++,k--);
        }
        return true;
}
static void swap(int[] numbers,int i,int j){
	int temp = numbers[i];
    	numbers[i] = numbers[j];
        numbers[j] = temp;
}

Next Combination

개념

Next Permutation과 마찬가지로 조합을 구할 때, 현재 구한 조합에서 사전순으로 다음에 오는 조합을 생성하면서 단계적으로 모든 조합을 구하는 방식입니다.

Next Combinataion의 구현은 Next Permutation을 이용해서 nCr의 구현이 가능합니다.
이때 특별한 기법을 사용하는데 0과 1로 구성된 배열을 사용합니다.

n개의 원소를 가진 배열에서 r개의 1을 갖도록 만들어준 다음 그 배열을 이용해서 next permutation을 이용해서 만들어낼 수 있는 순열을 구합니다.
4개 중 2개를 뽑는 경우로 예를 들어보겠습니다.

0 0 1 1 - 초기에 이렇게 초기화를 합니다.
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

next permutation을 이용하면 위와 같은 결과를 얻을 수 있는데, 위의 결과에서 1이 있는 곳의 인덱스와 대응되는 원래 있던 데이터를 뽑아주면 쉽게 조합을 구할 수 있습니다.
(ex. 0 1 0 1 -> 1번째 원소와 3번째 원소를 뽑는다)
이 방법은 비트마스킹을 사용하는 방법과 비슷한 것 같다.

구현

int n = 4, r = 2;
int cnt = 0;
int temp = 0;
int[] data = {3,4,8,1};
int[] p = new int[n];
while(++cnt<=r) p[n-cnt] = 1;
Arrays.sort(data);

do {
	for(int i = 0;i<n;i++){
                if(p[i]==1) System.out.println(data[i]);
        }
}while(nextPerm(p));

//...next permutation

비트마스킹

비트마스킹이라는 개념을 처음 접했을 때 아래의 그림이 가장 먼저 생각났다.

수험생 때 공부했던 평가원 기출 국어 지문에 있던 그림인데, 비트마스킹의 개념을 이해하는데 많은 도움이 됐다.
비트 마스킹은 내가 관심있는 비트에만 표시를 해두고 그 비트만 볼 수 있습니다.

비트 마스킹을 사용하면 특정 상황에서 코드의 속도를 효율적으로 줄일 수 있습니다.

배열 입력을 갖는 함수에서 배열 대신 정수로 집합을 표현해서 배열의 인덱스로 쓸 수 있는 경우
ex)
1 1 1 -> 7
0 1 1 -> 3
0 0 1 -> 1
로 표현하면 입력을 배열의 인덱스로 쓸 수 있다.
O(1)우선 순위 큐
우선 순위가 특정 범위로 제한되어 있을 경우에는 비트 마스크를 이용해서 모든 작업을 O(1)에 처리할 수 있습니다.(이 내용은 추후에 우선 순위 큐를 정리할 때 다룰 예정입니다)

비트 연산자

| vs || , & vs &&

|,&는 논리연산이 아닌 비트 연산이기 때문에 선행조건의 참,거짓과 관계없이 비트연산을 수행해서 결과를 만들어야한다.

| 선행조건이 참이여도 뒤에오는 애 봄

|| 선행조건이 참이면 뒤에오는 애 안 봄

& 선행 조건이 거짓이여도 뒤에 오는 애 봄

&& 선행 조건이 거짓이면 뒤에 오는 애 안 봄
cf) ||,&&은 비트연산이 아니고 논리연산자
<< 피연산자의 비트 열을 왼쪽으로 이동(새로운 공간은 0으로 채움)
>> 피연산자의 비트 열을 오른쪽으로 이동(새로운 공간은 부호비트와 같은 비트로 채움)
>>> 피연산자의 비트 열을 오른쪽으로 이동(새로운 공간은 0으로 채움)