목록2018/11/23 (1)

모종닷컴

7장 분할 정복

분할 정복 알고리즘이란 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 재귀 호출과 차이점은 이 부분 문제를 나누는 방법에 있어 재귀 호출은 작은 부분하나씩 분리해서 해결하지만, 분할 정복은 항상 비슷한 크기의 부분으로 나눈다는 것 분할 정복을 사용하는 알고리즘들의 세 가지 구성 요소문제를 더 작은 문제로 분할하는 과정각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 분할 정복을 이용한 문제1) 1~n까지의 합을 구하여라재귀 함수를 이용하여 1~n 까지의 합을 구했을 때는 O(n) 시간 복잡도였지만분할 정복을 이용한다면 O(log n) 까지 줄일 수 있다. 2)행렬의 거듭..
카테고리 없음 2018. 11. 23. 17:53
이전 Prev 1 Next 다음