[SWEA]파이썬 SW문제해결 기본 - LIST 2 : 부분 집합 (2/2)

---

파이썬 SW 문제 해결 기본 - LIST 2

02 부분 집합

(2/2)

---

이미지를 클릭하시면 SW Expert Academy의 해당 강좌로 이동합니다

※이 글은 2편 중 2편입니다. 전편(1편)을 먼저 확인하는 것을 권장합니다.※

[SWEA]파이썬 SW문제해결 기본 - LIST 2 : 부분 집합 (1/2)

[SWEA]파이썬 SW문제해결 기본 - LIST 2 : 부분 집합 (1/2)

---

02. 부분 집합

3️⃣ 부분 집합 문제 알고리즘 2

◾ Bit로 생각해보기

앞서 부분 집합을 구하는 방법을 소개하며 '이진수'로 생각해보면 이해가 쉽다고 언급했다. 앞선 코드에서는 크기 4(원소가 4개)인 집합의 bit 리스트를 생성하기 위해 for문을 4번이나 중첩했다. 그러나 'bit'리스트를 이진수로 생각해보면 다음과 같다.

즉 반복문을 4번이나 중첩시키는 대신, 이진수 값을 1씩 증가시키는 편이 더욱 효율적인 방법이 되겠다. 이 원리를 바탕에 둔 방법이 바로 다음에 이어진다.

---

 

◾ 비트 연산자

비트 연산자 : 0과 1로 이루어진 이진수에 대한 연산을 수행하는 연산자이다.

📌 비트 연산자 종류
- &    : 비트 단위로 AND 연산을 한다.
- |      : 비트 단위로 OR 연산을 한다. (키보트 Enter 키 위에 있는 "\키+Shift"로 쓸 수 있다.)
- <<  : 피연산자의 비트 열을 왼쪽으로 이동시킨다.
- >>  : 피연산자의 비트 열을 오른쪽으로 이동시킨다.

---

◾ 비트 연산자를 이용, 부분 집합을 구하기 위한 'bit' 만들기

1)
예제) 2 << 3 : '10'(2의 2진수 표현)을 왼쪽으로 3만큼 이동한다.
결과 -> 10000 -> 16

1<<0 = 1
1<<1 = 2
1<<2 = 4
1<<3 = 8
 ...
📌1<<n = 2^n = 원소가 n개일 경우의 모든 부분 집합의 수!

2)
예제) 5 & 3 : 이진수 '5'와 3'의 비트 단위 기준, 자릿수 별로 OR연산을 한다.
결과 -> 5 & 3 -> 101(5의 2진수 표현) & 011(3의 2진수 표현) -> 010 -> 2

10(1010) & 1(0001) = 0
10(1010) & 2(0010) = 1
10(1010) & 4(0100) = 0
10(1010) & 8(1000) = 1

3)
1번과 2번을 모두 활용하면 다음과 같이 쓸 수 있다.
10(1010) & 1<<0 = 0
10(1010) & 1<<1 = 1
10(1010) & 1<<2 = 0
10(1010) & 1<<3 = 1

즉,
📌i & (1<<j) : i에서 오른쪽으로부터 j+1번째 비트가 1인지 0인지를 리턴한다.

---

◾ 보다 간결하게 부분 집합을 생성하는 방법

arr = [1, 3, 5, 8]
n = len(arr)    # n : 원소의 개수(4개)

for i in range(1<<n):    # 1<<n : 부분 집합의 개수
    temp = []    # temp : 부분 집합을 저장할 임시 리스트 초기화
    for j in range(n):    # 원소의 수만큼 비트를 비교함
        if i&(1<<j):  #i의 j번째 비트가 1이면 True
            temp.append(arr[j])    # 비트가 1에 해당하는 원소를 부분 집합 리스트에 추가
    print(temp)    #부분 집합 출력

위 코드를 실행하면 다음과 같은 결과가 나온다.

 

[] [1] [3] [1, 3] [5] [1, 5] [3, 5] [1, 3, 5] [8] [1, 8] [3, 8] [1, 3, 8] [5, 8] [1, 5, 8] [3, 5, 8] [1, 3, 5, 8]

---

마치며...

사실 그동안 코딩을 하면서 비트 연산자를 쓸 일이 거의 없었는데 이런 식의 활용이 참 신기했다. 부분 집합을 구해야 해결 가능한 문제가 많으니 정확히 이해하고 넘어가는 것이 좋겠다. 

다음 글에서는 '검색 알고리즘'을 다룬다.