자료구조의 이해

자료구조의 개념

프로그래밍을 하다보면 다양한 형태의 데이터를 저장하여 처리해야 할 경우가 있다.
실생활에서도 마찬가지다. 대표적으로 전화번호부가 있다. 요즘은 그다지 사용되지 않지만 과거에는 'Yellow Page'라는 두꺼운 전화번호부에서 번호를 저장하였다. 또한 번호 보기쉽게, 찾기 쉽게 정리하기 위해 가나다 순으로 저장하였다. 즉 번호라는 데이터 자료들을 가나다 순의 방법으로 저장한 것이다. 데이터에서도 마찬가지다. 데이터의 특징을 고려하여 데이터를 저장하는 방법을 자료구조(data structure)라고 한다.

전화번호부 이외에도 실생활에서 데이터의 특징을 반영하여 저장해야 할 경우는 많다. 예를 들어 은행의 번호 표 처리방식이다. 은행의 번호표 단말기에서는 사용자가 번호표를 하나씩 뽑으면 대기 인원이 1이 증가하며, 번호가 빠를 수록 먼저 일을 보는 방식이다. 이 경우 사용되는 번호표의 번호 정보와 현재 대기 인원을 모두 관리한다면 효율적으로 데이터를 관리할 수 있다.
또 다른 예로 택배의 수하물이 있다. 택배의 물건들은 가장 늦게 배달되는 물건은 트럭에 가장 깊숙이 넣고, 가장 먼저 배달되는 물건을 가장 앞에 배치시킨다. 이러한 특징을 고려한 데이터(물건,번호) 저장 방식은 일상, 컴퓨터 내에서 유용하게 사용된다.

정리하면, 자료구조는 특징이 있는 정보를 메모리에 효율적으로 저장 및 반환하는 방법으로, 데이터를 저장하는 방식이다. 특히 대용량일수록 빨리 저장하고 빠르게 검색하여, 메모리를 효율적으로 사용하고 실행 시간을 줄일 수 있게 해준다.

파이썬에서의 자료구조

파이썬에서의 기본적인 저장 방식은 리스트가 있다. 이 외의 자료구조는 아래와 같다.

자료구조명	특징
스택(stack)	나중에 들어온 값을 먼저 나갈수 있도록 해 주는 자료구조(last in first out)
큐(queue)	먼저 들어온 값을 먼저 나갈수 있도록 해 주는 자료구조(first in first out)
튜플(tuple)	리스트와 같지만, 데이터의 변경을 허용해주지 않는 자료구조
세트(set)	데이터의 중복을 허용하지 않고, 수학의 집합 연산을 지원하는 자료구조
딕셔너리(dictionary)	전화번호부와 같이 키(key)와 값(value)형태의 데이터를 저장하는 자료구조, 여기서 키값은 다른 데이터와 중복을 허용하지 않는다.
collections 모듈	위에 열거된 여러 자료구조를 효율적으로 사용할 수 있도록 지원하는 파이썬 내장(built-in)모듈

참고로 자료구조는 컴퓨터공학과에서 한 학기 수업으로 가르치는 어려운 과목이다. 따라서 자세한 내용은 자료구조와 알고리즘을 다루는 전문 서적을 참고하는 것이 바람직하다.

스택과 큐

스택(stack)

자료구조의 핵심 구조중 하나인 스택(stack)은 마지막에 들어간 데이터가 가장 먼저 나오는 형태로, 데이터의 저장 공간을 구현하는 것이다. 간단히 표현하면 LIFO(Last In First Out)으로 정의할 수 있다.

스택에서 데이터의 저장을 푸시(Push), 데이터의 추출을 팝(Pop)이라고 한다.

스택은 아래의 그림과 같이 사각형의 저장 공간을 뜻한다. 즉 4, 10 과 같은 데이터를 저장하는 공간으로, 리스트와 비슷하지만 저장 순서가 바뀌는 형태를 스택 자료구조(stack data structure)라고 한다.

스택의 사용 용도

앞서 언급한 택배 수화물을 생각해보자. 가장 늦게 배달되는 수화물을 트럭의 가장 깊숙히, 가장 먼저 배달되는 수화물을 트럭의 가장 앞에 배치 시킨다. 이와 같이 수화물에 대한 데이터도 이런식으로 저장한다면, 좀 더 쉽게 데이터를 관리할 수 있다.

파이썬에서도 리스트를 사용하여 스택을 구현할 수 있다. 리스트라는 저장 공간을 만든 후, append() 함수로 데이터를 저장(push)하고 추출(pop)한다.

a = [1, 2, 3, 4, 5]
a.append(10)
print(a)
a.append(20)
print(a)
a.pop() # 20이 추출된다.
a.pop() # 10이 추출된다.
print(a)

출력 결과:
[1, 2, 3, 4, 5, 10]
[1, 2, 3, 4, 5, 10, 20]
[1, 2, 3, 4, 5]

스택을 만들 수 있는 프로그램

스택으로 만들 수 있는 프로그램은 다양하다. 예를 들어 10진수를 2진수로 변환하는 프로그램, '이진수 변환기'가 있다. 2로 나눈 나머지 값을 스택에 푸시한 후, 마지막에 들어온 값부터 팝으로 추출하고 출력한다면 원하는 결과를 얻을 수 있다.

list = []
remain_num = 0

decimal_num = int(input("십진수 정수 기입: "))
while True:
    if decimal_num < 1:
        break
    remain_num = decimal_num%2
    decimal_num = decimal_num // 2
    list.append(remain_num)

for _ in range(len(list)):
    print(list.pop(),end='')

출력 결과:
십진수 정수 기입: 11
1011

위의 코드에서 for문의 루프 변수에 '_' 기호가 들어가 있다. 이는 파이썬에서 굉장히 많이 쓰이는 코드 중 하나이다. 일반 for문에서 많이 쓰이는데, for문에서 '-'기호는 해당 반복문에서 생성되는 값을 코드에 사용하지 않겠다는 의미이다.

또 다른 예로는 입력 받은 문자열을 역순으로 출력하는 프로그램이 있다.

word = input("Input a word: ")
# 받은 문자열을 리스트로 변환
world_list = list(word)
print(world_list)

result = []
# 받은 문자열을 추출하여 result리스트에 푸쉬
for _ in range(len(world_list)):
	result.append(world_list.pop())
print(result)
# 처음의 입력받은 문자열을 뒤에서부터 재 배열 
print (word[::-1])

큐(Queue)

스택과 반대 개념인 큐(Queue)는 스택과 다르게 먼저 들어간 데이터가 먼저 나오는 FIFO(First in First Out)의 메모리 구조를 가지는 저장 체계이다.
아래의 그림은 큐에서 일반적으로 사용할 수 있는 저장 체계이다. 기존에 삽입 시 offer(), 추출 시 poll()를 사용한다.

큐의 예로는 앞서 언급한 은행에서 대기 번호표를 뽑을 때 번호를 저장하는 방식이다. 먼저 온 사람이 앞의 번호표를 뽑고, 먼저 서비스를 받는다.

메모리 개념으로 볼 때, 큐는 스택보다 구현이 더 복잡하다. 스택은 메모리가 시작하는 지점이 고정되어 있는 반면, 큐는 처음 값이 저장된 메모리 주소가 값이 사용됨에 따라 계속 바뀌게 되어 구현에 좀 더 신경을 써야한다. 다행이도 파이썬에서는 이러한 부분이 스스로 구현되어 있어서 어렵지 않게 사용할 수 있다.

파이썬에서의 큐 구현

파이썬에서 큐를 구현하는 것은 매우 간단하다. 기본적으로 스택의 구현과 같은데, pop()함수를 사용할 때 인덱스가 0번째인 값을 쓴다는 의미로 pop(0)을 사용하면 된다. 즉, pop() 함수가 리스트의 마지막 값을, pop(0)은 리스트의 처음 값을 사용한다.

a = [1, 2, 3, 4, 5]
a.append(10)
print(a)
a.append(20)
print(a)
print(a.pop(0))
print(a.pop(0))
print(a)

출력 결과:
[1, 2, 3, 4, 5, 10]
[1, 2, 3, 4, 5, 10, 20]
1
2
[3, 4, 5, 10, 20]

튜플(tuple)

튜플(tuple)의 개념

튜플은 리스트와 매우 유사하다. 다만 튜플의 내용은 변경이 불가능하다. 어떻게 보면 튜플이 불편해 보이나, 어떤 경우에는 변경이 불가능한 것이 도움이 된다. 이유는 리스트는 변경이 가능한 객체이기에 실수로 요소가 추가되거나 삭제, 변경이 될 수 있기 때문이다. 또 튜플은 리스트에 비해 접근 속도가 빠르다. 아울러 튜플은 시퀀스의 일종이다. 따라서 시퀀스에 속하는 연산을 지원한다. 즉 인덱싱(indexing), 슬라이싱(slicing), 덧셈 연산(adding), 곱셈 연산(multiplying)이 지원된다.

튜플의 특징

• 튜플에는 정수, 문자열, 리스트 등 자료형을 섞어서 저장할 수 있다.
• 공백 튜플을 생성할 경우 단순히 소괄호() 만 적으면 된다.
• 만일 하나의 값 만을 저장할 경우 뒤에 꼭 쉼표(,)를 붙여줘야한다. 쉼표가 없다면 단순한 수식으로 처리되는데 예를 들어 (10)은 정수 10으로 받아들인다.

# 정수, 문자열, 리스트를 포함하는 튜플
test1 = (1,2,3)
test2 = ('안녕하세요')
test3 = ([1,2,3,4,5])

# 공백 튜플
test4 = ()

# 쉼표의 유무에 따라 다르게 받아들인다.
test5 = (10)
test6 = (10,)

print(test1)
print(test2)
print(test3)
print(test4)
print(test5)
print(test6)

출력 결과:
(1, 2, 3)
안녕하세요
[1, 2, 3, 4, 5]
()
10
(10,)

• 튜플도 리스트와 마찬가지로 내부에 다른 튜플을 가질 수 있다.
• 앞서 언급한 대로 튜플은 시퀀스이기에 모든 시퀀스 연산이 적용된다. 또 len(), min(), max()와 같은 함수들도 사용할 수 있다.
• 튜플은 변경이 불가한 객체이기에 만들어진 튜플의 요소는 변경될 수 없다.
• 두 개의 튜플을 합하여 새로운 튜플의 생성이 가능하다. 새로 만들어진 튜플의 변경은 불가하다.

# 내부에 다른 튜플을 가지는 튜플 u
t = (1, 2, 'hello!')
u = t, (1, 2, 3, 4, 5)
print(u)

# len 함수의 적용
numbers = (1, 2, 3, 4, 5)
print(len(numbers))

# 튜플의 변경은 불가하다.
t1 = (1, 2, 3, 4, 5)
t1[0] = 100

numbers1 = ( 1, 2, 3, 4, 5 )
colors = ("red", "green", "blue")
t1 = numbers1 + colors
print(t1)


출력 결과:
((1, 2, 'hello!'), (1, 2, 3, 4, 5))

5

Traceback (most recent call last):
  File "C:/Users/pc/OneDrive/바탕 화면/코딩/Python/test.py", line 7, in <module>
    t1[0] = 100
TypeError: 'tuple' object does not support item assignment

(1, 2, 3, 4, 5, 'red', 'green', 'blue')

• 튜플은 내장 튜플을 가질 수 있는데 상위 튜플의 요소는 하위 튜플의 주소를 가진다. 예를 들면 다음과 같다.
  상위 t3는 자체의 고유한 주소를 가지고 t3[0]은 t1의 주소를 가지고 있음을 확인할 수 있다. 마찬 가지로 t3[1]은 t2의 주소를 가지고 있다.

t1 = (1,2.2,"ㅎㅇ")
t2 = (3.3, 4,"ㅎㅇ")
t3 = t1 ,t2
print("t1 주소",id(t1))
print("t2 주소",id(t2))
print("t3 주소",id(t3))
print("t3[0]의 주소",id(t3[0]))
print("t3[1]의 주소",id(t3[1]))

출력 결과:
t1 주소 1954587382080
t2 주소 1954587382272
t3 주소 1954588502464
t3[0]의 주소 1954587382080
t3[1]의 주소 1954587382272

기본적인 튜플 연산들

튜플은 +와 와 같은 연산자에 반응한다. 리스트와 동일하게 +는 접합을 의미하고 *는 반복을 의미한다. 물론 튜플은 변경이 불가능하므로 연산의 결과는 새로운 튜플이 된다. 실제로 튜플은 시퀀스가 제공하는 모든 일반 연산을 사용할 수 있다.

파이썬 수식	결과	설명
len((1,2,3))	3	튜플의 길이
(1,2,3)+(4,5,6)	(1,2,3,4,5,6)	접합
('Hi',)*4)	('Hi','Hi','Hi','Hi')	반복
3 in (1,2,3)	True	멤버쉽
for x in (1,2,3): print x,	1 2 3	반복

인덱싱, 슬라이싱, 매트릭스

튜플도 시퀀스의 일종이기 때문에 인덱싱과 슬라이싱은 문자열이나 리스트와 동일하게 동작한다.

test = ('one','two','three')
# 인덱싱
print(test[0])
# 매트릭스
print(test[-2])
# 슬라이싱
print(test[1:])

괄호가 없는 튜플

튜플은 기본적으로 () 소괄호로 감싸는 것이 원칙이다. 하지만 만약 괄호가 없이 나열된 객체가 있다면 기본적으로 튜플로 간주된다.

t1 = 'physics', 'chemistry', 'c language'
t2 = 1, 2, 3, 4, 5
t3 = "a", "b", "c", "d"

print(type(t1))
print(type(t2))
print(type(t3))

출력 결과:
<class 'tuple'>
<class 'tuple'>
<class 'tuple'>

튜플의 내장 함수

튜플은 다음과 같은 내장 함수를 지원한다. 앞서 말한대로 시퀀스가 제공하는 모든 함수를 사용 가능하다.

함수	설명
t1.__eq__(t2)	2개의 튜플을 비교한다.
len(t)	튜플의 길이를 반환한다.
max(t)	튜플에 저장된 최대값을 반환한다.
min(t)	튜플에 저장된 최소값을 반환한다.
tuple(seq)	리스트를 튜플로 변환한다.

튜플의 대입 연산

파이썬은 튜플 대입 연산(tuple assignment)이라는 기능을 가지고 있다. 이 기능은 튜플에서 여러 개의 변수로 한 번에 값을 대입한다.

student1 = ("철수", 19, "CS")
(name, age, major) = student1
print(name)
print(age)
print(major)

출력 결과:
"철수“
19
"CS"

튜플에 값을 저장하는 과정을 튜플 패킹(tuple packing)이라고도 한다. 반대로 튜플에서 값을 꺼내어 변수에 대입하는 과정을 튜플 언패킹(tuple unpacking)이라고도 생각할 수 있다. 튜플 대입 연산을 가장 효과적으로 사용하는 예는 변수의 값을 교환할 때이다.

일반적인 프로그래밍 언어에서는 다음과 같은 문장으로 값을 교환한다.

temp = x
x = y
y = temp

하지만 튜플을 활용하여 간단하게 값의 교환이 가능하다.

# 괄호를 치지 않으면 기본적으로 튜플로 간주한다.
x,y = y,x
# 괄호를 친 경우
(x, y) = (y, x)

위에서 왼쪽은 변수들이 모인 튜플이며, 오른쪽은 값들이 모인 튜플이 된다. 값은 해당되는 변수에 대입된다. 대입되기 전에 오른쪽 수식들이 먼저 계산되므로 혼동이 발생할 소지는 없다.
당연하게도 변수의 개수와 값의 개수는 일치하여야 한다.

세트(Set)

세트(Set)는 수학의 집합이다. 세트는 중복되지 않은 항목들의 집합이다. 또한 세트는 순서가 없다. 만약 응용 프로그램에서 순서 없는 항목들의 집합을 원한다면 세트가 최선의 선택이 된다. 하지만 중복은 있어서는 안된다.
파이썬에서의 세트의 생성은 중괄호 기호({})이다.

세트의 중복을 불허한다는 점에서 프로그래밍에서 매우 유용하다.
대표적으로 종류를 세는 경우이다. 문서 하나에 들어가 있는 단어 종류의 개수를 셀 때 모든 단얼르 추출한 후 세트로 변환하면, 단어 종류의 개수를 쉽게 파악할 수 있다.

numbers = {2, 1, 3}
# 세트는 순서가 없기에 자동적으로 차례로 배치되어 출력된다.
print(numbers)
print(len(numbers))

출력 결과 : 
{1, 2, 3}
3

세트의 특징

• 세트는 튜플과 리스트와 동일하게 문자열 및, 정수, 세트 등 여러가지 자료형을 담을 수 있다.
• 비어있는 세트의 생성은 set()함수를 사용한다. 단순한 {}로 생성되지 아니한다.
• 어떤 항목이 세트 안에 있는지를 검사하려면 in 연산자를 이용하면 된다.
• 세트는 집합이기에 중복되는 요소는 자동으로 삭제된다.

cities = { "Paris", "Seoul", "London", "Berlin", "Paris", "Seoul" }
print(cities)
출력결과 : 
{'Seoul', 'London', 'Berlin', 'Paris'}

• 세트의 항목은 순서가 없기 때문에 위치를 가지고 세트의 항목(ex,인덱스)을 접근할 수는 없다. 하지만 for 반복문을 이용하여 각 항목들에 접근할 수 있다. 여기서 주의해야 할 점은 항목들이 출력되는 순서는 입력되는 순서와 다를 수 있다는 점이다. 단, 정수의 경우 재실행을 해도 패턴이 동일하지만, 문자열 타입의 실행은 매번 패턴이 달라진다. 만일 정렬된 순서를 출력하고자 한다면 아래와 같이 sorted() 함수를 사용해야한다.

test = {'a','r','e','a','d','b'}
for x in sorted(test):
    print(x, end=" ")
print("")
# 아래는 실행될 때마다 다르게 출력된다.
for x in test:
    print(x, end=" ")

출력 결과:
a b d e r 
d a b e r 

• 세트는 모든 요소들을 해싱(hashing)을 이용하여 저장하고 관리한다. 따라서 요소들이 해싱이 가능(hashable)하여야 한다. 해싱이란 아주 간단히 설명하면 각각의 객체들에 식별할 수 있는 숫자 코드를 부여하여 객체를 테이블에 저장하는 것이다.
  파이썬에서 요소가 해싱 가능하려면 해쉬 코드를 가져야 하며 그 값이 변경되면 안된다. 따라서 세트는 변경 가능한 요소를 가지면 안된다. 예를 들어 세트는 리스트를 가져선 안된다.반면에 변경이 불가한 튜플은 요소로 가질 수 있다.

numbers = {1, 2, [3, 4, 5]}
...
TypeError : unhashable type: list'

• 위의 특징대로 변경 가능한 리스트를 세트의 요소로 가지는 것은 불가하나 리스트와 문자열을 세트로 변경하는 것은 가능하다.

# 리스트 -> 세트
print(set([1, 2, 3, 1, 2, 3]))

# 문자열 -> 세트
# 출력결과는 계속 바뀐다.
print(set("abcdefa"))
    
 
출력결과 : 
{1, 2, 3}
{'c', 'a', 'f', 'b', 'd', 'e'}

요소 추가하고 삭제하기

세트는 변경 가능한 객체이다. 따라서 세트에 요소를 추가하거나 삭제할 수 있다. 앞서 말한대로 세트의 요소에는 인덱스가 없기 때문에 인덱싱이나 슬라이싱 연산은 의미가 없다.

numbers = { 2, 1, 3 }
print(numbers[0])

출력 결과:
TypeError: 'set' object does not support indexing

세트의 요소 추가는 add()메소드,update()메소드가 있다. 둘의 차이는 추가시킬 요소의 개수 차이다. add()는 하나의, update()는 여러개의 요소를 추가할 수 있다. 물론 중복되는 요소는 추가되지 않는다.

요소의 삭제는 remove()메소드, discard()메소드, clear()메소드가 있다. remove()와 discard()의 경우 요소를 삭제 시키는데 remove()의 경우 없는 요소를 삭제시킬려고 한다면 오류를 발생한다. clear()은 세트의 모든 요소를 삭제한다.

pop()를 이용하여 요소의 삭제가 가능하지만 임의로 아무요소를 삭제한다.

numbers = { 2, 1, 3 }

# add
numbers.add(4)
print(numbers)

# update
numbers.update('사람',['인간',2, 3, 4, 5]) 
# 리스트 안에 있고 없고에 따라 다르게 저장된다.
print(numbers)

# discard
# 리턴 타입이 없다.
numbers.discard(1)
print(numbers)

# remove
#numbers.remove(7)
## 7은 세트의 없는 요소이기에 오류를 발생시킨다.
# 그렇기에 보통 if문과 함께 사용한다.

# clear
numbers.clear()
print(numbers)

# pop
test = {0,1,2,3,4,5}
for _ in range(len(test)):
    print(test.pop(), end="")
print('\n현재 test의 크기: ',len(test))

출력 결과 :
{1, 2, 3, 4}
{1, 2, 3, 4, 5,'인간','사','람'}
{2, 3, 4, 5}
set()
012345
 현재 test의 크기: 0

부분 집합 연산

2개의 세트가 같은지에 대해 검사할 수 있다. 이는 ==, =! 연산자를 사용한다.

A = {1, 2, 3}
B = {1, 2, 3}
print(A == B)

출력결과 : True

또한 두 세트의 관계에 대해서 <와 <=의 연산자를 통해 진부분 집합인지, 부분 집합인지를 검사할 수 있다. 또한 진상위 집합인지, 상위 집합인지 또한 검사가 가능하다.

A = {1, 2, 3, 4, 5}
B = {1, 2, 3}
print(B < A)

출력결과 : True

연산자가 아닌 메소드를 통해서 부분 진합인지, 상위 집합인지 검사할 수 있다.
부분 집합의 검사는 issubset()를 통해, 상위 집합의 검사는 isupperset()을 통해 할 수 있다.

A = {1, 2, 3, 4, 5}
B = {1, 2, 3, 4, 5}
# B는 A의 부분 집합인가?
print(B.issubset(A))

A = {1, 2, 3, 4, 5}
B = {1, 2, 3}
# A는 B의 상위 집합인가?
print(A.issuperset(B))

출력 결과:
True
True

집합 연산

세트가 유용한 이유는 교집합이나, 합집합, 차집합과 같은 여러 집합 연산을 지원하기 때문이다. 이것은 연산자 또는 메소드를 통해 구현할 수 있다.

합집합은 두 개 이상의 집합을 합하는 연산이다. 물론 중복되는 요소는 제외된다. 합집합은 | 연산자, union()메소드를 사용한다.

교집합은 두 개 이상의 집합에서 겹치는 요소를 구하는 연산이다. 교집합은 & 연산자와 intersection() 메소드를 사용한다.

차집합은 하나의 집합에서 다른 집합의 요소를 빼는 것이다. 차집합은 -연산자나 difference()메소드를 사용한다.

A = {1, 2, 3, 4}
B = {1, 2, 5, 6}

# 합집합
print(A | B)
print(A.union(B))
print(B.union(A))

# 교집합
print(A & B)
print(A.intersection(B))

# 차집합
print(A-B)
print(B.difference(A))

출력 결과:
{1, 2, 3, 4, 5, 6}
{1, 2, 3, 4, 5, 6}
{1, 2, 3, 4, 5, 6}
{1, 2}
{1, 2}
{3, 4}
{5, 6}

집합에 대해서도 all(), any(), isdisjoint() ,enumerate(), len(), max(), min(), sorted(), sum() 등의 메소드는 사용할 수 있다.
all()은 세트의 모든 요소가 True인 경우에 세트가 True가 된다. any()는 하나의 요소라도 True이면 True를 반환한다. isdisjoint()는 두 개의 세트를 비교하여 모든 요소가 다르다면 True를 출력한다.

# all()집합에서 모든 값이 참이어야만 참을 리턴해준다.
# any()집합에서 단 하나라도 참이면 참을 리턴해준다.
test = {0,1,2,3,4,5}
test1= {10,20,30}
# 기본적으로 0을 제외한 모든 수는 참이다.
# 아래의 연산은 0으로 인해 False가 출력된다.
print("all()의 결과: ",all(test))
print("all()의 결과: ",any(test))
print("같은 요소가 존재하지 않는가? : ",test.isdisjoint(test1))

출력 결과:
all()의 결과:  True
all()의 결과:  True
같은 요소가 존재하지 않는가? :  True