자료구조

파이썬에서 각 자료구조에 대한 설명

List

동일 타입, 동일 사이즈의 경우 array를 사용하여 더 효율적으로 사용가능

lst = [1, 2, 3]

연산

• 인덱싱 : O(1)
• 할당 : O(1)
• 삽입
  • append로 끝에 삽입시 : O(1)
  • insert로 처음, 중간 삽입시 : O(n)
• 삭제
  • pop으로 끝제거시 : O(1)
  • remove, pop으로 처음, 중간 삭제시 : O(n)
• 사이즈
  • len 사용시 : O(1)
    • 동적 배열사용으로 리스트 객체에 미리 리스트 사이즈가 저장되어 있어야함
• search : O(n)
• sort : O(nlogn)

LinkedList

리스트를 node를 이용해서 구현하는 방법, 노드들은 다른 노드와 서로 연결(link)된 형태로 구현된다. 보통 Node, LinkedList 클래스를 구현해서 사용하며 head, tail 포인터를 이용하여 리스트의 양끝에서 삽입 삭제가 상수시간안에 일어나게 할 수 있다. 단방향과 양방향이 있으며 단방향은 헤드부터 시작으로 다음 노드만 가리키는 구조다. 마지막 노드는 null을 가리킨다. 양방향은 노드가 각 이전노드, 다음노드를 가리키며 첫번째 노드는 이전노드가 null이며 마지막 노드는 다음노드가 null이다.

주소를 추가로 저장해야하기 때문에 기본적으로 list보단 메모리를 많이 사용하며 특정 순서에 있는 요소를 참조하려면 O(n)이 걸린다.

연산

• 삽입(양끝에)
  • O(1)
• 삭제(양끝에)
  • O(1)
• 서치
  • O(n)

Stack

Last in, first Out 후입선출의 자료구조로 python list의 append, pop의 리스트 끝에서 동작하는 시간복잡도가 상수시간이기에 list로 구현해서 사용한다.

연산

• 삽입(push)
  • stack.append(value)
  • O(1)
• 삭제(pop)
  • stack.pop()
  • O(1)
• 첫번째 요소 확인(top, peek)
  • stack[-1]
  • O(1)
• 스택이 비었는지 확인(is_empty)
  • if stack
  • O(1)

Queue

First in, first out 선입선출의 자료구조로 python list를 이용해서 구현시 삽입은 리스트 끝에 하기에 상수시간이지만 삭제는 queue.pop(0)로 진행해야 하기때문에 O(n)다. 그래서 파이썬에서는 collections의 deque(double-ended queue)로 구현한다

연산(deque)

• 삽입(enqueue)
  • q.append(value)
  • O(1)
• 삭제(dequeue)
  • q.popleft()
  • O(1)

from queue import Queue의 Queue로도 구현 가능하다. 그런데 Queue는 멀티쓰레딩 환경에서 동기화를 지원하기때문에 Thread-safe하고 그 때문에 성능 자체는 deque로 구현한 것보다 상대적으로 떨어지는 편이다.

연산(Queue)

• 삽입(enqueue)
  • q.put(value)
  • O(1)
• 삭제(dequeue)
  • q.get()
  • O(1)

Hash Table

파이썬에선 dict가 해시 테이블로 구현되어 있으며 삽입, 삭제, 조회가 전부 O(1)의 상수시간이다.해시 충돌에 따라 최악의 경우 O(n)이 소요되며 해시 충돌을 해결하는 방법은 여러가지 있다. 개방 주소법(Open Addressing), 분리 연결법(Separate Chaining) 등이 존재한다.

Open Addressing

• 파이썬의 dict의 구현에서 사용된 방법으로 배열 자체에 값을 저장하게 되며 충돌이 일어날시 여러 방법으로 다음에 저장할 공간을 찾게 된다. 로드 팩터(해시 테이블의 채워진 정도)가 높아질수록 성능이 저하되므로 테이블 리사이징을 한다.
  • 선형 탐사(Linear Probing)
    • 해시 충돌이 일어날시 다음 공간에 저장한다. 계속 해시 충돌이 발생시 연속적인 메모리 영역에 데이터가 모이는 클러스터링 현상이 발생할 수 있다.
  • 이차 탐사(Quadratic Probing)
    • 해시 충돌이 일어날시 이차식(제곱)으로 다음 저장공간을 찾는다.
  • 이중 해싱(Double Hashing)
    • 해시 충돌이 일어날시 두번째 해시함수로 다음 저장공간을 찾는다. 충돌이 계속 발생할시 두번째 해시함수에 충돌횟수를 곱해서 찾는다.

Separate Chaining

• 해시 테이블의 각 배열의 요소가 연결리스트로 구현되며 해시 충돌이 발생할시 해당 위치의 연결 리스트에 추가되는 방식이다. 데이터가 계속 입력되어도 해시테이블의 사이즈는 변함없이 연결리스트의 사이즈가 늘어나는 방식으로 연결리스트가 길어지면 조회 성능이 떨어지므로 로드 팩터가 높아지면 테이블 리사이징을 해야한다.

Graph

노드(node, 혹은 정점 vertex)와 간선(edge)로 이루어진 자료구조로 네트워크 등을 표현하는데 주로 쓰인다. 그래프는 방향성, 가중치, 사이클 등의 여러 특성을 가질 수 있다. 구현 방식에 따라 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List)로 나뉘게 된다.

인접 행렬

• 행렬로 구현하며 grapth[i][j] = w 와같이 i -> j로 가는 간선의 가중치를 저장하게된다. 무방향인 경우 둘다 같은 값을 가지게 하며 자기자신의 경우 0으로 표현하고 가는 경로가 없는경우 INF와 같이 도달하지 못하는 값을 사용한다.
• 한 노드로부터 다른 모든 노드로 가는 정보를 표현하므로 간선이 별로없는 희소 그래프의 경우 비효율적이다. 밀집 그래프의 경우 좋다. 메모리를 많이 사용한다.
• 두 정점 간의 연결여부를 O(1)만에 알 수 있다.
• 플로이드-와샬에서 쓰인다.

인접 리스트

• 정점간의 연결 여부를 리스트로 표현한다.
• 메모리를 적게 사용한다. 간선이 별로 없는 희소 리스트에서 효율적이다.
• 두 정점 간의 연결 여부를 알려면 인접 정점의 수만큼 걸린다.
• 그래프의 간선 정보를 바탕으로 그래프를 순회할때 인접 행렬보다 효율적이다.
  • 인접 행렬의 경우 노드를 기준으로 인접 정점을 확인하려면 행 전체를 확인해야하므로 O(V^2)만큼 걸릴수 있다.
  • 인접 리스트의 경우 노드를 기준으로 인접 정점을 리스트를 통해 확인하므로 전체 순회를 할 경우에 O(V+E)만큼 걸린다.

Tree

• 그래프의 일종인 트리는 부모가 없는 루트노드가 존재한다. 루트를 제외한 다른 노드들은 하나의 부모 노드와 여러 자식노드를 가질 수 있다. 이로인해 트리의 간선 수는 트리의 노드 수 - 1이 되고 사이클이 존재하지 않는다. 노드들이 계층적으로 연결된 비선형 자료구조이다. 자식이 없는 노드는 단말(leaf)노드라고 한다.