PQ and Heap

Hash Tables

• 해시테이블: 키(key)와 값(value)로 데이터를 저장하는 자료구조
• 해시함수를 사용해 key를 인덱스 or 해시값으로 변환한 뒤, 해당 위치에 value로 저장
  • DFS(Depth First Search, 깊이 우선 탐색): 해시테이블의 키로 그래프의 노드를, 값으로 연결된 인접 노드 리스트를 저장함
  • BFS(Breadth First Search, 너비 우선 탐색): 역시 해시테이블을 사용해 노드와 인접 노드들을 표현하고, 탐색 과정에서 큐(queue)를 이용해 너비 방향으로 탐색함

HW1: Longest Palindrome

HW2: Smallest Missing Integer

주어진 정수 목록에서 그 목록에 포함되지 않은 가장 작은 양의 정수를 반환하시오.
Note: 여기서 얼마나 많은 반복을 해야 할지에 대해 생각해 보기!

HW3: Two Sum

HW4: Intersection of Two Arrays

HW5: Longest Substring Without Repeating Characters

Graphs

• Implement DFS
  • DFS 깊이 우선 탐색: 그래프의 노드를 하나씩 깊게 들어가며 탐색하는 방식 -> 하나의 노드를 방문한 후, 그 노드에 연결된 자식 노드를 깊이 들어가며 계속 탐색
• Implement BFS
  • BFS 너비 우선 탐색:시작 노드를 방문하고 그와 연결된 노드를 먼저 방문 -> BFS는 큐 자료구조를 사용하여 탐색을 진행하며, 각 레벨을 차례대로 탐색

HW1: Implement DFS

1. 스택을 사용하여 DFS를 구현
2. 스택에서 노드를 하나씩 꺼내며 그 노드를 방문
3. 방문한 노드의 인접 노드들을 스택에 추가하여 탐색을 계속 진행
4. 모든 노드를 탐색할 때까지 반복

HW2: Implement BFS

1. 큐를 사용하여 BFS를 구현
2. 큐에서 노드를 하나씩 꺼내며 그 노드를 방문
3. 방문한 노드의 인접 노드들을 큐에 추가하여 그 노드들을 순차적으로 탐색
4. 모든 노드를 탐색할 때까지 반복