(파이썬 다시 보기)파이썬, python: 5. 자료구조

목차

 

1. 배열(Array): 리스트 타입

- 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

- 장점: 시작 위치만 알면 Index를 통하여 접근 가능 (메모리의 효율적인 사용)
- 단점: 데이터를 삽입, 삭제할 경우, 기존 데이터들의 위치까지 변경해야 할 수 있음

# 2차원 배열
my_array = [[1, 2, 3], [4, 5, 6],[7, 8, 9]]
my_array[0][1] # 정수형 반환
>>> 2

my_array = ['123', '456', '789']
my_array[0][1] # 문자열 반환
>>> '2'

 

1-1. 예제 1: 2차원 배열에서 모든 요소에 1을 더하기

my_array = [[1, 2, 3], [4, 5, 6],[7, 8, 9]]
for i in range(len(my_array)): # 3 번 행을 돈다.
    for j in range(len(my_array[i])):
        # print(i, j)
        my_array[i][j] += 1 

print(my_array)
>>> [[2, 3, 4], [5, 6, 7], [8, 9, 10]]

 

1-2. 예제 2: 2차원 배열에서 특정 값 위치 찾기

my_array = [[1, 2, 3], [4, 5, 6],[7, 8, 9]]
search_value = 7 # 7 => (2, 0) 위치에 있음

for i in range(len(my_array)):
        for j in range(len(my_array[i])):
            if my_array[i][j] == search_value:
                  print(f'{search_value}은 ({i}, {j})에 위치해 있음')
>>> 7은 (2, 0)에 위치해 있음

 

2. 큐(Queue)

- FIFO (First-In, First-Out) 구조
- 파이썬: collections의 deque 또는 queue 라이브러리 사용하여 구현 -> 주로 deque 사용
- enqueue는 데이터 In(추가하기), dequeue는 데이터 Out(꺼내기)
- Priority Queue 라는 특수한 Queue도 있음 (단순 선입선출이 아닌, 우선순위가 높은 것이 먼저 Out)
-> Priority Queue는 queue 라이브러리에만 있음

- popleft() 사용

 

2-1. 클래스로 큐 구현

- 리스트를 사용하기 때문에, 성능이 좋지는 않음

- 실제 알고리즘 테스트에서는 deque 라이브러리를 사용하는 것이 좋음

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        return self.items.pop(0)
    
    def size(self):
        return len(self.items)
    
    def is_empty(self):
        return self.items == []

 

예제 1: 1부터 10까지 합을 구하기

queue = deque()
for i in range(1, 11):
    queue.append(i)
    
sum_val = 0
while queue:
    num = queue.popleft()
    sum_val += num

print(f'1부터 10까지의 합: {sum_val}')
>>> 1부터 10까지의 합: 55

 

3. 스택

- LIFO (Last In, First Out) 구조 (후입선출, 접시를 쌓아 놓은 것)
- 파이썬: 리스트 또는 collections의 deque 라이브러리 사용하여 구현 가능
- 활용: 함수 실행 순서와 유사 (재귀함수)
- push는 데이터 In(추가하기), pop은 데이터 Out(꺼내기)

- pop() 사용

 

3-1. 예시 1: 함수 호출

# 스택 활용 예시: 함수 호출
def print_numbers(n):
    if n == 0:
        return
    print_numbers(n-1)
    print(n, '함수 호출 종료')

print_numbers(5)
>>> 1 함수 호출 종료
	2 함수 호출 종료
	3 함수 호출 종료
	4 함수 호출 종료
	5 함수 호출 종료

 

4. 링크드리스트

- 배열은 순차적으로 연결된 공간에 저장하는 방식이라면, 떨어진 곳에 존재하는 데이터를 화살표로 연결
하는 데이터 구조
- 파이썬에서는 리스트 데이터 타입이 링크드 리스트의 기능을 모두 지원
- 위치값(인덱싱)으로 바로 원하는 값에 접근을 불가능하지만, 다음 노드 위치 변경하여 삽입과 삭제 가능
- 링크드 리스트 끝에 데이터 추가, 전체 값 출력, 중간에 데이터 추가, 특정값 삭제 실습

 

4-1. 클래스로 링크드리스트 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
class LinkedList:
    def __init__(self):
        self.head = None

 

5. 해시테이블

- 해시 테이블: Key와 Value를 저장하는 데이터 구조
- Index 처음부터 확인하며 탐색할 필요 없이, 바로 key 있는 위치로 접근 가능
- 파이썬에서 딕셔너리 데이터 타입에 구현되어 있음
- 충돌 문제 (다른 key 인데, 해시 값이 동일한 경우) 해결 필요
• Chaining 기법: 해시 테이블 외 공간을 활용 (링크드 리스트)
• Linear Probing 기법: 충돌이 일어난 해시값 다음부터 맨 처음 나오는 빈공간에 저장
- 해시 함수 SHA의 활용: 비밀번호의 저장과 확인 (실제 비밀번호를 저장하지 않음)

 

5-1. 단순한 형태의 해시 테이블

size = 10
table = [0 for _ in range(size)]
table

# key -> 인덱스 (해시 함수)
def hash_function(key):
    return key % size

def insert(key, value):
    hash_key = hash_function(key) # hash_key는 해시테이블의 index
    table[hash_key] = value

def search(key):
    hash_key = hash_function(key)
    return table[hash_key]
    
insert(11, 'one') # 11이 key이고, 'one'이 value
insert(23, 'three')
insert(37, 'seven')

table
>>> [0, 'one', 0, 'three', 0, 0, 0, 'seven', 0, 0]

search(11)
>>> 'one'

 

6. 이진탐색트리

- 그래프 → 트리 → 이진 트리 → 이진 탐색 트리
(이진 검색 트리 조건: 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값)
- 탐색 속도가 빠름
- 트리의 균형이 있게 트리가 만들어져야 검색이 빠름
(균형 맞추는 데이터구조도 있음: 자가 균형(self-balancing) 이진 탐색 트리)

 

 

7. PriorityQueue Heap

- 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

- 우선순위가 동일할 경우, 값들 중에서는 오름차순으로 가져옴
- 데이터 추가 (우선순위가 낮을 수록 높은 순위를 가짐)

from queue import PriorityQueue
pq = PriorityQueue()

# 데이터 추가 (우선순위가 낮을 수록 높은 순위를 가짐)
pq.put([10, 'ten']) # [우선순위, 값] 
pq.put([1, 'one'])
pq.put([2, 'two'])

# 데이터 가져오기
pq.get()
>>> [1, 'one']

pq.qsize()
>>> 2

pq.get()
>>> [2, 'two']

pq.qsize()
>>> 1