Algorithm&DataStructure - Divide and Conquer

1 Divide and Conquer

- 분할 정복

- 재귀를 활용

- 퀵소트, 머지소트, n제곱 구하기 등에 활용

• 1단계  : 분할, 원래 문제를 분할하여 비슷한 유형의 하위 문제들로 나눔
• 2단계 : 정복, 하위 문제를 정복. 이때 분할, 탈출 조건을 설정하여 재귀로 해결한다.
• 3단계 : 합치기, 정복된 문제들을 종합하여 초기 문제를 해결

- 즉 한 문제를 유형이 비슷한 여러개의 하위 문제들로 나누어 해결하고 나중에 합친다.

2 백준 2630번: 색종이 만들기

- 0 또는 1로만 이루어진 정사각 색종이들의 수를 구하라

#include <iostream>
using namespace std;

class Paper{
private:
  int n;
  bool** table;
  int blue;
  int white;

public:
  Paper(int _n):n(_n),blue(0),white(0){
    table = new bool*[n];
    for(int i =0; i<n; i++){
        table[i] = new bool[n];
    }

    for(int i =0; i<n; i++){
      for(int j =0; j<n; j++){
        cin>>table[i][j];
      }
    }
  }

  void Divide(int x, int y, int n){

    bool flag = true;
	// 정사각 꼴을 이루는지 확인
    for(int i = x; i<x+n; i++){
      for(int j = y; j<y+n; j++){
        if(table[x][y] != table[i][j]){
          flag = false;
          break;
        }
      }
      if(!flag) break;
    }

    // 정사각 꼴이라면 divide 멈추고 conquer->탈출
    if(flag){
      if(table[x][y] == 1) blue++;
      else white++;

      return;
    }
	// 정사각 꼴이 아니라면 divide진행
    Divide(x, y, n/2);
    Divide(x+n/2, y, n/2);
    Divide(x,y+n/2, n/2);
    Divide(x+n/2, y+n/2, n/2);
  }

  void PrintResult(){
    cout<<white<<endl;
    cout<<blue<<endl;
  }

  ~Paper(){
    for(int i =0; i<n; i++){
        delete[] table[i];
    }
    delete[] table;
  }
};


int main() {
  int n;
  cin>>n;

  Paper paper(n);
  paper.Divide(0,0,n);
  paper.PrintResult();
}

3 백준 1629번: 제곱

- 분할 정복으로 제곱을 빠르게 수행해보자.

#include <iostream>
#include <cmath>
using namespace std;

long int Divide(int a, int b, int c){
  // 탈출조건
  if(b<=1) return a;
  if(b%2!=0){
    // 홀수일때 분할: 1 and n-1
    return Divide(a,b-1,c) * a % c;
  }else{
    // 짝수일때 분할: n/2 and n/2
    long int x = Divide(a,b/2,c);
    return x * x % c;
  }
}

int main(){
  
  int A,B,C;
  cin>>A>>B>>C;
  
  cout<<Divide(A,B,C)%C;
}