알고리즘

얼마나 빠르게 실행되는가시간 복잡도 관련얼마나 많은 자원이 필요한가공간 복잡도 관련

단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 자료 구조 방향성 있는 비순환 그래프의 한 종류깊이 우선 탐색다음 분기를 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법정점의 수 : N, 간선의 수 : E인접 리스트로 표현된 그래프 : O(N+E)인접 행렬

최단거리 알고리즘간선에 가중치가 있는 경우 사용지속적으로 거리를 갱신정점의 수 : V, 간선의 수 : E인접 리스트 + 힙 사용시 : O(ElogV)그래프 내 모든 정점을 포함하는 트리최소 연결이어야 한다.(최소 간선)n개의 정점을 가진 경우 n-1개의 간선을 가지게

pivot을 이용한 divide and conquer평균 시간 복잡도 O(NlogN)탐색의 깊이 : N = 2^k → k번 순환 호출 한다 → k = logN각 단계에서 비교 : N최악 시간 복잡도 O(N^2)탐색의 깊이 : N각 단계에서 비교 : N이미 정렬된 대상을