DS - Data Structure

기술면접을 위해 기초 CS에 대한 복습중이다.
공부한 내용 중 요점이나 나중에 기억해야할 부분을 정리해보려고 한다.
내가 아는 부분은 생략되어 있을 수 있고, 혹여나 틀린 부분이 있을 수도 있으니 이 글을 보고 '다른 사람'이 공부하기에는 도움이 되지 않을 수 있으니 주의!

Stack & Queue

• Stack 2개로 Queue 구현하는 방법
  • enqueue용 stack, dequeue용 stack을 만들어서 구현한다.
  • enqueue: 1st stack에 push
  • dequeue: 1st stack에서 pop 후 2nd stack에 push, 이걸 반복한다. 주의할 점은 2nd stack이 완전히 비었을 때에만 1st stack의 첫 번째 값이 들어올 수 있다.
• Stack의 활용
  • 시스템 스택 (프로그램 간의 호출과 복귀 시 복귀 주소, 매개 변수 등)
  • 수식의 괄호검사
• Queue(Heap)의 활용
  • OS의 프로세스 스케줄링

Hash Table

• 시간 복잡도
  • average case일 때, search, insertion, delete 모두 $O(1)$
  • worst case일 때, search, insertion, delete 모두 $O(n)$
    collision이 생기면 전부 다 돌면서 찾아봐야 하기 때문
• Collision 해결 방법
  • 개방 주소 방식: 비어있는 메모리에 넣는 방법
  • 분리 연결 방식: Chaining. 버킷을 list로 넣는 방법.

Hash map과 Set의 차이

• set: 집합 같은 것. key만 보관. 순서대로 보관해서 시간 복잡도는 $O(logN)$
• map: key, value 둘 다 보관
• Hash map: C++에서 unordered_map. 순서 상관 없이 hash function 사용하여 보관
• 언제 어떤 걸 사용하는 게 좋을까?
  • 데이터 존재 유무만 궁금할 때: set
    • 중복 데이터 허용한다면: multiset
  • 데이터에 대응되는 데이터를 저장하고 싶을 경우: map
    • 중복 데이터 허용한다면: multimap
  • 속도가 중요할 때: unordered_set, unordered_map
    • 단, collision 가능성이 있을 땐 크기에 주의!

---

참고한 사이트

• 모두의 코드 씹어먹는 C++