시간복잡도

[알고리즘] mergeSort 병합(합병)정렬 (pseudo-code, 파이썬, Java)

병합정렬(mergeSort) 주어진 크기가 n인 리스트 A를 크기가 n/2인 두 부분으로 나눈다. 크기가 n/2인 두 부분을 재귀적으로(recursively) 정렬한다. 정렬된 두 부분을 하나로 병합한다 Merge(병합) 알고리즘 : 나뉜 두부분의 첫부분을 비교하여 작은 원소를 새로운 배열에 넣어주고, 작은 원소가 있던 부분배열의 인덱스를 늘려준다. 이렇게 부분배열이 다 넣어질 때까지 반복한다. 다른 한쪽부분은 남은 부분이 있을 수 있으므로 남은 부분배열의 전체를 배열에 넣어준다. Pseudo-code mergeSort 함수 : 정렬되지 않은 리스트(배열)을 재귀적으로 분할하는 역할을 한다 Algorithm mergeSort(arr, left, right) if (left < right) mid = (f..

[알고리즘]분할과 정복 개념 및 예시

분할과 정복 큰 입력의 문제를 작은 입력의 문제들로 나눈다. 나눈 작은 문제들의 해를 재귀적으로 구현한다. 재귀적으로 나눈 문제들의 해를 이용하여 원래 문제의 해를 구한다. 리스트(배열)에서 최대값 찾기 분할과 정복 Algorithm maximum(a, first, last) if(first == last) then return a[first] else mid = (first + last) // 2 lmax = maximum(a, first, mid) rmax = maximum(a, mid + 1, last) if lmax > rmax then return lmax else return rmax mid 를 기준으로 나눈 왼쪽 반의 최대값 lmax 와 오른쪽 반의 최대값 rmax 를 비교하여 더 큰값이 전..