개발스토리

분할 정복 문제를 나눌 수 없을 때까지 나눈 뒤, 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘. 분할 정복 설계 전략 1. 분할(Divide) 단계 - 문제를 같은 유형의 여러 개의 더 작은 부분 문제들로 나눈다. - 부분 문제는 풀기 쉬울 때까지 계속 나눈다. 2. 정복(Conquer) 단계 - 부분 문제들을 보통 재귀적으로 해결하여 해를 구한다. 3. 합병(Merge) 단계 - 문제에 대한 해를 구하기 위해 부분 문제들의 해를 합친다. -> 문제를 제대로 나눈다면 정복 단계는 쉬워지므로 분할 단계를 제대로 해야한다. 문제 : 최댓값 최솟값 찾기 문제: 크기가 n인 배열내의 요소들 중 최댓값과 최솟값을 찾는다. 1.최댓값을 찾는다. -- 비교 횟수: n – 1 2.남은 배열 요소들의 최솟값을..