기술 블로그

분할정복법mergesort, quicksort, heap sort  mergesort는 분할정복법이라는 것인데 통째로 정복하는 것보다 각각을 정복하는 알고리즘 설계 전략 중 하나입니다. -분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할-정복 : 각각의 작은 문제를 순환적으로 해결-합병 : 작은 문제의 합을 합하여(merge) 원래 문제에 대한 해를 구함  문제를 반으로 쪼갠 다음 작은 문제를 해결하기 위해서 또 다른 알고리즘을 고안할 필요는 없습니다. 원래 문제를 해결하는 동일한 방법으로 즉 recursion으로 해결하면 됩니다. 최대값을 찾기 위해 둘로 쪼개서 왼쪽 오른쪽 각각에서 최대값을 찾으면 되는 것입니다.  합병에 해당하는 단계는 왼쪽 최대값과 오른쪽 최대값 중 더 큰 값을 찾..

Selection sort가장 큰 값을 가지고 맨 마지막에 합니다. 그 다음에 계속 확인하면서 반복을 합니다. 마지막에 간 값은 다시 확인하지 않아도 됩니다. 나머지에도 똑같은 일을 계속 반복해주면 됩니다. 다섯개 값에 마지막 값을 하나 추가했다면 네개의 값에서 가장 큰 값과 4번째 인덱스를 바꿔줍니다. 이렇게 계속 반복해줘서 해주는 것이 선택 정렬입니다.  selectionSort(A[], n){ for last A[last]; }}실행시간:for 루프는 n-1번 반복가장 큰 수를 찾기 위한 비교 횟수 n-1, n-2 ,,... , 2, 1상수 작업 시간 작업 시간복잡도 t(n) = n-1  + n-2 + ... 2 + 1 = O(n^2) bubble sort정렬할 데이터 중에서 가장 큰 값을..