devide

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

분할과 정복 큰 입력의 문제를 작은 입력의 문제들로 나눈다. 나눈 작은 문제들의 해를 재귀적으로 구현한다. 재귀적으로 나눈 문제들의 해를 이용하여 원래 문제의 해를 구한다. 리스트(배열)에서 최대값 찾기 분할과 정복 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 를 비교하여 더 큰값이 전..