#graph
노트 13개
Backend › Database
웹 검색엔진의 동작: 크롤링, 색인, 랭킹, 질의 처리웹 검색엔진은 크롤러가 링크 그래프를 따라 페이지를 모으고, 중복을 묶어 샤딩된 역인덱스에 넣은 뒤, 질의가 오면 의도를 해석해 후보를 뽑고 여러 랭킹 신호로 순서를 정한다. 크롤러의 URL 프런티어, PageRank, 2단계 랭킹, 구글의 랭킹 시스템과 네이버 통합검색의 컬렉션 구조를 자료구조·알고리즘 관점에서 정리했다.
Algorithm › Data Structure
서로소 집합 (Union-Find)원소들이 어떤 집합에 속하는지 관리하며, 두 집합을 합치고 대표를 찾는 연산을 빠르게 처리하는 자료구조.
Algorithm
그래프정점과 간선으로 관계를 표현하는 그래프의 기본 개념과 최단 경로 알고리즘.
Algorithm › Graph
그래프의 기본과 표현 방법정점과 간선으로 이루어진 그래프의 종류, 사이클 없는 그래프와 트리의 차이, 인접 행렬·인접 리스트로 저장하는 방법과 밀집·중복 간선의 처리, 탐색 기법과 놓치기 쉬운 경우.
Algorithm › Graph
다익스트라 최단 경로음이 아닌 가중치 그래프에서 한 정점으로부터 모든 정점까지의 최단 거리를 우선순위 큐로 구하는 알고리즘.
Algorithm › Graph
단절점과 단절선지우면 그래프가 끊어지는 정점(단절점)과 간선(단절선)을 DFS 방문 순서와 low 값으로 O(V + E)에 찾는 방법.
Algorithm › Graph
오일러 경로와 오일러 회로모든 간선을 정확히 한 번씩 지나는 경로·회로의 존재 조건(차수의 짝홀)과, 히어홀저 알고리즘으로 O(V + E)에 회로를 구하는 방법. 다중 간선에서 이미 쓴 간선을 다시 훑지 않는 요령을 함께 정리한다.
Algorithm › Graph
위상 정렬방향 비순환 그래프(DAG)의 정점을 모든 간선 u→v에서 u가 앞에 오도록 나열하는 위상 정렬. 진입 차수와 큐를 쓰는 칸 알고리즘, DFS 후위 순서를 뒤집는 방법, 사이클 판별, 사전순 최소 순서를 정리한다.
Algorithm › Graph
최단 경로 알고리즘 고르기가중치 유무, 음수 간선·음수 사이클, 출발점 하나인지 모든 쌍인지, 목적지가 하나인지에 따라 BFS·0-1 BFS·다익스트라·벨만-포드·플로이드-워셜·DAG 최단 경로·A*를 고르는 기준과 각 알고리즘의 원리, 트리와 밀집 그래프에서의 선택.
Algorithm › Graph
최소 공통 조상 (LCA)트리에서 두 노드의 가장 가까운 공통 조상을 찾는 LCA. 깊이를 맞춰 함께 올라가는 O(N) 방법과, 2^k번째 조상 표(희소 테이블)로 질의마다 O(log N)에 답하는 이진 올리기(binary lifting), 두 노드 사이 거리 구하기까지.
Algorithm › Graph
최소 신장 트리: 크루스칼과 프림가중치 그래프의 모든 정점을 사이클 없이 가장 싸게 잇는 최소 신장 트리와, 간선을 고르는 크루스칼·정점을 넓혀 가는 프림 알고리즘의 동작·복잡도·선택 기준, 결과가 늘 트리인 이유와 비연결 그래프의 최소 신장 숲.
Algorithm › Search
깊이 우선 탐색 (DFS)한 갈래를 갈 수 있는 데까지 파고든 뒤 되돌아오는 그래프 탐색으로, 스택이나 재귀로 구현한다.
Algorithm › Search
너비 우선 탐색 (BFS)시작점에서 가까운 노드부터 큐를 이용해 차례로 방문하는 그래프 탐색으로, 가중치 없는 그래프의 최단 거리를 구한다.