[완전탐색] 순열 편

Greedy 알고리즘을 사용하면 눈 앞에 보이는 최적의 해답을 찾아서 이동하기 때문에 빠르게 답을 구해낼 수 있지만, 그리디 알고리즘만으로는 해결하지 못하는 경우가 있다.

 

그럴때는 완전탐색 기법을 사용해서 해결한다.

완전 탐색 혹은 완전 검색이라고 불리는 이 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. 이 방법은 Brute-force 혹은 generate-and-test 기법으로도 불리는데 모든 경우의 수를 테스트 한 후 최종 해법을 도출해낸다.

 

장/단점으로는

모든 경우의 수를 생성하고 테스트하기 때문에 수행속도가 느리다고 오래걸린다는 단점이 있다.

하지만 모든 경우의 수를 다 검색해 보기 때문에 해답을 찾아내지 못할 확률이 적다. 느리긴 하지만, 크기 제한이 작을때는 유용하다. 

따라서, 최적화가 목적이 아니라면 비교적 쉽게 접근할 수 있기 때문에 검정에서는 나쁘지 않은 방법이다. 시험장에서 문제를 만났는데 모르겠으면 일단 완전탐색으로 다 찾은 후에 가지를 쳐내는 것도 괜찮은 방법이다. 

 

완전 탐색으로 순열, 조합, 부분집합과 같은 문제들과 연관 지을 수 있는데, 이번에는 순열에 대해 살펴 볼 것이다.

 

순열

순열은 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것이다. 

앞에서 선택된 것 빼고 골라야하고, 조합과는 다르게 순서가 중요하다. 

같은 숫자인 123을 사용한다고 하더라도, 231과 132는 다른 순열이 된다. 

서로 다른 n개 중 r개를 택하는 순열은 nPr이라고 표현하고, O(N!) 의 시간 복잡도를 가지고 있다. 

nPr은 n부터 r번 곱해지는데, 총 경우의 수는 n!/(n-r)! 이다.

 

순열 생성법

순열 생성법으로는 for문을 이용하는 것, 재귀 함수를 이용하는 법, 비트마스킹을 이용하는 법이 있다.

 

1) for문을 이용하는 법

- 이 방법은 n중 포문을 돌려야하기 때문에 n의 갯수가 작을 때 사용할 수 있다.

 

 2)재귀 함수를 이용하는 법

- 재귀함수를 이용해 내가 목표한 숫자(cnt)에 도달할 때까지 재귀를 돌려준다. 

  1) boolean형의 check 배열을 사용해서 중복을 확인.

  2) 사용하지 않은 숫자라면 결과 배열에 숫자를 넣어주고 사용했다고 체크 후 재귀 호출.

  3) 같은 방법대로 반복 하다가 N을 만나면 이번에 생성 된 순열 띄워주고 return.

  4) 갔던 곳 false로 바꿔주고 다음 번 루프 돌기. (1-3) 반복.

  5) for문이 종료되면 모든 순열이 다 호출 된 것이므로 함수 종료.

static void perm(int idx) { //순열
		if(idx == N) {
			System.out.println(Arrays.toString(result));
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(!check[i]) {
				result[idx] = arr[i];
				check[i] = true;
				perm(idx+1);
				check[i] = false;
				
			}
		}
	}

3)비트마스킹을 이용하는 법

- 재귀함수를 사용하는 것은 같은데, boolean 배열 대신 비트마스킹을 이용해서 순열을 생성하는 것이다.

- 전 방법과는 다르게 지금까지 뽑은 숫자의 수와 선택 된 원소에 대한 비트 정보를 표현하는 정수, 두 개의 인자를 사용 한다. 

- 이 방법은 논리 연산을 사용해야 한다.

 

* 논리 곱 & -> 둘다 1일때만 1
* 논리 합 | -> 하나라도 1이면 1
* XOR ^ -> 둘이 다르면 1, 같으면 0
* 반전 ~ -> 1이면 0으로, 0이면 1이로
* << 비트열을 왼쪽으로 이동. 계속해서 2배씩 키워줌
* >> 비트열을 오른쪽으로 이동. 2로 나눠주는 효과.

 

  1) flag와 and 연산을 이용해 중복 체크를 해주고, 원하는 위치의 상대 비트가 1이라면 넘긴다. 

  2) 아니라면 numbers에 i를 넣어주고, 다음번 재귀를 돌려준다.

static void perm(int cnt,int flag) { // 지금까지 뽑은 숫자의 수, 선택 된 원소에 대한 비트 정보를 표현하는 정수 
		if (cnt == N) {
			//순열 생성 완료
		}
		else {
			for(int i=0; i<N; i++){
				if (flag & 1<<i != 0) //중복 체크.
					continue; //원하는 위치의 상대 비트가 1이면 넘김
				numbers[cnt] = i; //아니라면 numbers에 i 넣기
				perm(cnt+1, flag | 1<<i); //상태를 추가하는 것. i를 1로 추가. 
				//cnt가 N이되어 돌아오면 flag가 그대로 유지되어야 하기 때문.
			}
		}
	}

 

 

나는 순열을 구해야 할 때 2번을 자주 쓴다. 

3번은 손에 안 익어서 그런지 잘 안쓰게 된다.

더 많은 방법이 있을 것 같은데, 다른 방법을 배우면 추가해 봐야겠다.