[자료구조] 배열, 스택, 큐, 연결 리스트, 트리, 해시 테이블, 그래프

배열(Array, List)

배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음

 

 

✨ 사용 사례

. 순차적인 데이터를 저장하며 값보다는 순서가 중요할 때
. 다차원 데이터를 다룰 때
. 어떤 특정 요소를 빠르게 읽어야 할 때
. 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때

 

🚩리스트 / 튜플 / 딕셔너리

① 리스트 (list)

. 리스트는 어떠한 모음이라고 생각하면 이해하기 쉽다.

. 파이썬 리스트는 다른 언어의 배열과는 다른 점이 있는데, 바로 요소의 자료형을 통일해주지 않아도 된다는 것이다.

Haedal_character = ['해달이', '시라용', '아리', '매기', '사스미']

② 튜플 (tuple)

. 튜플은 리스트와 거의 유사하지만 수정할 수 없다는 특징을 가지고 있다.
. 변수와 상수에 비유하자면, 리스트는 변수이고(수정 가능) 튜플은 상수이다(수정 불가능).

 mytuple = (1, 2, 5, 4, 3)

 

③ 딕셔너리 (dictionary)

. 리스트나 튜플은 인덱싱을 통해 값에 접근하는데 반해 키(Key)와 값(Value)으로 구성되는 딕셔너리는 키를 통해 값에 접근한다는 것이 가장 큰 특징이다.

Haedal_character = {'이름':'해달이', '나이':1, '핸드폰 번호':'01012345678'}
Haedal_character['이름']  ##'해달이'

 

④ 집합 (set)

. 중복을 허용하지 않고, 순서가 없다는 집합 자료형의 특징인데, 이는 리스트와 튜플과의 차이점이라고 할 수 있겠다. 순서가 없기 때문에 인덱싱, 혹은 슬라이싱을 하기 위해서는 리스트나 튜플로 변환해 준 다음에 해야 한다.

. 집합을 만들 때에는 set() 키워드와 리스트를 만들 때 사용하는 대괄호[]를 활용하거나, 문자열을 활용해서 만들 수 있다. 또한 간단하게 중괄호 {}를 사용해도 된다.

a = set([1, 2, 3])			## {1, 2, 3}
b = set('hello Haedal')			## {'h', 'H', 'e', 'a', 'd', ' ', 'l', 'o'}
c = {'Hello', 'I`m', 'Haedal'}		## {'I`m', 'Hello', 'Haedal'}

 

 

---

스택(Stack)

스택은 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조.

 

 

✨ 사용 사례

. 재귀 알고리즘을 반복문을 통해서 구현할 수 있게 해줌
. 실행 취소 (undo)
. Backtracking
. 웹 브라우저 뒤로가기
. 구문분석
. 후위(postfix) 표기법 연산
. 문자열의 역순 출력 등

 

ex. 수식의 괄호의 유효성 검증하기

수식의 소괄호, 중괄호, 대괄호가 맞게 쓰였는지 판단하는 알고리즘을 스택을 통해 구현할 수 있다. 수식을 왼쪽부터 한글자씩 읽어서, 여는 괄호 (,{,[ 를 만나면 스택에 push 하고, 닫힌 괄호를 만나면 스택에서 pop하여 딕셔너리의 쌍을 이루는 괄호인지 검사한다. 끝까지 검사한 후에는 스택에 비어있어야 올바른 수식이다. 

def solution(expr):
    match = {')' : '(', 
             '}':'{', 
             ']':'['
            }         # 맞는 괄호를 딕셔너리로 지정
    
    S = ArrayStack()
    for c in expr:
        if c in '({[':    # 여는 괄호를 스택에 넣음
            S.push(c)
            
        elif c in match:  # 닫힌 괄호(key)일 때
            
            if S.isEmpty():  # 만약 스택이 비어있으면 False
                return False
            
            else:
                t = S.pop()
                if t != match[c]:  # 스택에 담긴 괄호(열린괄호)와 닫힌 괄호가 같지 않으면
                    return False
                
    return S.isEmpty()   # 끝까지 검사한 후 스택이 비어있어야 올바른 수식

 

(+) 스택관련 문제 유형: https://velog.io/@kimyunbin/Stack-80esrsjx

---

큐(Queue)

큐는 먼저 집어넣은 데이터가 먼저 나오는 FIFO (First In First Out) 구조로 저장하는 선형 자료구조

✨사용 사례

. 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기시킬 때 사용합니다.
    ex) CPU 스케줄링, 디스크 스케줄링
. 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용합니다. (비동기 전송)
   ex) IO 버퍼, 파이프, 파일 IO 

 

✔️ 파이썬 문제 유형

BFS(너비우선탐색) 구현에는 큐를 이용하는 것이 정석인데, 그 이유는 BFS는 인접한 노드부터 차례로 넓게 탐색하는 알고리즘이기 때문이다. (BFS에 대해서는 따로 설명하지 않겠다) Python에는 친절하게도 deque 라이브러리가 존재해서, 큐 자료구조를 이용하고 싶을 때는 관련 라이브러리를 다음과 같이 import 해 이용하면 된다. 

 

---

🚩 stack + queue == deque

collections 모듈의 deque는 double - ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.

deque는 양방향이기 때문에 append(), pop()과 더불어 appendleft(), popleft() 메소드가 있어 각각 맨 앞에 데이터를 삽입하거나 맨 앞에서 제거할 수 있다

from collections import deque

dq=deque() # 덱 생성
dq.append() # 덱의 가장 오른쪽에 원소 삽입
dq.popleft() # 가장 왼쪽 원소 반환
dq.appendleft() # 덱의 가장 왼쪽에 원소 삽입
dp.pop() # 가장 오른쪽 원소 반환
dp.clear() # 모든 원소 제거
dp.copy() # 덱 복사
dp.count(x) #x와 같은 원소의 개수를 계산

'''공식문서 : https://docs.python.org/3.8/library/collections.html#collections.deque'''

 

---

연결리스트(Linked List)

연결 리스트는 데이터와 포인트로 구성된 노드 간의 연결(link)을 이용해서 리스트를 구현한 자료구조

 

 

📌 배열 vs. 연결리스트

. 배열은 물리적인 메모리 주소가 연속적이고, 연결리스트는 물리 메모리 주소가 연속적이지 않고 랜덤이다.

. 배열은 삽입/삭제가 O(n)의 시간이 걸리지만, 동적으로 연결된 연결리스트는 삽입/삭제에 O(1)이 걸린다.

. 배열은 각 원소에 인덱스로 O(1)의 시간으로 손쉽게 접근이 가능하다. 그러나 연결리스트는 O(n)의 시간이 소요된다. (배열과 다르게 연결된 메모리가 아니기 때문에, 데이터를 찾기 위해서는 모든 노드를 거쳐서 탐색해야 한다.)

 

✔️ 종류

. 이중 연결 리스트

 

 

 

✔️ 삽입

 

✔️ 삭제

 

---

트리(Tree)

트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조

 

 

✨ 사용 사례

① 계층 적 데이터 저장
트리는 데이터를 계층 구조로 저장하는 데 사용됩니다. 예를 들어 파일 및 폴더는 계층적 트리 형태로 저장됩니다.

 

② 효율적인 검색 속도
효율적인 삽입, 삭제 및 검색을 위해 트리 구조를 사용합니다. 

 

③ 데이터 베이스 인덱싱

데이터베이스 인덱싱을 구현하는데 트리를 사용합니다.
예) B-Tree, B+Tree, AVL-Tree..

 

✔️ 종류

. 포화 이진 트리(full binary tree) : 모든 레벨에서 노드들이 모두 채워져 있는 트리
. 완전 이진트리(complete binary tree): 마지막 레벨을 제외하고 노드가 모두 채워져 있는 트리, 마지막 레벨도 오른쪽으로 연속된 몇개의 노드만 비어있을 수 있음, 왼쪽부터 차례로 채워나감

 

 

---

해시 테이블(Hash Table)

해시 테이블(Hash table)이란 검색하고자 하는 키값을 입력받아서 해쉬 함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조

 

 

 

 

---

그래프(Graph)

그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조입니다.
. 정점(Vertex) : 자료를 저장하려는 자료의 단위, 노드(Node)라고도 말함.
. 간선(Edge) : 정점 사이를 연결하는 선으로 두 정점 쌍 (u, v)로 표현함.

 

 

 

 

 

 

 

 

📌 출처

https://yoongrammer.tistory.com/category/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%20%28Data%20structure%29?page=3