알고리즘 / 자료구조

DP란 문제에 접근하기 위한 방식으로 '문제의 일부분을 풀고 그 결과를 재활용하는 방법'이다. 주어진 최적화 문제를 보다 작은 문제로 나누어 부분 문제를 풀고, 해당 결과를 재활용하여 전체 문제의 해답에 이르는 방식이다.

그래프는 정점(node/vertex)과 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조로, 연결되어 있는 객체 간의 관계를 표현할 수 있는 구조이다. 예로 지도, 지하철 노선도 상의 최단 경로를 구하는 데에 그래프 구조가 사용될 수 있다.

그래프를 구현하는 방식에는 크게 두 가지가 있는데, 인접 리스트와 인접 행렬이다. 인접 리스트는 그래프의 전체 노드 목록을 저장한다. Python에서는 하나의 노드가 키(key)가 되고, 그 노드에 인접한 노드가 값(value)이 되는 딕셔너리로 구현할 수 있다.