선형 자료구조 ( python 자료구조, 자료형, 추상 자료형의 차이 )

Konseo·2023년 10월 7일

알고리즘 알고리즘 개념

알고리즘

목록 보기

17/21

선형 자료구조에 해당하는 배열, 연결리스트, 스택, 큐, 데크, 우선순위 큐, 해시테이블에 대해 간단히 정리하고 자료구조, 자료형, 추상 자료형의 차이점에 대해 명확히 알아보자 🕵 💭

선형 자료구조

데이터 요소가 순차적으로 배열되는 자료구조를 선형 자료구조라고 함
즉, 선형 자료구조는 단일 레벨로 구성됨
따라서 한 번에 탐색이 가능하며, 구현하기도 쉽다.
종류 : 배열, 스택, 큐, 연결 리스트 등

자료구조 방식

메모리 공간 기반의 연속(Contiguous) 방식
- ex. 배열
포인터 기반의 연결(Link) 방식
- ex. 연결 리스트

추상 자료형(Avstract Data Type)의 실제 구현 대부분은 배열 또는 연결 리스트를 기반으로 한다. 예를 들어 스택은 연결 리스트로 구현하고, 큐는 배열로 구현하는 식이다. 물론 반대의 경우도 충분히 가능하다.

배열

연속 방식의 가장 기본이 되는 자료형
특정 인덱스에 접근하기 위한 시간 복잡도 : O(1)
파이썬에서는 리스트라는 동적 배열 자료형을 지원한다
- 참고로 리스트는 접근, 탐색, 삽입, 삭제의 기능이 있는 추상 자료형으로 분류된다 (why? 리스트가 동적 배열을 사용하므로)

연결리스트

포인터 방식의 가장 기본이 되는 자료형
다양한 추상 자료형 구현의 기반이 됨
동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 물리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉬움
특정 인덱스에 접근하기 위한 시간 복잡도 : O(n)
- 배열과 달리 연결 리스트는 특정 인덱스에 접근하기 위해서 전체를 순서래도 읽어야하므로 상수 시간에 접근할 수 없다.
파이썬에서 연결리스트를 지원하는 자료형이 있는가?
- 연결리스트는 C언어에서의 중요한 데이터 구조인데, 파이썬은 리스트가 연결리스트의 모든 기능을 지원하고 있다.
- 배열 이어붙이기, 중간 삽입, 삭제 등

스택

LIFO
push()와 pop()을 주요 연산으로 갖는 추상 자료형
파이썬에서는 스택 자료형을 별도로 제공하지 않지만 리스트가 스택의 모든 연산을 지원한다

큐

FIFO
파이썬에서는 큐 자료형을 별도로 제공하지 않지만 리스트가 스택의 모든 연산을 지원한다(스택과 동일)
그러나 리스트는 동적 배열로 구현되어 있어 큐의 연산을 수행하기에는 효율적이지 않기 때문에, 큐를 위해서는 데크라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다.

스택과 큐는 각각의 특징이 뚜렷하지만 별도로 구분해 사용하기가 번거로운 만큼, 한 번에 두 자료형의 특징을 모두 갖고 있는 복합 추상 자료형이 있다면 훨씬 더 편하게 사용할 수 있을 것이다.

데크

데크는 스택과 큐의 연산을 모두 갖고 있는 복합 추상 자료형이다
Double-Ended Queue의 줄임말이다
큐를 일반화한 형태의 추상 자료형
양쪽에서 삭제와 삽입을 모두 처리할 수 있다.
데크의 구현은 배열이나 연결리스트 모두 가능하지만, 이중 연결 리스트로 구현 하는 편이 가장 잘 어울린다.
파이썬은 데크 자료형을 collections 모듈에서 deque 라는 이름으로 지원한다.

우선순위 큐

데크와 동일하게 스택과 큐의 연산을 모두 갖고 있는 복합 추상 자료형이다
추출 순서가 일정하게 정해져 있지 않다. 즉, 스택과 큐와 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다고 생각하면 된다. 그래서 데이터를 제거할 때 가장 작은 값 먼저 제거된다
결국 내부적으로 정렬하는 매커니즘을 갖고 있다는 뜻인데, 이는 heapq 을 통해 구현되어있다.

파이썬은 우선순위 큐를 queue 모듈에서 PriorityQueue 라는 이름으로 지원한다.

from queue import PriorityQueue

q = PriorityQueue() 
q1 = PriorityQueue(maxsize=10) # maxsize를 활용하면 삽입할 수 있는 원소 크기 제한 가능

q.put(3) # 원소를 넣는 과정
q.put(4)
q.put(1)

q1.put((1, 'apple')) # (우선순위, 값)의 형태로 저장할 수도 있음

# 원소 삭제 및 반환
q.get() # 1
q1.get()[1] # (우선순위, 값)의 형태에서 값 반환

heapq을 import해서 사용하여도 된다.

import heapq

hq = []
heapq.heappush(hq, 4)
heapq.heappush(hq, 1)
heapq.heappush(hq, 3)
heapq.heappush(hq, 7)

heapq.heappop(hq) # 1

해시 테이블

해시 테이블 또는 해시 맵은 키를 값에 매칭할 수 있는 구조인, 연관 배열 추상 자료형(ADT)를 구현하는 자료구조이다.
해시 테이블의 가장 큰 특징은 대부분의 연산의 시간 복잡도가 O(1)이라는 것이다. 때문에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다는 장점이 있다.
해시 함수
- 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수
해싱
- 해시 테이블을 인덱싱하기 위해 해시함수를 사용하는 것
충돌이 발생할 경우
- 개별 체이닝 기법 또는 오픈 어드레스 기법을 사용
- 파이썬의 경우 오픈 어드레스 기법을 사용 중임

자료구조, 자료형, 추상 자료형

자료구조 및 알고리즘을 공부하다보면 자료구조(Data Structure), 자료형(Data type), 추상 자료형(Abstract Data Type) 이라는 용어들이 여러 차례 번갈아 등장한다. 각 단어는 서로 비슷해 보이지만 분명한 차이가 있는 만큼 각각의 정의에 대해 명확하게 구분할 수 있도록 살펴보자

먼저, 컴퓨터과학에서 자료구조란 데이터에 효율적으로 접근하고 조작하기 위한 데이터의 조직, 관리, 저장 구조를 말한다. 우리가 일반적으로 얘기하는 학문으로서의 자료구조를 일컫는다.

보통 자료형과 자료구조를 많이 혼동하는데, 자료형이란 컴파일러 또는 인터프리터에게 프로그래머가 데이터를 어떻게 사용하는지를 알려주는 일종의 데이터 속성(Attribute)이다. 좀 더 쉽게 말하자면 자료형은 자료구조에 비해 훨씬 더 구체적이며, 특정 언어에서 자료형이라 함은 정수(integer), 실수(floatinf-point Number), 문자열(string) 등 해당 언어에서 지원하는 원시 자료형(Primitive Data Type)까지 포함하는 모든 자료의 유형을 말한다.

자료구조는 일반적으로 원시 자료형을 기반으로 하는 배열, 연결 리스트, 객체 등을 말하며, 자료형의 관점에서 보자면 여러 원시 자료형을 조합한 자료구조는 복합 자료형(Comopositive Data Type)이 된다.

마지막으로 추상 자료형은 일반적으로 줄여서 ADT라 부르며 자료형에 대한 수학적 모델을 지칭한다. 좀 더 쉽게 정리하자면, ADT란 해당 유형의 자료에 대한 연산들을 명기한 것이다. ADR는 행동만을 정의할 뿐 실제 구현 방법은 명시하지 않는다. ⭐️ 이런 점에서 자료구조와는 다르다. OOP에 대한 경험이 있다면 추상화(Abstraction)를 떠올리면 이해하기 쉬울 것이다. 추상화는 필수적인 속성만 보여주고, 불필요한 정보는 감추는 것을 의미하는데 이처럼 인터페이스만 보여주고 실제 구현은 보여주지 않는다는 점에서 ADT는 OOP의 추상화와 비슷한 개념이라 할 수 있다.