[TIL] 24.01.24

1. 알고리즘 문제 풀이

 

 

알파벳(백준 1987):

 기본적인 DFS, 백트래킹 문제이다. DFS로 탐색하되 인접 칸이 모두 유효하지 않을 경우, 현재까지의 이동 칸 수를 가지고 최대 이동 칸 수를 갱신한 뒤 백트래킹으로 돌아간다. 원래 탐색 알고리즘에서는 노드의 방문처리가 필요한데, 이 문제에선 방문한 알파벳을 확인해야하므로 이를 통해 노드의 방문처리도 가능하다. 비트마스크를 이용하면 좀 더 최적화가 가능할 것 같긴하다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int dx[4] = {1, 0 , -1, 0};

int dy[4] = {0, 1, 0, -1};

vector<vector<char> > matrix;

vector<bool> isVisited(26, false);

int w, h, maxNum=1;

bool isValid(pair<int, int>& p) {

    return p.first>=0 && p.second>=0 && p.first<h && p.second<w && isVisited[matrix[p.first][p.second]-'A']==false;

}

void DFS(pair<int, int> p, int curBlockNum) {

    bool flag = false;

    isVisited[matrix[p.first][p.second]-'A'] = true;

    for(int i=0; i<4; i++) {

        pair<int, int> nextP = make_pair(p.first+dy[i], p.second+dx[i]);

        if(isValid(nextP)) {

            flag = true;

            DFS(nextP, curBlockNum+1);

        }

    }

    if(!flag) {

        maxNum = max(maxNum, curBlockNum);

    }

    isVisited[matrix[p.first][p.second]-'A'] = false;

}

int main() {

    cin.tie(nullptr);

    ios_base::sync_with_stdio(false);

    cin >> h >> w;

   

    matrix = vector<vector<char> >(h, vector<char>(w));

    for(int i=0; i<h; i++) {

        for(int j=0; j<w; j++) {

            cin >> matrix[i][j];

        }

    }

   

    DFS(make_pair(0, 0), 1);

    cout << maxNum;

}

 

 

 

 

색종이 붙이기(백준 17136):

 처음에 큰 색종이부터 작은 색종이까지 좌상단부터 그리디 하게 붙이는 알고리즘을 사용해서 풀었는데, 틀렸습니다가 떴다. 생각해보니 큰 색종이부터 붙인다고 최적해가 찾아지는 것은 아니었다. 종이의 크기가 10*10으로 작았기 때문에 브루트 포스와 백트래킹으로 모든 경우를 탐색하기로 했다.

 

 전체 종이의 좌상단에서부터 1이 처음 등장하는 곳을 찾고 그 곳에 크기별 색종이를 붙일 수 있는지 확인한 후, 붙일 수 있다면 붙인다. 그 다음 또 1이 처음 등장하는 곳을 찾아 크기별 색종이를 붙일 수 있는지 확인한 후 붙이는 것을 반복한다. 만약 더 이상 1이 등장하는 곳이 없다면 종이를 다 채운 것이므로 최소 색종이 수를 갱신하고, 탐색 과정에서 최소 색종이 수보다 더 많은 종이를 사용중이라면 백트래킹으로 돌아간다. 물론, 남은 1이 존재하지만 붙이려고 하는 크기의 색종이를 모두 소모한 경우나 해당 색종이를 붙일만큼 공간이 나지 않는 경우는 더 탐색하지 않는다.

 

  위와 같은 흐름으로 알고리즘을 작성했고, 이제 색종이를 붙이는 모든 경우를 따질 수 있게 되어 통과했다. 어떻게 하면 색종이를 붙이는 모든 경우를 효율적으로 따져볼 수 있을까를 떠올리는 것이 까다로운 문제였다. 크기 별로 붙일 수 있는 케이스를 모두 배열에 저장해놓고, 하나하나 선택된 케이스와 선택되지 않은 케이스로 나누어 계산해볼까도 생각했다. 그러면 아마 워스트 케이스가 종이의 모든 칸이 1일 경우일 것인데, 연산횟수를 어림잡다가 바로 포기했다..

#include <iostream>

using namespace std;

int paper[10][10] = {0,};

int colorPaper[6] = {0, 5, 5, 5, 5, 5};

int nextY=0, nextX=0;

int minColorPaper = 26;

void fill(int y, int x, int size, int num) {

    for(int i=y; i<y+size; i++) {

        for(int j=x; j<x+size; j++) {

            paper[i][j] = num;

        }

    }

}

bool canFill(int y, int x, int size) {

    if(y+size>10 || x+size>10) {

        return false;

    }

    for(int i=y; i<y+size; i++) {

        for(int j=x; j<x+size; j++) {

            if(paper[i][j]==0) {

                return false;

            }

        }

    }

    return true;

}

void findNext(int y, int x) {

    for(int i=y; i<10; i++) {

        for(int j=0; j<10; j++) {

            if(paper[i][j]==1) {

                nextY = i;

                nextX = j;

                return;

            }

        }

    }

    nextY = -1;

    nextX = -1;

    return;

}

void DFS(int y, int x, int cnt) {

    if(minColorPaper<=cnt) {

        return;

    }

    findNext(y, x);

    if(nextX==-1&&nextY==-1) {

        minColorPaper = cnt;

        return;

    }

    int nY = nextY;

    int nX = nextX;

    for(int k=5; k>=1; k--) {

        if(colorPaper[k] == 0) continue;

        if(!canFill(nY, nX, k)) continue;

        colorPaper[k]--;

        fill(nY, nX, k, 0);

        DFS(nY, nX, cnt+1);

        fill(nY, nX, k, 1);

        colorPaper[k]++;

    }

}

int main() {

    for(int i=0; i<10; i++) {

        for(int j=0; j<10; j++) {

            cin >> paper[i][j];

        }

    }

    DFS(0, 0, 0);

    if(minColorPaper==26) {

        cout << "-1";

        return 0;

    }

    cout << minColorPaper;

    return 0;

}

 

 

2. 데일리 미션 - 앱개발 용어 정리 

 

-IDE: 통합 개발 환경, 소프트웨어 개발을 위한 모든 작업을 하나의 프로그램 안에서 처리할 수 있도록 처리한 것.

-컨벤션(코딩 컨벤션): 약속된 코딩 스타일, 규칙. 다수의 인원이 개발하는 프로젝트라면, 가독성 및 유지보수를 위해 필수적.

-자료형: 데이터의 형식을 식별할 수 있게 하는 분류. 이를 통해 메모리 상에서 비트의 나열인 데이터를 구분하여 처리할 수 있다.

-변수와 상수: 변수는 런타임 중에 변경될 수 있으며, 상수는 변경될 수 없다. 일반적으로 상수는 메모리의 Code 영역에 로드되어 Read-Only로 동작하게 된다.

-메소드: 클래스 내에서 기능을 함수형태로 구현해놓은 부분.

-클래스: 특정 속성 값들을 보유하고, 특정한 기능을 하는 인스턴스를 생성하기 위해 정형화 해놓은 틀.