기준 값(pivot)을 설정한 다음 큰 수와 작은 수를 교환한 뒤pivot 보다 작은 데이터 그룹과 큰 데이터으로 나누는 방식을반복 수행하여 데이터를 정렬하는 알고리즘이다.평균 시간 복잡도 : O(nlogn)최악 시간 복잡도 : O(N^2)
정렬된 데이터에서 시작점, 끝점, 중간점을 정하여 찾으려는 데이터와 중간점 위치에 있는 데이터를반복적으로 비교하여 원하는 데이터를 찾는 알고리즘O(logN)
큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 하다.다음의 조건에서 큰 문제를 여러 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법
여러 개의 노드가 있는 그래프에서 음의 간선이 없을 때 ,방문하지 않는 노드 중 가장 최단 거리가 짧은 노드를 선택하는 과정을반복하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘O(E logV) ( E : 간선의 개수 ,V : 노드의 개수 )모든 지점에서
공통 원소가 없는 두 집합을 의미한다.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산find 연산 : 특정한 원소가 속해있는 집합이 어떤 집합인지 알려주는 연산
하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프인 신장 트리에서, 크루스칼 알고리즘은 트리의 최소 비용을 구하는 최소 신장 트리 알고리즘 중 하나간선의 개수가 E개 일 때, O(E logE)
방향 그래프의 모든 노드를 ' 방향성에 거스르지 않도록 순서대로 나열 ' 하는 정렬노드의 개수 : V , 간선의 개수 : E 일때 , O( V+E )
부분합, 누적합이라고 불리우는 배열의 일부 구간에 대한 합을 빠르게 구해주는 알고리즘반복문을 통한 부분 배열의 합 : O(N)누적합 알고리즘을 통한 부분 배열의 합 : O(1)크기가 X인 arr 일 때, 크기 X+1 인 sum배열 생성sumi = arr0+arr1+ .