python_자료구조

객체지향설계, 파이썬 고급주제는 향 후 시간이 남을때 한번 정리하기로 하고, 이제 알고리즘 세상 속으로 들어가보자.

 

추상 데이터 타입(abstract data type)은 유사한 동작을 가진 자료구조의 클래스에 대한 수학적 모델을 가르키며, 각기 크래스는 다르지만, 기능적으로 동일하게 구현된 자료구조를 가질 수 있다.

 

먼저 알고리즘을 이해하기전 자료구조에 대해 알아보자.

자료구조는 크게 배열 기반 연속방식과 포인터 기반의 연결 방식으로 분류한다.

 

스택(stack)

큐(queue)

데크(deque)

우선순위 큐(priority queue)

힙(heap)

연결 리스트(linked list)

해시 테이블(hash table) 

 

스택(stack) - 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조형식이며, 배열 인덱스 접근이 제한되고 LIFO(last in, first out) 구조이다.

스택의 대표적인 함수는 아래와 같다.

push-(맨 끝에 항목 삽입)

pop-(맨 끝 항목 반환 및 제거)

top/peek-(맨 끝 항목 조회)

empty-(비어 있는지 확인)

size-(크기 확인)

파이썬에서는 리스트의 append()와 pop()메소드로 스택을 구현할 수 있다.

스택은 깊이 우선 탐색(DFS)에서 유용하게 사용되므로, 한번쯤 구현해봐야한다.

스택 코드 - 클릭

 

 

큐(queue) - 스택과 다르게 항목이 들어온 순서대로 접근이 가능하다. 즉, 먼저 들어온 데이터가 먼저 나가는 FIFO(first in, first out) 구조이다. 큐 역시 배열의 인덱스 접근이 제한된다.

enqueue-(뒤쪽에 항목 삽입)

dequeue-(앞쪽 항목 반환하고 제거)

peek/front-(큐 앞쪽의 항목 조회)

empty-(비어 있는지 확인)

size-(크기 확인)

큐도 마찬가지로 파이썬의 리스트를 이용하여 구현할 수 있다.

코드에서는 insert 함수를 이용하였는데, 리스트 두개를 이용해서 구현하면 더 효율적으로도 구현 할 수 있다.

큐 코드 - 클릭

 

 

 

데크(dequeue) - 스택+큐 형식이라고 생각할 수 있다. 양쪽 끝에서 조회,삽입,삭제가 가능하다. 앞서 구현한 큐 코드를 조금만 변형시켜서 구현 할 수 있다.

여기서도 insert를 이용하기 때문에 비효율적인데, 파이썬에서 제공하는 collections 패키지의 deque 모듈을 사용하면 이 문제가 해결된다.

from collections import deque

데크 코드 - 클릭

 

 

우선순위 큐(priority queue)와 힙(heap) - 스택과 큐와 비슷한 타입이지만, 각 항목마다 연관된 우선순위가 있다. 두 항목의 우선순위가 같으면 큐의 순서를 따른다. 우선순위 큐는 힙을 사용하여 구현한다.

힙(heap)은 각 노드가 하위 노드보다 작은(또는 큰) 이진 트리다. 일반적을 가장 작은 요소에 반복적으로 접근하는 프로그램에 유용하다. 최소 힙을 사용하면 가장 작은 요소를 처리하는 시간복잡도는 O(1) 이고 조회 추가 수정을 처리하는 시간복잡도는 O(logn)이다.

 

headpq 모듈은 효율적으로 시퀀스를 힙으로 유지하면서 항목을 삽입하고 제거하는 함수 제공

headpq를 이용하여 간단하게 구현할 수 있다.

참고자료 - 클릭

 

그 외에도 최대힙 최소힙, 해시테이블, 연결리스트는 조만간 업데이트 해야겠다.

 

 

-reference : 파이썬 자료구조와 알고리즘