57. 입력한 N에 따라 0부터 N-1까지 모둔 부분집합 출력하기 알고리즘

0부터 N-1까지 모든 부분집합 출력하기 알고리즘.

이 알고리즘은 컴퓨터 과학에서 나열하기의 한 종류이다.

나열하기 알고리즘은 대부분 모든 경우를 다 조사하는 전수조사법이 기반이다. 

그렇기에 컴퓨터과학에 무척 어울리는 종류의 주제이며, 재귀적인 방법이 주로 쓰인다.

0부터 N-1까지의 집합 중에서 모든 부분집합 출력하는 방법은 단 두 문장으로 정리된다.

(1) 현재 원소를 포함한 부분집합

(2) 현재 원소를 제외한 부분집합

이 두 문장의 조합으로 모든 부분집합을 찾을 수 있다.

예를 들어 만약 {0,1,2} 집합의 모든 부분집합은 다음과 같다.

{0, 1, 2}

{0, 1}

{0}

{1, 2}

{1}

{2}

공집합

이렇게 8개이다. 즉, 모두가 다 알듯이 2^n개가 바로 n까지의 부분집합 개수이다.

다음은 코드이다.

주석을 통해서 실행원리를 아주 자세히 작성했다.

주석을 많이 쓴 코드는 원리를 파악하기는 좋지만, 한 눈에 보기 어려우니 다음은 주석을 뺀 코드다.

굉장히 코드가 간결하다. 이 코드에 대한 출력은 다음과 같다.

(1) {0, 1, 2}의 모든 부분집합 출력

(2) {0, 1, 2, 3, 4}의 모든 부분집합 출력

올바른 결과를 확인할 수 있다. 아래 빈 공백이 바로 공집합을 의미한다.

그럼 지금부터가 아주 짧지만 이 포스팅의 주 본론이다.

만약 재귀적으로 돌아가는 두 분기의 순서를 코드에서 바꾼다면 어떻게 될까?

결과는 다음과 같다.

왜 올바른 출력이 나타나지 않을까?

순서를 바꾸든 안바꾸든 결국 두 조건

(1) 현재 원소를 포함한 부분집합과 

(2) 현재 원소를 제외한 부분집합의

합인데.

그 이유는 모두가 알다시피 배열을 통한 포인터 접근이기에 이전 분기를 돌면서 기존의 필요한 데이터가 덧씌어져이다.

이를 간단하게 그림으로 한 번 실행 흐름을 따라가며 그려보면 더 명확히 알 수 있다.

그럼 이 바뀐 순서를 유지하면서 올바른 출력을 만들어내려면 어떻게 해야할 까?

다음 코드와 같이 데이터의 처리를 유효한 분기와 밀접하게 연결시켜주면 된다.

이 말을 잊지 않기 위해서 이 포스팅을 작성하였다. 

결과는 다음과 같다.

분기의 순서가 다르기에 전체적인 출력 형태의 순서도 달라진 것을 볼 수 있다.

이처럼 전체 경우를 나열하는 문제는 꽤 많다.

또한 분기가 2개가 아니라 여러개일 수 도 있는데, 그 땐 지금까지 데이터를 백업했다가 각 분기별로 recover하는 방식으로

코드를 작성해왔다. 하지만 이 방식은 너무 비효율적이다. 데이터를 유효 분기에 연결시켜주긴 하지만 그러니 조금 더 연구

해서 더 깔끔하고 효율성있는 방법을 찾아보자.