0. 문제

1992번: 쿼드트리

1. 문제 이해

• 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축.
• (0(0011)(0(0111)01)1)

왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 모두가 같은 값이 될 때까지 4등분 한다.

→ 재귀적으로 호출한다.

2. 제출

// 백준 1992번 퀴드트리
#include <iostream>
#include <string>

using namespace std;

const int max_n = 64;
const int dy[] = {0, 0, 1, 1};
const int dx[] = {0, 1, 0, 1};
int n, a[max_n][max_n];
string s, ret="";

string quadtree(int y, int x, int n){
    string str = "";
    bool pass = true;
    int tmp = a[y][x];

    for(int i=y; i<y+n; i++)
        for(int j=x; j<x+n; j++)
            if(a[i][j] != tmp)
                pass = false;

    if(pass){
        str += to_string(tmp); 
    }else{
        str += "(";
        for(int i=0; i<4; i++){
            int ny = y+dy[i]*n/2;
            int nx = x+dx[i]*n/2;
            str +=    quadtree( ny, nx, n/2);
        }
        str += ")";
    }

    return str;
}

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

    cin  >> n;

    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < n; j++){
            a[i][j] = s[j] - '0';
        }
    }

    ret = quadtree(0,0, n);

    cout << ret << "\n";

    return 0;
}
Code language: PHP (php)

• quadtree를 재귀적으로 호출.

string quadtree(int y, int x, int n){
    string str = "";
    bool pass = true;
    int tmp = a[y][x];

    for(int i=y; i<y+n; i++)
        for(int j=x; j<x+n; j++)
            if(a[i][j] != tmp)
                pass = false;

    if(pass){
        str += to_string(tmp); 
    }else{
        str += "(";
        for(int i=0; i<4; i++){
            int ny = y+dy[i]*n/2;
            int nx = x+dx[i]*n/2;
            str +=    quadtree( ny, nx, n/2);
        }
        str += ")";
    }

    return str;
}
Code language: JavaScript (javascript)

• 범위 n*n 내에 모든 값이 동일하면 그 값을 반환.
• 그렇지 않으면 괄호 안에 범위를 4 등분해서 quadtree를 재귀적으로 호출.

가. 개선점

int n, a[max_n][max_n];
...
string quadtree(int y, int x, int n){
Code language: CSS (css)

• 전역변수 n과 매개변수 n의 변수명이 동일해서 잘못 이해할 수 있다. 매개변수 n보다는 size로 교환할 것을 추천.

int tmp = a[y][x];
...
if(a[i][j] != tmp)

• tmp보다는 flag를 추천.

나. 분할 정복 알고리즘

위와 같은 것을 Divide & Conquer라고 한다.

**분할 정복 알고리즘(Divide and conquer algorithm)**은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.

• 분할 정복 알고리즘은 보통 재귀 함수(recursive function)를 통해 자연스럽게 구현된다.
• 빠른 실행이나 부문제 해결 순서 선택을 위해, 재귀호출을 사용하지 않고 스택, 큐(queue) 등의 자료구조를 이용하여 분할 정복법을 구현하는 것도 가능하다.

아래는 stack을 이용해서 분할 정복 알고리즘을 구현한 예시다.

[알고리즘] 3986번: 좋은 단어

0. 문제 3986번: 좋은 단어 1. 문제 이해 예제 입력 1 예제 출력 1 예제 입력 2 예제 출력 2 2. 제출 가. 틀렸습니다. 좋은 단어의 조건을 잘못 파악했다. 처음부터 계속 시간초과를 당하니깐 시간을 줄이는 것에 너무 신경 쓴 것 같다. 우선 돌아가도록 만드는 것이 더 중요한 것 같다. 나. 시간 초과 같지만 더 편한 방법이다. 조금 고쳐도 안된다. 다. 수정 “같은 글자가 연속되면 지운다. 이를 반복해서 모든 글자가 지워지면 좋은 글자다.”라는 조건 만족하는지 알기 위해서 string을 순회하면서 같은 글자가 연속되면 지우는 코드를 사용했다. 이와 같이 반복문을 이중으로 사용하기보다 “**스택”**을 사용하면 더 쉽고 빠르게 구현할 수 있다. 허무하다… 하나의 문제 … 더 읽기

출처 : https://ko.wikipedia.org/wiki/분할_정복_알고리즘