자료구조

Array vs Linked List

• Array

  • 배열, 논리적 저장순서와 물리적 저장순서가 일치한다
  • 특정 자료형들이 메모리 공간 상에서 연속적으로 저장된다
  • 인덱스로 해당 원소에 접근 가능하다 → 시간복잡도 O(1)
  • 삭제, 삽입 과정에서는 작업을 완료한 후 다른 원소들을 옮겨주는 작업이 추가로 필요하다. → 시간복잡도 O(N)
  • 메모리 공간 활용에 제약이 있다
  • 메모리에 선언되자마자 compile time에 할당 → 정적 메모리 할당

• Linked List

  • 메모리 공간 상에서 각 노드들이 연속적으로 저장되지 않고, 각각의 노드가 자신의 다음 노드를 알고 있는 형태
  • 데이터 검색시 처음부터 순회해야한다 → 시간복잡도 O(N)
  • 논리적 저장순서와 물리적 저장순서가 다르기 때문
  • 원소를 삽입, 삭제시 원소의 직전, 직후 노드의 참조값만 변경하면 된다. → 시간복잡도 O(1)
  • 새로운 node가 추가될 때 runtime에 할당 → 동적 메모리 할당

• 결론

  • 삽입과 삭제가 빈번하게 일어나면 linked list를 이용
  • 데이터 접근이 빈번하다면 array

Stack vs Queue

• Stack

  • LIFO(Last In First Out)
  • 시간복잡도, 공간복잡도 모두 O(N)

• Queue

  • FIFO(First In First Out)
  • 시간복잡도, 공간 복잡도 모두 O(N)

• 두개의 스택으로 큐 구현(파이썬)

stack1 = []
stack2 = []
next_pop = 1 # 다음번에 pop할 stack
next_push = 1 # 다음번에 push할 stack
def push(num):
    global next_push
    if next_push == 1:
        stack1.append(num)
        next_push = 2
    else:
        stack2.append(num)
        next_push = 1

def pop():
    global next_pop
    if next_pop == 1:
        s1 = stack1
        s2 = stack2
    else:
        s1 = stack2
        s2 = stack1

    if len(s1) == 0:
        return -1

    size = len(s1) - 1
    while len(s1) > 1:
        s2.append(s1.pop())
    res = s1.pop()
    while len(s1) < size:
        s1.append(s2.pop())
    if next_pop == 1:
        next_pop = 2
    else:
        next_pop = 1
    return res


turn = 1

while True:
    command = input().split()
    if command[0] == 'push':
        num = int(command[1])
        push(num)
    elif command[0] == 'pop':
        print(pop())

Tree

• 실제 나무를 거꾸로 세운 듯한 모양이라서 트리라고 부른다
• Stack이나 Queue와 다르게 비선형 구조이다.
• 계층적 관계를 표현한다.
• 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드만을 갖는다.
• 삽입, 삭제 시간복잡도 O(log N)

• node : 트리를 구성하는 각 요소
• edge : 노드와 노드를 연결하는 선
• root node : 트리 구조에서 최상위에 있는 노드
• terminal node : 하위에 다른 노드가 연결되지 않은 노드
• internal node : terminal node 제외한 다른 노드들

이진트리

• 루트 노드를 중심으로 두개의 서브 트리, 나눠진 두 서브 트리도 모두 이진 트리여야 한다.

• 포화(full) 이진 트리 : 모든 level이 꽉 찬 트리

• 완전(complete) 이진 트리 : 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리

• 순회 : 항상 부모 노드를 기준으로 생각한다.

  • 전위순회 : 부모 노드 → 좌측 자식 → 우측 자식
  • 중위순회 : 좌측 자식 → 부모 노드 → 우측 자식
  • 후위순회 : 좌측 자식 → 우측 자식 → 부모 노드

Heap

• 우선순위 큐를 위해 만들어졌다.

• 우선순위 큐

  • 우선순위 개념을 큐에 도입, 우선순위가 높은 데이터들이 큐에서 먼저 빠져나가도록
  • 배열, 연결리스트, 힙으로 구현 가능하다

• 삽입 O(log N), 삭제 O(log N)

• 배열 기반 완전 이진 트리

• 최댓값, 최솟값을 찾아내는 데에 유용하다

• index 1부터 사용한다. i번째 노드에 대해 왼쪽 자식은 i*2, 오른쪽 자식은 i*2 + 1

• 최대힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리, 최소힙은 반대

• 최대힙에서 최댓값을 찾는 시간복잡도는 O(1)

• 중복된 값을 허용한다

• 최대 힙 삽입 구현

  • 일단 새로운 노드를 힙의 마지막 노드에 삽입하고, 새로운 노드를 검사하여 부모 노드와 교환한다.

heapSize를 1증가, 마지막 노드에 x삽입

for i = heapSize to i = 2 do
  if i번째 노드가 부모 노드(index i//2인 노드)보다 크다
  then 두 값을 교환한다.
  else for문을 중단한다
  endif
endfor

• 최대 힙 삭제
  • 루트 노드를 삭제한 후 힙의 마지막 노드를 루트 노드에 삽입
  • 힙을 재구성한다

heap이 비어있으면 -1을 return

root = heap[1] # 루트 노드 값을 저장
heap[1] 에 마지막 노드를 삽입하고, heapSize 1감소

i = 1
while i번째 노드의 자식 노드가 존재
  if i번째 노드 값이 자식 노드들 값보다 큼
  then while문 중단
  if 왼쪽 child 노드가 i번째 노드보다 큼
  then 왼쪽 child 노드와 i번째 노드 swap하고 i = 왼쪽 child 노드의 인덱스로 변경
  else 오른쪽 child 노드와 i번째 노드 swap하고 i = 오른쪽 child 노드의 인덱스로 변경
endwhile

원래 루트 노드 값이었던 root을 return

• heapify : 두개의 서브 트리가 최대힙(또는 최소힙)일때, root을 포함하는 전체가 heap이 되도록 위치를 조정하는 과정

이진 탐색 트리

• 이진 탐색 + 연결 리스트

  • 이진 탐색은 탐색에 소요되는 시간 복잡도가 O(logN)이지만 삽입이나 삭제가 불가하다.
  • 연결리스트의 삽입, 삭제의 시간 복잡도는 O(1)이지만 탐색의 시간 복잡도는 O(N)

• 이진 트리의 일종, 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값들만, 오른쪽 서브트리에는 해당 노드보다 큰 값의 노드들로만 이루어진다.

• 중위 순회 방식 이용

• 탐색 시간 복잡도는 평균적으로 O(logN)이지만 최악의 경우 편향 트리가 되어 O(N)

• 중복이 없어야 되는 이유? 검색을 목적으로 하기 때문, 노드가 많을 수록 검색 속도가 저하된다. 노드에 count 변수를 추가하는 것이 효율적

• 구현하기(파이썬)

  • reference: gingerkang tistory

class Node:
  def __init__(self, value):
    self.value = value
    self.left = None
    self.right = None

class BST:
  def __init__(self, root):
    self.root = root
  
  # 노드 삽입
  def insert(self, value):
    self.current_node = self.root
    while True:
      if value < self.current_node.value:
        if self.current_node.left == None:
          self.current_node.left = Node(value)
          break
        else:
          self.current_node = self.current_node.left
      else:
        if self.current_node.right == None:
          self.current_node.right = Node(value)
          break
        else:
          self.current_node = self.current_node.right
  
  # 노드 탐색
  def search(self, value):
    self.current_node = self.root
    while self.current_node:
      if self.current_node == value:
        return True
      elif self.current_node < value:
        self.current_node = self.current_node.right
      else:
        self.current_node = self.current_node.left
    return False

• 노드 삭제는 귀찮아서 설명으로 대체

  • 삭제하려는 노드를 현재 노드라고 지칭할 때,
  • 현재 노드에게 자식 노드가 없을 경우 그냥 삭제(None으로 변경)
  • 자식 노드를 하나만 가질 경우, 자신의 자리를 자식 노드로 대체
  • 자식 노드를 두개 가지고 있을 경우, (pseudo code)

# target_node(삭제하려는 노드가) 자식 노드를 두개 가질 경우 target_node를 제거하는 코드

target_node = 삭제하려는 노드
change_node = 삭제하려는 노드의 right child
change_node_parent = target_node

# right child 중 가장 왼쪽의 노드를 찾아주기
while change_node의 왼쪽 child가 존재
  change_node를 왼쪽 child로 바꾸고
  change_node_parent를 change_node로 바꿔준다

if change_node에 오른쪽 child가 존재
then change_node_parent에 오른쪽 child를 넣어주기
else change_node_parent의 왼쪽 child를 제거

target_node의 자리에 change_node를 넣어주기

Hash

• hashing : 데이터를 저장할 위치(index)를 연산(해시 함수)을 통해 구하는 것
• 이러한 hash 값을 index로 하여 값을 저장하면, hash (or hash table)가 된다.
• 해시 테이블의 각 요소를 버킷bucket이라고 한다.
• 굉장히 빠른 검색 속도를 갖는다
• 서로 다른 데이터가 같은 해시 값을 가져 같은 인덱스를 참조하게 되는 경우를 충돌(collision)이라고 한다.
• 충돌에 대한 대처 방법으로는 두가지가 있다
  • 체인법(chaining or open hashing): 같은 해시 값을 갖는 요소를 linked list(or tree)로 관리하기
  • 오픈 주소법: 빈 버킷을 새롭게 찾는 것 (고정 크기만큼 다음 주소로 이동하거나, 제곱수만큼 이동하거나, 새로운 해시 함수를 적용하거나, 해시 테이블 크기를 늘려서 모든 데이터들을 다시 해싱하거나...) 데이터 삭제시, 연결된 버킷이 존재하는 지의 유무를 알려줘야 한다.
• 탐색, 삽입, 삭제 모두 평균적으로 O(1)의 시간복잡도를 가지고, 최악은 O(N)이다.
• java에는 hashTable과 hashMap 두가지가 존재한다. HashMap은 동기화를 지원하지 않고, key와 value로 null이 허용되는 반면, HashTable은 HashMap보다 속도가 느린대신 동기화를 지원하면 null을 허용하지 않는다.

Trie(트라이)

• 정렬된 트리 구조
• 텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는데 유용하다
• 루트노드는 아무런 의미가 없음
• 루트노드를 제외한 child 노드들은 해당노드와 공통 접두어를 가진다는 특징이 있다.

Graph

• 정점과 간선의 집합
• 트리 또한 그래프이며, 그 중 사이클이 허용되지 않는 그래프를 말한다
• 방향성이 있는 그래프를 Undirected, 방향성이 있는 그래프를 Directed 그래프라고 한다.
• 그래프는 인접 행렬 또는 인접 리스트를 통해 구현 가능하다

Degree

Undirected Graph에서 각 정점에 연결된 edge의 개수를 degree라고 한다.

최소 신장 트리

• spanning tree : 그래프 G의 모든 정점이 cycle 없이 연결된 형태

• 그래프 G의 spanning tree 중 edge의 가중치 합이 최소인 spanning tree를 지칭한다

• 크루스칼 알고리즘 : weight가 가장 작은 edge부터 차례대로 추가하는 것. spanning tree 조건을 만족시키기 위하여 cycle이 생기지 않는 경우에만 edge를 추가하고, 모든 정점이 연결되면 탐색을 끝낸다.

  • 모든 정점이 연결됐는지 확인하기? node - 1 의 간선개수로 최소 신장 트리를 연결할 수 있다.
  • 사이클이 발생하는 지 확인하기? Union-Find 알고리즘을 이용한다.

    Union-Find Disjoint set(서로소인 집합들로 나눠진 원소들에 대한 자료구조)를 표현할 때 사용하는 알고리즘이다. 두 집합을 합치는 union, x가 속한 집합의 대표값을 반환하는 find로 구성된다.

  • 시간복잡도 : Edge를 weight을 기준으로 sorting하는 ElogE (union-find를 최적화하면 시간복잡도가 상수)
  • cycle 생성 여부를 검사하고

• Prim 알고리즘 : 하나의 vertex로 이루어진 초기 그래프 A를 구성한다. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점을 선택하고, 모든 정점이 선택될때까지 반복한다.

  • 크루스칼이 트리의 조각들을 합쳐 스패닝 트리를 만든다면, 프림은 하나씩 정점을 추가하여 스패닝 트리를 만들어간다.
  • minWeight[] : 트리와 이 정점을 연결하는 간선의 최소 가중치. 트리에 정점을 추가할때마다 인접한 간선을 순회하면서 갱신한다.
  • pseudo code

# 해당 정점이 트리에 포함되어있는지를 저장할 배열
added를 정점개수 * [False]로 정의
# 트리에 인접한 간선 중 해당 점점에 닿는 최소 간선의 정보
minWeight = 정점개수 * INF

minWeight[0] = 0
for (i = 0) to 정점개수-1 do
  트리에 포함되지 않은 정점들 중 minWeight가 가장 작은 정점(u)을 찾는다.

  새로운 정점 u를 트리에 추가한다
  u와 연결된 간선들에 대하여 minWeight를 갱신한다.

• 시간복잡도는 O(E logV)
• minWeight를 binary heap으로 구현하면 (정점의 개수만큼-V) (minWeight인 정점 u찾기-logV) + (간선 개수-E)(key값 변경-logV)