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

---

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

02 부분 집합

(1/2)

---

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

---

02. 부분 집합

1️⃣ 부분 집합 문제

◾ 부분 집합의 합 문제

유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분 집합 중에서 그 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제이다.

EX. {-7, -3, -2, 5, 8}
1) {-3, -2, 5}는 부분집합
2) (-3) + (-2) + 5 = 0
=> TRUE

🥾접근 방법 : 
1) 완전 검색기법으로 부분 집합 합 문제를 풀기 위해서는 우선 집합의 모든 부분 집합을 생성한 후 각 부분 집합의 합을 계산한다.
2) 또는 주어진 집합의 부분 집합을 생성하는 다른 방법을 생각해본다.

---

◾ 부분 집합의 수

문제 : 어떤 집합의 부분 집합을 구할 경우 부분 집합의 개수는 총 몇 개 일까?

정답 : 집합의 원소가 n개일 때, 공집합을 '포함'한 부분 집합의 수는 2^n(개)

각 원소를 부분 집합에 포함시키거나(1) 포함시키지 않는(0) 2가지 경우를 모든 원소에 적용한 경우의 수와 같다.
EX) {1, 2, 3} => 2 * 2 * 2 => 2^3 => 8
📌이진수처럼 생각해 보면 이해가 쉽다! (000,001,010,011,100,101,110,111)

---

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

◾ Loop를 이용하여 확인하고, 부분 집합을 생성하는 방법

bit = [0, 0, 0, 0]
for i in range(2):
    bit[0] = i                    # 0번째 원소
    for j in range(2):
        bit[1] = j                # 1번째 원소
        for k in range(2):
            bit[2] = k            # 2번째 원소
            for l in range(2):
                bit[3] = l        # 3번째 원소
                print(bit)        # 생성된 부분집합 출력

📚bit : 실제 대상 List의 각 원소의 포함 여부(0,1)를 정하는 List

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

[0, 0, 0, 0] [0, 0, 0, 1] [0, 0, 1, 0] [0, 0, 1, 1] [0, 1, 0, 0] [0, 1, 0, 1] [0, 1, 1, 0] [0, 1, 1, 1] [1, 0, 0, 0] [1, 0, 0, 1] [1, 0, 1, 0] [1, 0, 1, 1] [1, 1, 0, 0] [1, 1, 0, 1] [1, 1, 1, 0] [1, 1, 1, 1]

---

◾ 부분 집합 문제 알고리즘 1

위 코드를 이용하여 실제 부분 집합을 생성하는 과정을 소개하기 위해 코드를 약간 수정했다.

example = [1, 3, 5, 8]            # 전체 집합

bit = [0, 0, 0, 0]
for i in range(2):
    bit[0] = i                    # 0번째 원소
    for j in range(2):
        bit[1] = j                # 1번째 원소
        for k in range(2):
            bit[2] = k            # 2번째 원소
            for l in range(2):
                bit[3] = l        # 3번째 원소
                temp = [example[m] for m in range(len(example)) if (bit[m])]    #부분 집합 생성
                print(bit, temp)    # bit, 부분 집합 출력

📚example: 전체 집합
📚bit : 실제 대상(부분 집합) List의 각 원소의 포함 여부(0,1)를 정하는 List

📌 temp = [example[m] for m in range(len(example)) if (bit[m])]
: 리스트 함축(내포)을 이용한 코드이다. 리스트 함축에 대해서는 다른 글에서 간략하게 소개한 바 있다.
[SWEA]파이썬 SW문제해결 기본 - LIST 1 : 알고리즘, 리스트

[SWEA]파이썬 SW문제해결 기본 - LIST 1 : 알고리즘, 리스트

 

💻위 코드의 실행 결과 :

[0, 0, 0, 0] []            #공집합
[0, 0, 0, 1] [8]
[0, 0, 1, 0] [5]
[0, 0, 1, 1] [5, 8]
[0, 1, 0, 0] [3]
[0, 1, 0, 1] [3, 8]
[0, 1, 1, 0] [3, 5]
[0, 1, 1, 1] [3, 5, 8]
[1, 0, 0, 0] [1]
[1, 0, 0, 1] [1, 8]
[1, 0, 1, 0] [1, 5]
[1, 0, 1, 1] [1, 5, 8]
[1, 1, 0, 0] [1, 3]
[1, 1, 0, 1] [1, 3, 8]
[1, 1, 1, 0] [1, 3, 5]
[1, 1, 1, 1] [1, 3, 5, 8]

---

위 코드는 부분 집합을 훌륭하게 구할 수 있다. 그러나 큰 문제점이 있다면... 원소의 개수만큼 for문을 중첩시켜야 한다는 점이다. 굉장히 비효율적이라고 할 수 있다. 글을 꼼꼼히 보는 사람이라면 앞서 '이진수'를 잠깐 언급한 사실을 기억할 것이다.

그렇다. 부분 집합 구하기는 '이진수'를 활용하면 훨씬 간결해진다. 바로 이어지는 다음 글에서 '이진수'의 특징을 활용하여 훨씬 간단하게 부분 집합을 구하는 방법을 알아볼 것이다.

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

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