(알고리즘과 자료구조) 자료 구조

(알고리즘과 자료구조) 자료 구조

Contents

1. 배열 (Array)
2. 큐 (Queue)
3. 스택 (Stack)
4. 링크드 리스트 (Linked List)
5. 해쉬 테이블 (Hash Table)
6. 트리 (Tree)
7. 힙 (Heap)

(1) 배열 (Array)

• 정의 : 데이터를 나열 & 인덱스에 대응하는 구조 ( 가장 기본적인 자료 구조 )

• 예시 : 파이썬의 list, 넘파이의 array

• 배열이 필요한 이유?
  • 같은 종류의 데이터를 효율적/순차적으로 관리

• 배열의 장점

  • ( “인덱스 번호”를 통한 ) 빠른 접근이 가능하다

• 배열의 단점

  • 미리 공간을 사전에 지정해줘야 ( ex. 6칸의 array를 만들것이야! )
  • 중간에 값을 제거할 경우, 뒤의 데이터를 앞으로 땡겨줘야함

  \(\rightarrow\) 즉, 값의 추가/제거가 용이하지 않음

Python의 배열은, C와는 다르게 미리 지정할 필요 없음 ( 배열의 살짝 변형 버전 )

country = 'KOREA'
print(country)

country = country + 'S'
print(country)

2차원 배열

data =[[1,2,3],[4,5,6]]

(2) 큐 (Queue)

• 정의 : FIFO (선입선출) 구조의 자료구조

  ( 한쪽 끝에서만 자료를 put/get 할수만 있다 )

• 용어 :

  • enqueue : 넣기
  • dequeue : 빼기

• queue가 자주 사용 되는 곳?

  • (OS) 프로세스 스케줄링 구현할 때!

• 변형 : LIFOqueue, Priorityqueue

ex) queue.Queue()

import queue

queue1 = queue.Queue() # FIFO

### enqueue
queue1.put('A')
queue1.put(33)

print(queue1.qsize()) # 2

### dequeue
queue1.get() # A
queue1.get() # 33

print(queue1.qsize()) # 0

ex) queue.PriorityQueue()

• 데이터를 enqueue할 때, “우선순위 (Priority)”도 함께 넣는다

import queue

queue3 = queue.PriorityQueue() # withPriority

### enqueue 
### 우선순위가 "작을"수록 "높은" 것이다. 
### (우선순위, 데이터)
queue3.put((1,'A')) 
queue3.put((3,33))
queue3.put((2,55))

print(queue1.qsize()) # 3

### dequeue
queue3.get() # A
queue3.get() # 33
queue3.get() # 55

print(queue3.qsize()) # 0

(3) 스택 (Stack)

• 정의 : LIFO (후입선출) 구조의 자료구조

  ( = LIFO queue )

• 용어 :

  • push : 넣기
  • pop : 빼기

ex) queue.LifoQueue()

import queue
queue2 = queue.LifoQueue() # LIFO

### enqueue
queue2.put('A')
queue2.put(33)

print(queue1.qsize()) # 2

### dequeue
queue2.get() # 33
queue2.get() # A

print(queue2.qsize()) # 0

stack = list()
stack.append(1)
stack.append(2)

stack.pop() # 2
stack.pop() # 1

(4) 링크드 리스트 (Linked List)

• 배열 vs 링크드 리스트
  • 배열 : 순차적으로 연결된 공간에, 데이터를 나열
  • 링크드 리스트 : 떨어진 곳에 존재하는 데이터를, 화살표를 통해 연결

• 용어 :

  • node : 데이터 저장 단위
  • pointer : 이전/이후 노드의 연결 정보

  배열은 하나의 데이터만을 기록하면 되지만, 링크드 리스트는 위 2가지를 하나의 데이터로써 관리를 한다.

• 링크드 리스트의 장점
  • 데이터 공간 미리 할당 필요 X
• 링크드 리스트의 단점
  • 데이터 당 2개의 정보를 저장해야 ( 노드 & 포인터 )
  • 중간 데이터 삭제 시 / 삽입 시, 데이터 연결을 재구성하는 추가적인 작업이 필요

class Node:
  def __init__(self, x, next_ = None):
    self.x = x
    self.next = next_

node1 = Node(1)
node2 = Node(2)
node1.next_ = node2
head = node1

def add(x):
  node = head
  while node.next_:
    node = node.next_
  node.next_ = Node(x)

더블 링크트 리스트

데이터의 크기가 매우 크고, 우리가 찾고자 하는 데이터가 매우 뒤에 있다면…?

\(\rightarrow\) 뒤에서 부터 찾으면 어떨까?

\(\rightarrow\) 기존의 포인터는 “뒤” 데이터의 주소를 연결하지만, 더블 링크드 리스트는 “앞” 데이터 주소를 향하는 반대 방향의 포인터도 가지고 있다.

(5) 해쉬 테이블 (Hash Table)

• 정의 : key-value를 저장하는 데이터 구조
• 예시 : 파이썬 dictionary
• 용어
  • hash : 임의 값을 고정 길이로 변환하는 것
  • hash table : key-value 접근이 가능한 데이터 구조
  • hashing function : key값이 주어졌을 때, value를 찾을 수 있는 매핑함수
• 해쉬 테이블의 장점
  • 읽기/쓰기 속도가 매우 빠름
  • key에 대한 value 확인이 쉬움
• 해쉬 테이블의 단점
  • 더 많은 저장공간이 필요함
  • 여러 key에 해당하는 주소가 동일할 경우, 충돌 해결을 위한 별도의 자료구조 필요
• 활용
  • 검색이 잦은 경우
  • 읽기/쓰기/삭제 등이 잦은 경우
  • 캐쉬 구현 시 ( 중복 확인 용이하므로 )

(6) 트리 ( Tree )

• 용어 : Node , Root Node, Level, Parent Node, Child Node, Leaf Node , Sibling, Depth 등
• 활용 : (이진) 트리 구조로, 탐색/검색 알고리즘 구현에 많이 사용
• Binary Search Tree
  • 특정 노드보다 “작으면 왼쪽”, “크면 오른쪽”

시간 복잡도 (탐색 시)

• depth = \(h\)
• 시간 복잡도 : \(O(h)\)

(7) 힙 ( Heap )

• 정의 : 데이터에처 max / min을 빠르게 찾기 위해 고안된 완전 이진 트리 ( Complete Binary Tree )
  • 완전 이진 트리 : node 삽입 시, “최하단+왼쪽”부터 삽입
• 힙 사용 이유
  • 배열에서 찾으려면, \(O(N)\)이 필요함
  • 힙을 사용하면, \(O(\log N)\)이 필요함
• [Max Heap] 2가지 조건
  • 각 node은, 자식 node값 “이상”이다
  • 완전 이진 트리 ( Complete Binary Tree )
• [Min Heap] 2가지 조건
  • 각 node은, 자식 node값 “이하”이다
  • 완전 이진 트리 ( Complete Binary Tree )