Divide&Conquer(DAC)

intro>

🍻 분할(Divide)하고 정복(Conquer)하는 이 알고리즘은 문제를 풀 때의 접근 방식으로 분할 → 정복 → 결합 크게 세 단계로 진행된다.

 

🍻

① 분할(Divide): 주어진 문제를 더 작은 여러 개의 sub-problem으로 분할한다.

② 정복(Conquer): 재귀적으로 sub-problem들을 각각 해결한다.

③ 결합(Combine): 각각의 sub-problem 해결 결과를 묶어 전체 문제의 최종 솔루션을 도출!

 

🍻 divide & conquer 접근법을 사용하는 대표 알고리즘 모음(각각의 별도 포스팅 참조)

① Quicksort

② Merge Sort

③ Closest Pair of Points

④ Strassen's Algorithm

⑤ Cooley-Tukey Fast Fourier Transform(FFT) Algorithm

⑥ Karatsuba algorithm for fast multiplication

example>

Q. input으로 주어진 array의 최솟값과 최댓값을 DAC 접근법으로 풀기

 

→ 접근법

→ 전체 최솟값 또는 최댓값을 구하는 problem을 현재 index+1부터 오른쪽 끝까지의 결과와 현재 index 원소와 최대,소 비교하는 sub-problem으로 나누었다.

 

A. python)

def DAC_Max(a, index, l):
    max = -1
    if(l - 1 == 0):
        return arr[index]
    if (index >= l - 2):
        if (a[index] > a[index + 1]):
            return a[index]
        else:
            return a[index + 1]
  
    # Logic to find the Maximum element
    # in the given array.
    max = DAC_Max(a, index + 1, l)
  
    if (a[index] > max):
        return a[index]
    else:
        return max

def DAC_Min(a, index, l):
    min = 0
    if(l - 1 == 0):
        return arr[index]
    if (index >= l - 2):
        if (a[index] < a[index + 1]):
            return a[index]
        else:
            return a[index + 1]
  
    # Logic to find the Minimum element
    # in the given array.
    min = DAC_Min(a, index + 1, l)
  
    if (a[index] < min):
        return a[index]
    else:
        return min

if __name__ == '__main__':
    # Defining the variables
    min, max = 0, -1
  
    # Initializing the array
    arr = list(map(int,input().split()))
    l = len(arr)

    # Recursion - DAC_Max function called
    max = DAC_Max(arr, 0, l)
  
    # Recursion - DAC_Max function called
    min = DAC_Min(arr, 0, l)

    print("The minimum number in a given array is : ", min)
    print("The maximum number in a given array is : ", max)

DAC vs. DP

🍻 앞선 DP 포스팅에서 두 접근법의 비교에 대해 다룬 적이 있다.

---

---

🍻 즉, DP는 여러 sub-problem이 서로 영향을 미치지만(subproblems are evaluated many times), DAC는 여러 sub-problem이 서로 영향을 주지 않는다(are evaluated only once)

Time Complexity

T(n) = aT(n/b) + f(n)

① n = size of input

② a = number of subproblems in the recursion

③ n/b = size of each subproblem. All subproblems are assumed to have the same size.

④ f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions

Advantages & Disadvantages of DAC

1) Advantages

(1) The difficult problem can be solved easily.

(2) It divides the entire problem into subproblems thus it can be solved parallelly ensuring multiprocessing

(3) Efficiently uses cache memory without occupying much space

(4) Reduces time complexity of the problem

(5) Solving difficult problems: Divide and conquer technique is a tool for solving difficult problems conceptually. e.g. Tower of Hanoi puzzle. It requires a way of breaking the problem into sub-problems, and solving all of them as an individual cases and then combining sub- problems to the original problem.

(6) Algorithm efficiency:The divide-and-conquer paradigm often helps in the discovery of efficient algorithms. It was the key, for example to the Quicksort and Mergesort algorithms, and fast Fourier transforms. In all these examples, the D and C approach led to an improvement in the asymptotic cost of the solution. In particular, if the base cases have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem’s size n, and there are a bounded number p of subproblems of size-n/p at each stage, then the cost of the divide-and-conquer algorithm will be O(n log n).

(7) Parallelism: Normally DAC algorithms are used in multi-processor machines having shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.

(8) Memory access: These algorithms naturally make an efficient use of memory caches. Since the subproblems are small enough to be solved in cache without using the main memory that is slower one. Any algorithm that uses cache efficiently is called cache oblivious.

(9) Roundoff control: In computations with rounded arithmetic, e.g. with floating point numbers, a divide-and-conquer algorithm may yield more accurate results than a superficially equivalent iterative method. For example, one can add N numbers either by a simple loop that adds each datum to a single variable, or by a D And C algorithm that breaks the data set into two halves, recursively computes the sum of each half, and then adds the two sums. While the second method performs the same number of additions as the first, and pays the overhead of the recursive calls, it is usually more accurate.

2) Disadvantages

(1) It involves recursion which is sometimes slow

(2) Efficiency depends on the implementation of logic

(3) It may crash the system if the recursion is performed rigorously.

(4) Overhead: The process of dividing the problem into subproblems and then combining the solutions can require additional time and resources. This overhead can be significant for problems that are already relatively small or that have a simple solution.

(5) Complexity: Dividing a problem into smaller subproblems can increase the complexity of the overall solution. This is particularly true when the subproblems are interdependent and must be solved in a specific order.

(6) Difficulty of implementation: Some problems are difficult to divide into smaller subproblems or require a complex algorithm to do so. In these cases, it can be challenging to implement a divide and conquer solution.

(7) Memory limitations: When working with large data sets, the memory requirements for storing the intermediate results of the subproblems can become a limiting factor.

(8) Suboptimal solutions: Depending on how the subproblems are defined and how they are combined, a divide and conquer solution may not always produce the most optimal solution. In some cases, it may be necessary to apply additional optimization techniques to improve the final solution.

(9) Difficulty in parallelization: In some cases, dividing the problem into subproblems and solving them independently may not be easily parallelizable, leading to inefficient use of computational resources.

exercises

 

---

* 썸네일) https://www.vecteezy.com/vector-art/2210465-divide-and-conquer-red-gradient-concept-icon

* 출처1) https://www.geeksforgeeks.org/divide-and-conquer/