선형 자료 구조 (feat. 파이썬)

young.h·2022년 5월 5일

CS

목록 보기

1/6

선형 자료 구조

데이터가 순차적으로 배열되는 자료구조

1. 배열
2. 연결리스트
3. 스택
4. 큐, 우선수위 큐
5. 해시 테이블

1. 배열

값 또는 변수 엘리먼트의 집합으로 하나 이상의 인덱스 또는 키로 식별됩니다.
배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말합니다. 크기가 고정되어 있고, 한 번 생성한 배열은 크기를 변경하는 것이 불가능합니다.
어느 위치에나 O(1)로 조회 가능합니다. 그래서 조회가 많이 일어나는 데에 적합한 자료구조입니다.
?? 동적 배열 ??
배열의 크기 변경이 불가능하다는 불편함을 해소하기 위해 등장한 게 동적 배열입니다. 자바에서는 ArrayList, 파이썬에서는 리스트가 동적 배열 자료형입니다.(파이썬은 정적 배여링 아예 없음)
어떻게 동작할까? 초깃값을 작게 잡아 배열을 생성하고, 데이터가 꽉 채워지면 늘려주고 모두 복사하는 식으로 크기를 늘려줍니다.

2. 연결리스트

데이터 요소의 선형 집합으로 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다.
메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽고 삽입, 삭제가 간편합니다.
데이터를 구조체로 묶어서 포인트로 연결. 그래서 메모리 어딘가에 데이터가 서로 연결된 형태로 여기저기 흩뿌려져있다.
특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야하기 때문에 O(n) 시간 소요됨. 반면 시작/ 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능

3. 스택

LIFO(Last In First Out)
회전 초밥 접시와 같습니다. 접시는 먹은 순서대로 쌓일 것이고 가져가서 설거지를 할 때는 제일 마지막에 먹은 접시를 가장 먼저 설거지할 것입니다.

class Node:
    def __init__(self, item, next):
        # 노드의 값
        self.item = item
        # 노드를 가리키는 포인터
        self.next = next

class Stack:
    def __init(self):
        self.last = None

    def push(self, item):
        self.last = Node(item, self.last)

    def pop(self):
        item = self.last.item
        self.last = self.last.;next
        return item

4. 큐, 우선수위 큐

FIFO - 맛집 줄서기 (BFS에 사용)

# 큐를 이용한 스택 구현
class MyStack:
    def __init__(self):
        self.q = collections.deque()

    def push(self, x):
        self.q.append(x)
        #요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q) -1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q) == 0

# 두 개의 ㄴ스택를 이용한 큐 구현
class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x):
        self.input.append(x)

    def pop(self):
        self.peek()
        return self.output.pop()

    def peek(self):
        # output이 없으면 모두 재입력
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self):
        return self.input == [] and self.output == []

5. 해시 테이블

해시 함수
임의의 크기 데이터를 "고정 크기 값"으로 매핑하는 데 사용할 수 있는 함수로
성능 좋은 해시 함수는 해시 함수 값 충돌이 적고, 해시 테이블 전체에 해시 값이 균일하게 분포하게 하는 등의 특징이 있습니다.

아래 예에서 화살표의 역할
ABC -> A1
22846C -> CB

해싱한다?
해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것

좋은 해시 함수란?

해시 함수 값 충돌의 최소화
쉽고 빠른 연산
해시 테이블 전체에 해시 값이 균일하게 분포
사용할 키의 모든 정보를 이용하여 해싱
해시 테이블 사용 효율이 높을 것

로드 팩터

해시 함수를 재작성해야 될지/ 해시 테이블 크기를 조정해야 할지 결정하는 요소

로드 팩터 = n / k
n: 해시 테입을에 저장된 데이터 개수
k: 버킷의 개수

충돌 해결 방법

개별 체이닝
- 충돌 발생시 연결 리스트로 연결
- 원리
1. 키의 해시 값을 계산
2. 해시 값을 이용해 배열의 인덱스를 구함
3. 같은 인덱스가 있으면 연결 리스트로 연결
오픈 어드레싱
- 충돌 발생시 테이블 공간 내 탐사해서 빈 공간을 찾아 해결
- 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장 없음
- 테이블의 데이터가 고르게 분포되지 않고 뭉침(클러스터링)

young.h

다음 포스트