자료구조 - 집합(set)

오늘 다룰 자료구조는 '집합(set)'

집합의 특징은 '중복'을 허용하지 않는 다는 것이다.

중복 데이터를 배제해야만 할 때 사용한다.

오늘도 예시로 시작해보자

1. 집합 객체를 선언하고 값들을 넣어보자.

2.그리고 정말 중복값을 배제하는지 확인해보자.

#  집합을 정의 및 선언
set_data = set()

set_data.add(False) # 집합 object에 bool 타입 값 입력
set_data.add(1)     # 집합 object에 int형 1 값 입력
set_data.add("hi")  # 집합 object에 문자열 입력
set_data.add("this is programming") # 집합 object에 문자열 입력
set_data.add("234") # 집합 object에 문자열 입력

set_data.add(1) # <---- 집합 object에 int형 1 값 재 입력 

# (중복 입력 되는지 확인)
check = set_data.add(1)
print(check)

# 집합 object 출력
print(set_data) 

결과 : 중복값 배제됨 확인

set_data.add(1)  두 번 선언했으나, 맨 처음 선언한 1만 반영.

1. 집합이란?

집합은 '배열'과 매우매우매우매우 유사하다.

자료구조에서 중요한

1) 데이터 읽기

2) 데이터 검색

3) 데이터 삭제

4) 데이터 삽입

위의 4가지 중

4) 데이터 삽입을 제외하고는 똑같다.

서두에 언급했듯이, 데이터를 삽입하기 위해서

'집합'은 집합 안에 동일 데이터가 있는지 우선 확인해야하기 때문이다.

즉, 데이터 삽입을 위해서 '검색'을 진행해야 한다.

(이 자체가 이미 빅오 기준으로 보면 '배열'보다 시간복잡도가 높다. 단계가 하나 증가됐기 때문이다.)

따라서, 시간복잡도가 증가됨에도 불구하고!!!!

집합을 써야하는지를 프로그램의 특성에 맞게 결정해야 한다.

2. 시간 복잡도 계산 (데이터 삽입)

배열과 집합 간 시간 복잡도가 어떻게 차이가 나는지

코드를 통해 확인해보자.

1) 배열

# 배열 선언 및 초기화
list_data = []

# 배열과 집합에 데이터 삽입
# 1. 배열
list_data.append("바나나")
list_data.append("자동차")
list_data.append("기린")
list_data.append("음료수")
list_data.append("크레용")


#  배열과 집합 맨 처음(= 인덱스 0)에 데이터 "사과"를 입력해보자.
# 1. 배열
list_data.append(None)
cnt = len(list_data) - 1
while True:  
    if cnt == 0:
        list_data[0] = "사과"
        break
    list_data[cnt] = list_data[cnt-1]
    cnt -= 1

# 배열 데이터 확인
print(list_data)

결과

2) 집합

# 집합 선언 및 초기화 
# 배열을 활용하여 집합을 구현하였다.
# 왜냐하면 집합 메소드를 사용하면 내부적으로 어떻게 작동되는지 확인이
# 어렵기 때문이다. 

set_data = []     # 실제로는 set_data = set() 으로 구현됨

# 1. 집합에 데이터 삽입
set_data.append("바나나")
set_data.append("자동차")
set_data.append("기린")
set_data.append("음료수")
set_data.append("크레용")

# 집합의 인덱스 0에 데이터 "사과"를 입력해보자.
input_data = "사과"
# 1) '중복'이 안되니, 우선 "사과"가 집합 안에 있는지부터 체크!

# 바로 이 부분이 '배열'과는 다르게 단계(step)가 추가되는 부분이다.
# 따라서, 시간복잡도 증가
for data in set_data:
    if input_data == data:
        print("중복 데이터를 넣을 수 없습니다.")
        break
print("중복이 없으니 데이터를 입력합니다.")

# 2) 인덱스 0에 데이터 추가하기 위한 작업!
set_data.append(None)
cnt = len(set_data) - 1 
while True:
    if cnt == 0:
        set_data[0] = input_data
        break
    set_data[cnt] = set_data[cnt - 1]
    cnt -= 1

# 집합 데이터 확인
print(set_data)

결과

3. 배열과 집합 구현을 통해 느낀점

파이썬을 사용하며,

syntax의 명료함 그리고 제공되는 자료구조의 편의성을 만끽해왔다ㅎㅎㅎㅎ

하지만 무심코 쉽게쉽게 사용하던 자료구조가

내부적으로는 얼마나 많은 단계를 거치는지(시간복잡도)

확인해보지는 못했었다.

오늘의 배움을 계기로 자료구조 선택에 신중해야 겠다.

                                    - One step at a time -