200818_TIL

부스트 코딩뉴비챌린지

• 어제오늘 갑작스러운 컨디션 난조(+생활패턴 박살)로 공부를 많이 못하고 집에서 쉬었다ㅠ 오늘은 잠깐 자고 일어나서 약 먹었더니 어제보단 괜찮은 것 같아서 다 듣지 못한 강의를 마저 들으며 내용을 정리해 보았다.
• 6주차 강의를 다 들었다. 지금까지 열심히 달려오긴 했지만, 막상 들을 강의가 더 없는 걸 보니 6주가 짧은 시간이었던 것처럼 느껴진다.
• 수료증 발급받으니 더 시원섭섭하다ㅠ 미션 해결하고 이번 주차, 다음 주차 라이브 강의 들으면서 찐 마무리 해야지..!
  
  
  

해시 테이블 (Hash Table)

: 연결 리스트의 배열

• 해시 테이블의 값들은 해시 함수라는 맞춤 함수를 통해 어떠한 규칙에 따라 연결 리스트에 저장된다. 이 연결 리스트들이 배열처럼 연결되어 있는 것이 바로 해시 테이블!
• 여러 값들을 몇 개의 바구니에 넣는 경우를 생각해 볼 때, 값들은 해시 함수에 의해 어떤 바구니에 담길지 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 시작되는(?) 연결 리스트에 저장된다.
  즉 바구니는 연결 리스트의 첫 번째 요소를 가리키는 포인터가 되는 것이다.
• 해시 테이블은 해시 함수가 이상적일 경우(각 바구니에 하나의 값만 담기는 경우) O(1)이지만 최악의 경우(한 바구니에 n개의 값이 모두 담기는 경우) O(n)이 될 수도 있다.
• 하지만 배열만 혹은 연결 리스트만 사용할 경우보다는 확실히 빠르며, 이상적인 해시 함수를 설계하면 O(1)에 가까워지므로 효율적이다.
  
  
  

트라이 (Trie)

: 각각의 노드가 배열로 이루어진 트리

• 빠른 실행 시간을 위해 많은 메모리를 사용한다.
• 만약 A-Z까지의 알파벳으로 이루어진 문자열을 저장하는 트라이라면, 루트 노드는 A-Z의 알파벳 값을 가지는 배열이 된다. 자식 노드는 A-Z를 가진 다음 층의 배열이 된다.
  이와 같은 트라이에서 문자열을 검색하거나 삽입할 때 걸리는 시간은 단순히 문자열의 길이(상수)에 의해서만 결정되므로 O(k), 즉 O(1)이다.
  
  
  

큐 (Queue)

: 선입 선출(FIFO)의 특징을 가진 자료 구조

• enqueue: 큐에 자료를 넣는 것, dequeue: 큐에서 자료를 빼내는 것
  
  
  

스택 (Stack)

: 후입 선출(LIFO)의 특징을 가진 자료 구조

• push: 스택에 자료를 넣는 것, pop: 스택에서 자료를 빼내는 것
  
  
  

딕셔너리 (Dictionary)

: 값 혹은 자료의 쌍으로 이루어진 자료구조로, 해시테이블과 비슷한 면이 있다.

• '키'와 '값'이라는 두 요소로 이루어져 있으며 '키'에 해당하는 값을 저장하고 읽어 오므로, 키를 어떻게 정의할지가 중요하다.