[배열] 부분집합 관련 문제 비트연산으로 풀기 :: 코드자몽

부분집합 구하기

배열이 주어졌을때 부분집합을 구하는 코드를 작성해보자. 아래 기본 문제를 설명 및 코드샘플을 확인하지 않고 먼저 풀어보자.

 

기본 문제

{1, 2, 3, 4, -1, -5}

위 배열에서 홀수로 구성된 부분 집합을 모두 출력 하시오.

 

 

간단해 보이지만 비트연산을 이해하지 못하면 생각보다 어려운 문제이다.

위 문제를 완전탐색 혹은 배열의 위치를 이용해서 풀겠다고 접근했을것이라 생각합니다. 완전탐색 방법으로 풀려고 하다보니 for문을 중첩해서 사용하면 배열이 커질수록 효율도 떨어지고 시간복잡도가 제곱으로 늘어나는 것을 확인했을 것입니다. 그럼 배열의 위치를 이용해서 푸는 방법을 생각하다보니 0과 1을 이용하여 자리를 표시하는 방법이 떠오르게 될것입니다.

 

위의 문제 처럼 부분집합을 구하는 문제에서는 비트연산을 이용하게 되면 쉬워집니다.

 

풀이 코드

import java.util.Arrays;

public class PartElements {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, -1, -5};
        // 모든 부분집합의 경우의 수
        for (int i = 1; i < (1 << array.length); i++) {
            int[] temp = new int[array.length]; // 임시 부분 집합
            int count = 0; // 새로운 배열 크기
            boolean isOdd = true; // 홀수 여부 확인
            // 부분집합 생성
            for (int j = 0; j < array.length; j++) {
                if ((i & (1 << j)) != 0) {
                    if (array[j] % 2 == 0) {
                        isOdd = false;
                    }else{
                        temp[count++] = array[j];
                    }
                }
            }
            // 출력
            if (isOdd) System.out.println(Arrays.toString(Arrays.copyOf(temp,count)));
        }
    }
}

 

 

 

설명

비트연산을 이용한 문제풀이는 배열의 위치를 2진수형태로 표현하여 접근하는 방법입니다.

비트연산에 대한 내용은 아래 글을 통해 자세히 알아보자.

[자료구조 & 알고리즘/알고리즘] - JAVA 자바로 비트연산 알아보기 :: 코드 자몽

 

 

7

for (int i = 1; i < (1 << array.length); i++) {

모든 부분 집합의 경우의 수를 확인 하기 for문으로 확인한다. i의 범위는 1 ~ 63까지가 됩니다.

 

8 ~ 10

int[] temp = new int[array.length]; // 임시 부분 집합
int count = 0; // 새로운 배열 크기
boolean isOdd = true; // 홀수 여부 확인

추출한 부분집합의 임시 배열 생성하고 나중에 생성한 배열을 한번 더 수정해주기 위해 배열의 크기로 사용할 변수를 임시로 만들어준다.

 

12 ~ 20

for (int j = 0; j < array.length; j++) {
     if ((i & (1 << j)) != 0) {
         if (array[j] % 2 == 0) {
            isOdd = false;
        }else{
            temp[count++] = array[j];
        }
    }
}

이 부분이 이번 풀이에서의 핵심이다.

i의 숫자와 for문을 이용해서 0 ~ 5까지 각 자의 값이 있는지 확인하는 작업입니다.

if ((i & (1 << j)) != 0) { 의 if구문에서i 와 (1 << j) 의 & 비교가 하는 일을 표로 확인해봅시다.

i는 1 ~ 63의 반복문이고 j는 0 ~ 5까지의 반복문입니다.

 

i의 비트은 보기 쉽게 5자리로 표시했습니다.

i	i의 비트값	j	(1 << j)	i & (1 << j)	i & (1 << j)의 값
1	000001	0	000001	000001	1
1	000001	1	000010	000000	0
1	000001	2	000100	000000	0
1	000001	3	001000	000000	0
1	000001	4	010000	000000	0
1	000001	5	100000	000000	0
2	000010	0	000001	000000	0
2	000010	1	000010	000010	2
2	000010	2	000100	000000	0
2	000010	3	001000	000000	0
2	000010	4	010000	000000	0
2	000010	5	100000	000000	0
...
63	111111	0	000001	000001	1
63	111111	1	000010	000010	2
63	111111	2	000100	000100	4
63	111111	3	001000	001000	8
63	111111	4	010000	010000	16
63	111111	5	100000	100000	32

 

위 표와 같이 i & (1 << j) 값이 0이 아닐때 if문 안으로 들어가게끔 했다. 즉, 1~63까지 이진수로 나타내면 모든 부분집합의 경우의 수를 구할 수 있다. 나머지 홀수만 걸러주는 로직을 해당 if문안에 추가적으로 넣어주면 된다.

 

22

if (isOdd) System.out.println(Arrays.toString(Arrays.copyOf(temp,count)));

기존에 temp라는 배열을 array배열의 크기 그대로 생성해주었다. 홀수만 따로 뽑아냈기 때문에 나머지 자리에는 0이 채워졌을 것이다. 0을 모두 삭제해주기 위해 뽑아낸 배열의 크기 만큼만 배열 복사를 해주었다.

 

결과

 

 

비트연산으로 접근하여 부분집합을 구하는 문제를 하나 더 풀어보자.

 

변형 문제 : 황금떡볶이가 먹고싶어요

자몽초등학교 3학년 1반 학생들은 매일 용돈을 받는다. {자몽, 바나나, 애플망고, 멜론, 오렌지, 체리, 스트로베리, 키위, 리치}는

각각 {15000, 2000, 10000, 7000, 15000, 1000, 2000, 4000, 5000}원씩 받는다. 3학년 1반 학생들은 황금분식에서 판매하는 황금 떡볶이를 먹기위해 그룹을 모집하고 있습니다. 황금 떡볶이는 30000원입니다. 3명 이하의 그룹으로 황금떡볶이를 사 먹을 수 있는 그룹을 모두 출력 하시오.

 

풀이 코드

import java.util.Arrays;

public class Gold {
    public static void main(String[] args) {
        String[] names = {"자몽", "바나나", "애플망고", "멜론", "오렌지", "체리", "스트로베리", "키위", "리치"};
        int[] array = {15000, 2000, 10000, 7000, 15000, 1000, 2000, 4000, 5000};

        for (int i = 1; i < (1 << array.length); i++) {
            String[] temp = new String[array.length];
            int count = 0;
            int sum = 0;
            for (int j = 0; j < array.length; j++) {
                if ((i & (1 << j)) != 0) {
                    sum += array[j];
                    temp[count++] = names[j];
                }
            }
            String[] resultArr = Arrays.copyOf(temp, count);
            if (sum >= 30000 && resultArr.length <=3) System.out.println(Arrays.toString(resultArr));
        }
    }
}

 

 

 

결과