2의 n승 개의 경우 모두 확인하기.

확률에서 이런 경우가 많이 있다.

 

예를들어, 4명의 후보자가 있다. 그 중에 원하는 사람을 우리 팀에 뽑을 수 있다. 4명을 다 고를 수도 있고, 아무도 안 고를 수 있다면, 우리 팀에 후보자를 데려올 수 있는 경우의 수는 몇 가지인가?

 

풀이는 간단하다. 각 한명씩 뽑을 경우, 뽑지 않을 경우 두 가지 선택지만 존재하므로, 곱의 법칙을 이용해

2 * 2 * 2 * 2 총 16가지의 경우의 수가 존재한다.

 

이런식으로 각각의 선택지를 포함하고, 포함하지 않고 모두 탐색해야한다면 어떤식으로 풀어야할까?

---

아이디어는 간단하다. 0 ~ 15 (선택지가 4개 일 경우) 까지의 숫자를 이진수로 변환하여 각각의 경우에 대응하는 것이다.

 

모두 다 뽑지 않는 경우는 0 (0000)이 될 것이고, 모두 다 선택하는 경우는 15 (1111)이 될 것이다.

 

아래의 코드를 살펴보자.

#include <iostream>
#include <math.h>
using namespace std;


int main() {
	int option = 4;
	int pw = pow(2, option);
	for (int i = 0; i < pw; i++) {
		for (int index = 0; index < option; index++) {
			bool a = (i >> index) & 1;
			cout << a << ' ';
		}
		cout << '\n';
	}
	return 0;
}

반복문이 들어가면 읽기가 싫어진다.

 

하지만 어려운 코드가 아니니 천천히 보면 pow(a,b)는 math.h 헤더에 정의된 함수로 a의 b제곱 값을 구해준다.

따라서 첫 번째 for문의 i는 0부터 15까지 진행된다.

 

변수 a는 숫자 i의 2진수 값을 차례대로 반환한다. (i의 비트를 오른쪽으로 밀고 &(and) 연산을 통해 가장 오른쪽 비트가 1이면 1 0이면 0을 출력한다. 

 

따라서 위의 코드의 실행 결과는 아래와 같다.

이렇게 16가지의 경우의 수를 모두 확인할 수 있다. 

 

기본적으로 위의 아이디어는 2^n의 경우의 수를 전부 탐색하기때문에 n이 큰 값일때에는 적절하지않다.

따라서 알고리즘 풀이 시에 최대 N과 제한 시간을 확인해야한다.