완전검색

  • 완전 검색 방법의 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다.
  • Brute-force 혹은 generate-and-test 기법이라고도 불리운다.
  • 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다. 시간적으로는 불리하다.
  • 상대적으로 빠른 시간에 문제 해결(알고리즘 설계)을 할 수 있다.
  • 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
  • 이들은 전형적으로 순열, 조합, 그리고 부분집합과 같은 조합적문제들과 연관된다.

완전 검색으로 시작하라

  • 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
  • 검정 등에서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.

순열 응용 - 비트마스킹 순열

비트마스킹을 통한 순열 생성 - 정수와 비트연산자를 사용

PermutationBitMaskingTest.java

nPn -> N개의 원소로 만들 수 있는 모든 순열 생성
input[] : 숫자 배열
numbers[] : 순열 저장 배열

perm(cnt, flag) // cnt: 현재까지 뽑은 순열 원소의 개수, flag: 선택된 원소에 대한 비트정보를 표현하는 정수
  if cnt == N
    순열 생성 완료
  else
    for i from 0 to N-1
      if(flag & 1<<i) != 0 then continue // i번째 자리가 1이면 continue라는 의미
      numbers[cnt] <- input[i]
      perm(cnt+1, flag | 1<<i) // i번째 자리에 1을 넣는것
    end for
  end perm()

비트 연산자

  • & : 비트단위로 AND 연산을 한다.
    • 각 배트열을 비교하여 두 비트 모두 1이면 1, 아니면 0으로 처리
  • : 비트 단위로 OR 연산을 한다.
    • 각 비트열을 비교하여 두 비트 모두 0이면 0, 아니면 1로 처리
  • ^ : 비트 단위로 XOR 연산을 한다.(같으면 0 다르면 1)
  • ~ : 단항 연산자로서 피연산자의 모든 비트를 반전시킨다.
  • « : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
    • value « n : value를 n비트 만큼 왼쪽으로 shift
    • 왼쪽으로 밀어내고 남은 오른쪽 자리는 0으로 채움

  • : 피연산자의 열을 오른쪽으로 이동시킨다.

순열 응용 - Next Permutation

NextPermutationTest.java

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

알고리즘

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

주의사항

  • NextPermutation 사용 전에 숫자배열을 오름차순으로 정렬하여 가장 작은 순열 한번 처리

조합 응용 - Next Permutation 활용

hot encoding? 같은거?

  • 원소크기와 같은 크기의 int 배열 P를 생성하여 r개 크기만큼 뒤에서 0이 아닌 값(예를 들어 1)으로 초기화한다.
  • nextPermutation 알고리즘을 활용한다.
  • nextPermutation 알고리즘 한 번 수행시마다 조합이 만들어짐 nextPermutation 과정 수행시마다 0이 아닌 값의 위치가 변경됨
  • P 배열에서 0이 아닌 값을 갖고 있는 위치에 해당하는 원소가 조합에 선택된 것임

2022.08.16

부분집합 응용 - 바이너리 카운팅

바이너리 카운팅을 통한 사전적 순서(Lexicographical Order)로 생성하는 방법

  • 부분집합을 생성하기 위한 가장 자연스러운 방법이다.
  • 바이너리 카운팅(Binary Counting)은 사전적 순서로 생성하기 위한 가장 간단한 방법이다.

바이너리 카운팅(Binary Counting)

  • 원소 수에 해당하는 N개의 비트열을 이용한다.
  • n번째 비트값이 1이면 n번째 원소가 포함되었음을 의미한다.

바이너리 카운팅을 통한 부분집합 생성 코드 예

SubSet_BinaryCountingTest.java

int arr[] = {3, 6, 7, 1, 5, 4};
int n = arr.length;

for(int i=0; i<(1<<n); i++) { // 1<<n: 부분집합의 개수
  for(int j=0; j<n; j++) {    // 원소의 수만큼 비트를 비교함
    if(i & (1<<j) != 0) {
      System.out.print(arr[j] + " ");
  }
  System.out.println();
}