#dynamic-programming
노트 3개
Algorithm › Graph
최단 경로 알고리즘 고르기가중치 유무, 음수 간선·음수 사이클, 출발점 하나인지 모든 쌍인지, 목적지가 하나인지에 따라 BFS·0-1 BFS·다익스트라·벨만-포드·플로이드-워셜·DAG 최단 경로·A*를 고르는 기준과 각 알고리즘의 원리, 트리와 밀집 그래프에서의 선택.
Algorithm › Graph
최소 공통 조상 (LCA)트리에서 두 노드의 가장 가까운 공통 조상을 찾는 LCA. 깊이를 맞춰 함께 올라가는 O(N) 방법과, 2^k번째 조상 표(희소 테이블)로 질의마다 O(log N)에 답하는 이진 올리기(binary lifting), 두 노드 사이 거리 구하기까지.
Algorithm › Math
순열과 조합순서를 따지는 순열과 따지지 않는 조합의 공식을 재귀적으로 유도하고, 파스칼 점화식과 이항 정리, 중복 순열·중복 조합, 완전 탐색의 경우의 수 추정과 파이썬 구현을 정리한다.