반응형 Master Theorem2 08. Divide and Conquer(2) Decrease-and-Conquer 01. Decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance such a relationship is established, it can be exploited either top down or bottom up Top down > implemented recursively (ultimate implementation may well be nonrecursive) Bottom up > implemented iteratively (Sta.. 2021. 11. 21. 07. Divide and Conquer(1) 안녕하세요. 오늘은 Divide and Conquer. 한국어로는 분할정복이라고 불리는 알고리즘을 소개할까 합니다. 정말 유명한 알고리즘입니다. 다만, Search, DP, Greedy에 비해는 등장빈도가 조금 낮다고 할 수 있습니다. 분할하고 정복하기 분할 : 주어진 문제를 여러개의 부분 문제로 나눈다 정복 : 분할된 문제를 푼다. 이때 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다. 분할정복 문제 자체는 등장빈도가 조금 낮을 수 있다고 말씀드렸지만, 분할이라는 접근은 매우 유용하기 때문에 다른 자료구조나 알고리즘의 basic이 되는 경우가 많습니다. 정복을 설명하면서 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다고 말씀드렸는데요. Resursive function의 base case처럼 바로 .. 2021. 11. 18. 이전 1 다음 반응형
