Graph Search Sort Hash

그래프와 탐색 문제는 목적어를 보고 도구 선택

정점과 간선, DFS와 BFS, 정렬 알고리즘, 해싱은 모두 데이터를 다루는 방법입니다. 연결 관계인지, 방문 순서인지, 정렬인지, 빠른 검색인지 먼저 나눕니다.

graph

관계 표현

친구 관계, 경로, 네트워크처럼 대상 사이 연결이 핵심이면 정점과 간선으로 봅니다.

DFS/BFS

방문 순서

DFS는 스택과 재귀로 깊게 가고, BFS는 큐로 가까운 정점부터 넓게 탐색합니다.

sort

순서 재배열

삽입, 선택, 버블, 퀵, 합병, 힙 정렬은 비교 기준과 시간 복잡도를 함께 묻습니다.

hash

키 기반 검색

해싱은 키를 주소처럼 바꿔 빠르게 찾습니다. 충돌 처리는 체이닝과 개방 주소법을 구분합니다.

최소 비용 연결

모든 정점을 잇되 비용을 줄이면 최소 비용 신장 트리입니다.

MST
정렬된 배열

중간값 비교로 범위를 반씩 줄이면 이진 탐색입니다.

binary search
충돌 발생

같은 주소가 나오면 연결 리스트나 다음 빈 칸 탐색으로 해결합니다.

collision