[Algorithm] 분할 정복(Divide&Conquer)이란?

🚦 이번 포스팅에서는 〰️

▶️ 분할 정복(Divide&Conquer) 알고리즘이란?
▶️ 분할 정복(Divide&Conquer) 알고리즘 문제 풀어보기

 

📌분할 정복(Divide&Conquer) 알고리즘이란?

---

: 나누고 정복한다는 의미로, 크고 복잡한 문제를 작은 단위로 나눠 해결한 후 다시 합치는 알고리즘이다. (Top-down 형태)

• 현재의 선택이 나중에 미칠 영향을 고려하지 않는다.
• 그렇기 때문에, 그 정당성 분석이 중요하다.
  ▶️ 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 필요!
• 동적(dynamic) 프로그래밍 사용 시 지나치게 많은 일을 하는 것을 보완하기 위한 개념이다.
• 대표적인 문제로 거스름돈 문제, 활동 선택 문제 등이 있다.

 

〰️ 분할 정복법의 과정

1. Divide : 문제를 부분 문제로 분할하는 과정 ➡️ 가운데를 쪼개므로 O(1)
2. Merge : 각 문제에 대해 구한 값을 원래 문제에 대한 답으로 병합하는 과정 ➡️ O(n)
3. Base Case : 더이상 분할이 안되고 곧장 풀 수 있는 매우 작은 문제

 

〰️ 일반 재귀호출과 다른점

: 문제를 거의 같은 크기의 부분문제로 나눈다는 것! (가운데에서 쪼갠다)

 

 

〰️ 동적 계획법 vs 분할 정복법

: 우선 분할 정복법이란 큰 문제를 여러개의 작은 문제로 나누어 푸는 것을 말한다.

• 분할 정복법은 큰 문제를 여전히 다뤄질 수 있는 작은 문제로 분해해 가는 과정이 필요할 때 이용한다.
• 동적 계획법은 작은 문제들의 중첩의 과정에서 큰 문제를 해결할 때 이용한다.
• 동적 계획법(DP)이 분할 정복법보다 더 빠르다.
  ➡️ DP는 문제의 답을 저장해놓았다 답만 가져오기 때문에 초반에는 분할 정복법보다 시간이 더 걸릴 수 있지만, Input이 커지면 분할 정복법은 같은 문제를 계속해서 다시 풀기 때문에 시간이 기하급수적으로 늘어난다.

 

 

https://www.interviewbit.com/blog/difference-between-divide-and-conquer-and-dynamic-programming/

Divide&Conquer

 

 

동적 계획법이 더 궁금하다면? >> 동적계획법(dynamic programming) 이란? 참고

 

〰️ 그렇다면 분할 정복이 효과적일 때는 언제일까??

1. 수열의 빠른 합
   기존 재귀 호출 시간 복잡도 : sum(n) = 1+2+3+...+n
   분할 정복 시간 복잡도 : sum(n) = 2*sum(n / 2) + n2 / 4 (n은 짝수)
2. 행렬의 빠른 제곱
   행렬 또한 반으로 나누어 계산이 가능하므로 훨씬 빠르게 계산이 가능하다. 대신 n은 짝수!
3. 대표적인 예 : 병합정렬, 퀵정렬
   ➡️ 자세한 병합정렬, 퀵정렬 설명은 [Algorithm] Sorting Algorithm (정렬 알고리즘)  참고

 

 

〰️ 그렇다면 홀수일때는????

중복으로 구해야하는 값들이 많아져서 값이 증가함에 따라 호출 횟수가 선형적으로 증가한다.

이 경우 분할 정복을 하는 의미가 없게 된다.

이런!! 중복문제를 보완하는 방안이 동적 계획법이다.

 

 

📌분할 정복(Divide&Conquer) 알고리즘 문제 풀어보기

---

1️⃣ 백준 1074 Z

 

 

 

사실 문제를 어떻게 풀어야할지 전혀 감이 오지 않아서 다른 분의 블로그를 참고하였다. 하지만 혼자 했으면 못풀었을듯..

다시 복기해야겠다..ㅠㅠ (참고 - https://wjdgus2951.tistory.com/60)

 

우선 생각해야할 것

: 사분면은 늘 사분면으로 쪼갤 수 있다(2^1이 되기 전까지, 그리고 좌표는 그 안에 위치한다) + 우리가 찾는 좌표가 어느 사분면에 위치하는지만 알면 된다.

 

💡key point

우리가 찾는 좌표가 어느 사분면에 있는지 알아낸다면, 나머지 사분면은 그냥 탐색한 것으로 치고 더해주면된다!

(ex) 좌표가 3사분면에 위치해 있다면 1,2사분면은 이미 탐색을 완료했을것이므로, 답에 더해주면된다.

 

1. 우선 가장 큰 사분면부터 쪼개나간다. (전체)
2. 그리고 만약 r, c의 값이 그 사분면 안에 존재한다면 존재하는 사분면을 4개로 다시 쪼개나간다.
3. 만약 존재하지 않는다면 해당 사분면은 탐색한 것으로 간주, 사분면의 크기만큼 (n*n) 더해준다.
4. 사분면을 쪼개나갈 때 사분면의 길이인 n의 크기를 절반씩 줄여나간다. (처음 크기 = N)

#include <iostream>
using namespace std;

int N, r, c;
int x, y, ans;

void Z(int x, int y, int n)
{
    if(x==r && y==c) { //만약 x,y가 r,c와 같다면 찾은것임
        cout << ans << "\n";
        return;
    }
    if(r>=x && r<x+n && c>=y && c<y+n)
    {
        //1사분면 검사
        Z(x, y, n/2);
        //2사분면 검사
        Z(x+n/2, y, n/2);
        //3사분면 검사
        Z(x, y+n/2, n/2);
        //4사분면 검사
        Z(x+n/2, y+n/2, n/2);
    }
    else { //해당 사분면에 존재하지 않다면 탐색한 것으로 간주하고 skip한다.
        ans += n*n; //사분면의 크기만큼 더해줌 (사분면의 길이 = n)
    }
}


int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> r >> c;

    //pow(2,N) : 1 << N (left shift)
    Z(0,0,(1 << N));

    return 0;
}

 

 

 

[Reference]

https://syh39.github.io/algorithm/algorithm_DandC_DP/

https://velog.io/@turtle601/%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5