그래프 이론의 핵심 지금까지 배운 내용 시간 제한 참고 파이썬 => 1초 20000000번 연산 데이터 20,000,000 => O(N) 데이터 1,000,000 => O(NlogN) 데이터 4~5,000 => O(N^2) 데이터 100~200 => O(N^3) 그래프의 구현 방법 노드의 개수가 V, 간선의 개수가 E라고 하면 인접 행렬 : 2차원 배열을 사용하는 방식 인접 행렬의 경우 O(v^2) 만큼의 메모리 공간 필요 (메모리 측면) 인접 행렬의 경우는 특정 노드의 간선의 비용을 알기 위해선 O(1)의 비용이 듦 (속도 측면) 인접 리스트 : 리스트를 사용하는 방식 인접 리스트의 경우 O(E) 만큼의 메모리 공간 필요 (메모리 측면) 인접 리스트의 경우는 특정 노드의 간선의 비용을 알기 위해선 O(..