2020 동계 모각코 5주차

오늘의 계획

• 대표적인 관계형 DB인 MYSQL 강의 듣기

  • 섹션 4 - MySQL CRUD

• 분할정복 알고리즘 공부 및 문제 풀이

  • 백준 문제 풀이

---

오늘의 회고

• 인프런 DataBase 강의 수강

  

  • topic table의 description : DESC topic;

  

  • create row : INSERT INTO topic () VALUES();

  

  • read row (topic table로부터 모든 정보를 가져와 선택) : SELECT * FROM topic;

  

  • 5개의 행을 create 한 뒤 read한 모습

  

  • 테이블에서 표시하고 싶은 열만 표시

  

  • author의 이름이 egoing인 것만 표시

  

  • 내림차순으로 정렬

  

  • 2개만 표시

  

  • UPDATE : id가 2인 행의 description과 title을 각각의 값으로 수정

  

  • DELETE : id가 5인 행을 삭제

• 분할정복 알고리즘 문제 : 백준 SILVER 2(종이의 개수)

  • 분할정복 알고리즘 : 분할 정복 알고리즘은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이나 알고리즘을 의미한다. 보통 재귀 함수를 통해 구현된다.

  

  • 해결 방법 :

    • 우선 현재 종이의 위치를 x,y로 나타내고 종이의 크기를 n으로 나타내었다.
    • paper 2차원 배열을 만들어 입력 받은 N으로 N*N 크기의 벡터를 만들었고, paper_count 배열을 만들어 0번째 인덱스에는 -1, 1번째 인덱스에는 0, 2번째 인덱스에는 1로 이루어진 종이의 개수를 세어 저장하였다.
    • 기본적으로 0,0의 인덱스부터 시작해 재귀함수를 통해 구현하였고, check 함수를 통해 현재 확인하고자 하는 크기의 종이에서 다른 수로 되어 있는 종이가 있는지 체크하여 같다면 return으로 돌아가고, 다른 경우에는 9분할하여 다시 재귀하는 방식을 통해 문제를 해결하였다.

  • 코드

    ```c++
    #include <iostream>
    #include <vector>
    
    using namespace std;
    vector<vector<int>> paper;
    int paper_count[3];
    
    //종이가 모두 같은 수로 되어 있는지 체크하는 함수
    bool check(int x, int y, int n) { //n = 현재 크기
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (paper[x][y] != paper[i][j]) return false; //다른 수로 되어 있는 종이가 있다면 false 반환
            }
        }
        return true;
    }
    
    void solution(int x, int y, int n) {
        //paper_count[0] == -1 , paper_count[1] == 0 , paper_count[2] == 1
        if (check(x, y, n)) { //같은 경우
            paper_count[paper[x][y] + 1] += 1;
            return;
        }
        //다른 경우 9분할하여 재귀
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                solution(x + i * (n / 3), y + j * (n / 3), n / 3);
            }
        }
    }
    
    int main(void) {
        int N;
        cin >> N;
        paper = vector<vector<int>>(N, vector<int>(N, 0)); //입력받은 N만큼 N*N을 0으로 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> paper[i][j];
            }
        }
        solution(0, 0, N);
        for (int i = 0; i < 3; i++) {
            cout << paper_count[i] << endl;
        }
    }
    ```