Grace

모든 i -> j에 대해 bfs가 성공하는지 여부를 탐색한다.

i에서 j로 가는 경로를 구하는 것이기 때문에 i==j인 경우에는 바로 bfs를 성공한다고 생각했는데 아니였다.

예제 2번의 경우 i=1, j=1 인 경우 경로가 없다는 결과였기 때문이다.

따라서  i==j 경우에는 bfs를 시작할때 방문배열을 체크하지 않고 다시 돌아오는지를 확인하였다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
int result[100][100]={0,};
vector<int> a[100];

void bfs(int start_x, int end_x){
    queue<int> q;
    int v[100]={0,};

    q.push(start_x);

    while(!q.empty()){
        int x = q.front();
        q.pop();

        if(x == end_x && v[x]==1){
            result[start_x][end_x] = 1;
            return;
        }

        for (int i = 0; i < a[x].size(); i++){
            int dx = a[x][i];
            if(v[dx]==0){
                q.push(dx);
                v[dx] = 1;
            }
        }
    }
    return;
}

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

    cin >> n;

    for (int i = 0; i < n; i++){
        for (int x,j = 0; j < n; j++){
            cin >> x;
            if(x==1)
                a[i].push_back(j);
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            if(result[i][j]==0)
                bfs(i, j);
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

처음에는 bfs로 5개의 테트로미노의 대칭과 회전 모양 모두를 고려해야 하는 줄 알았다. 시도해보다가 좀 말이 안된다는 생각이 들었다. 어떻게 할까 생각하다가 구글링을 통해 ㅗ모양의 테트로미노를 제외한 모든 테트로미노가 depth를 4로 하는 bfs(혹은 dfs)모양이라는 것이었다.

이 힌트를 토대로 모든 좌표를 돌면서 dfs를 depth 4까지만 수행하였다.

그리고 dfs와 함께 추가적으로 ㅗ모양 테트로미노에 대한 점수 카운팅도 해주었다.

ㅗ모양 테트로미노 점수계산시에, 2중 for문을 통해 상하좌우 중 무시할 방향을 한군데씩 골라 계산하게 되면 딱 ㅗ ㅜ ㅏ ㅓ 테트로미노를 모두 고려할 수 있다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int board[502][502] ={0,}; // 0~501 1~500에 저장.
int v[502][502] ={0,};
int answer = 0;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int isPass(int x, int y){
    return x >= 1 && y >= 1 && x <= n && y <= m;
}

void dfs(int x, int y, int score, int depth){
    if(depth==4){
        answer = max(answer, score);
        return;
    }

    for (int i = 0; i < 4; i++){
        int tx = x + dx[i];
        int ty = y + dy[i];
        if (isPass(tx, ty) && v[tx][ty] == 0)
        {
            v[tx][ty] = 1;
            dfs(tx, ty, score+board[tx][ty], depth+1);
            v[tx][ty] = 0;
        }
    }
}

void blockChect(int x, int y){
    for (int i = 0; i < 4; i++){
        // i - 무시할 방향.
        int score = board[x][y];
        for (int j = 0; j < 4; j++)
        {
            int tx = x + dx[j];
            int ty = y + dy[j];
            if(i != j){
                score += board[tx][ty];
            }
        }
        answer = max(answer, score);
    }
    return;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> board[i][j];
        }
    }

    for (int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            v[i][j]=1;
            dfs(i, j, board[i][j], 1);
            v[i][j]=0;

            blockChect(i, j);
        }
    }

    cout << answer << endl;

    return 0;
}

ps. 처음에는 dfs가 아닌 bfs로 짜다가 queue안의 요소가 너무 복잡해졌다. 그래서 tuple을 이용해 x,y좌표, 점수, 깊이, 방문배열을 넣었는데 tuple안에는 int 배열을 넣을 수 없는 모양이였다..

나는 한동인이다.

입학때 부터 갈대상자라는 책이 한동의 역사를 담고 있는 책이라는 말을 많이 들어왔었다. 하나님의 대학 한동대학교, 설립때부터 하나님께서 역사하셨다는 식의 이야기들을 꽤 많이 들어왔다. 하지만 그때마다 별 감흥없이 당연하다는 듯이 생각했다.

한동에 대해 모르는 것들이 너무 많았다. 아니, 몰랐다기 보다는 깊에 생각해본적이 없었다고 하는 편이 맞을 것 같다. 한동명예제도 아너코드 무감독양심 갈대상자후원금 팀제도 기숙사.  이러한 제도들은 나에겐 그저 당연한 것이였다. 그저 당연한 것 처럼 여기고 있었던 한동의 다양한 제도와 문화들이었다. 갈대상자를 통해 그 본질을 깨닫고 나의 마음에 한동의 정신을 새기는 듯한 시간이었다. 그리고 한동이 설립과정부터 정상운영되기까지 정말로 하나님께서 역사하셔서 세우신 대학이라는 사실이 피부로 와닿았다. 어떤 것을 바라보든지 간에 그 대상의 역사적 맥락을 구체적으로 인지하는 것이 많은 효용을 가져다 주는 것 같다.

최근 서구문명, 종교개혁, 서양사 등을 공부하면서 알게된 역사적 흐름을 기반으로 현재의 현상에 대한 의미와 본질을 깨닫게 되는 순간들이 있다. 그 때마다 내가 뜬구름 잡듯이 알고 있던 역사들이 선조들의 산물이 아니라 세상을 주관하시는 하나님의 산물이라는 것을 점점 깨닫게 되는 듯 하다. 정말로 놀랍고 신비롭다. 갈대상자에서도 비슷한 느낌을 받는다.

그리스도인 김영길

한동대 초대 총장이셨던 김영길 총장님에 대해 별로 아는 것이 없었다. 그저 초대 총장이셨다는 사실뿐이였다. 갈대상자를 통해 김영길 초대총장님의 헌신적이고 순종적인 삶의 모범적인 태도를 볼 수 있었다. 고난 속에서 하나님만을 바라보는 귀한 그리스도인의 모습이었다. 세상사람들의 비난과 질타, 수많은 고발 가운데 아파하고 눈물흘리면서도 하나님의 인정만을 의지하시는 모습을 보았다. 한동을 세워가야 한다는 사명 하나만 보고 달리는 용맹하지만 동시에 따뜻함을 가진 전사셨다.

내가 이렇게 새워진 한동의 학생이라는 사실이 어색할 정도로, 그리고  그 무게가 굉장하다는 생각이 들정도로 한동은 너무나 많은 핍박과 역경을 시간 속에 단련되었던 것 같다. 뭐 만하면 일이 생기고 막히고 앞이 보이지 않았을까. 그 만큼 하나님만을 의지하는 믿음의 연단을 위함이었겠지만 글로 읽는 순간에도 내 마음 답답하고 아려 온다.

한동의 비전과 문화와 제도에 대한 공감과 재정비

내가 체험했던 다양한 한동의 문제와 제도들은 총장님께서 그리셨던 한동의 비전과 철학의 산물이였다. 그 철학의 본질에 대해 공감하고 정비할 수 있었다. 다시금 한동으로 복학하여 살아갈때 나는 어떻게 살아갈 것인가. 지성과 영성, 인성을 단련하는 전인적인 수재가 되어야겠다는 마음을 가지고 그렇게 실천하며 살아내야 겠다고 다짐하는 시간이었다.

4인실 생활이 힘들다고 하는 몇몇 학우들의 말을 듣는다. 기숙사 생활에 대해서 깊게 생각해 본 적이 없다. 갈대상자를 통해 생활관의 본질이 인성교육에 있었다는 것을 알게 되었다. 인성교육을 강조하며 빚을 져가면서까지 생활관 건설을 위해 힘썼던 총장님이셨다. 생활하는 과정 가운데 철이 철을 날카롭게 하듯 학생들의 인성과 인격의 성숙을 바라보셨다. 기숙사는 경쟁이 아닌 함께 양보하며 더불어 살아가는 방법을 배우는 시간과 공간이었다.

한동에 얽힌 많은 사연들이 갈대상대에 담겨있다. 농구장, 비전광장, 채플, 바베큐 파티, 기숙사 등등 어느것 하나 눈물의 사연이 담겨있지 않은 것이 없는 것 같다.. 뭐하나 얽히고 섥히지 않은것이 그리고 하나님의 손길이 닿지 않은곳이 없는 것 같다. 한동에서 생활하면서 이러한 이야기들를 나누며 감동을 나눌 수 있지 않을까. 팀모임이나 각 공동체에서 갈대상자 읽기 챌린지 같은 것을 통해 한동의 역사를 알아가고 나누면 어떨까. 더욱 풍성한 한동생활이 될 것 같다. 내년에 한동에 다시가면 내가 마주했던 한동의 역사들의 산물로 바라보며 가슴이 굉장히 벅차오를 듯 한 느낌이 든다.

한동의 주인은 하나님이시다. 한동에서 수없이 듣고 고백했던 말이다. 갈대상대를 읽으면서 이 말이 한층더 깊게 다가왔다. 잠시 꿈속에서 직접적으로 체험하고 겪고 깬듯한 느낌이었다. 전에 느껴본적 없었던 감동이 나안에 생겨났다. 한동의 주인은 하나님이십니다. 고백하는 문구에 어찌나 눈물이 나던지 모른다.

결론

한동은 그냥 세워진 대학이 아니다. 진정으로 하나님께서 세우신 하나님의 대학이다. 갈대상자에 담긴 다양한 사례와 간증을 통해 한동을 느끼고 바라보았다. 한동인으로서 한동의 가치를 수호해야할 거룩한 사명감을 느끼게 되는 시간이었다. 23년도 새내기 섬김이를 지원한 후 읽는 터라 그 감동과 비전이 더욱 생생하게 다가왔고 앞으로의 남은 두번의 해 동안에 한동에서의 시간 동안 영적 인성적 지적으로 성장해 전인적으로 훌륭한 사람이 되야겠다고 다짐했다. 전인적 교육이라는 단어는 계속 이때까지 많이 들어왔지만 갈대상자를 통해 깊은 본질을 깨닫게 되니 그 열기가 느껴지듯 피부로 가까이 다가왔다. 

한동이 왜 한동 다운지 우리가 지켜야할 가치는 무엇인지 왜 한동이 귀한지 얼마나 감사한 한동인지 알게 되는 것은 한동의 과거와 그 본질을 바라볼 때인 것 같다. 현재를 점검하고 미래를 바라보며 그 가치를 지키고 널리 전하기 위해 실천하고 행동할 때 무너지지 않는 견고한 담장을 세워 나갈 수 있을 것이다

❗ 인터럽트 기반 운영체제

현대의 운영체제는 모두 인터럽트를 기반으로 작동한다. 즉 부팅을 마친 후에는 인터럽트가 걸릴때 까지 운영체제는 아무일도 하지 않는 것이다.

우선 1)인터럽트가 무엇인지 알아보고 2)인터럽트가 발생할 경우 운영체제가 이를 어떻게 처리하는지 과정을 알아보자.

인터럽트란?

인터럽트에는 3가지 종류가 있다. 하드웨어, 소프트웨어 그리고 내부적으로 발생되는 인터럽트가 있다.

1. 하드웨어 인터럽트 : 마우스를 움직이거나 키보드를 타이핑하는 등 하드웨어적인 동작으로 인해 발생하는 인터럽트이다.
2. 소프트웨어 인터럽트 : 프로세스 내부에서 파일을 읽는 다거나 프린터를 동작하는 등 소프트웨어 자체적으로 인터럽트가 발생하는 경우이다.
3. 내부 인터럽트 : 프로그램 내부에서 허용되지 않는 접근을 시도한다던가 DivideByZero같은 계산이 발생하는 경우 내부적인 인터럽트로 인식이 된다.

인터럽트가 발생할 경우 운영체제의 동작

1. 어떤 경로로든 인터럽트가 발생할 경우에는 가장 먼저 CPU가 인터럽트를 인지하게 된다.
2. 인터럽트를 인지한 CPU는 지금 하고 있는 동작을 중지한 후
3. 메모리에 올라와 있는 운영체제 안에 존재하는 인터럽트를 처리하는 루틴(ISR, interupt service routine)으로 jump하게 된다.
4. 운영체제에는 각종 상황에 따른 ISR이 존재한다. 운영체제에서 ISR이 모두 실행되고 나면 다시 CPU는 원래하던 작업으로 돌아오게 된다.

이러한 방식으로 운영체제는 인터럽트를 기반으로 동작하게 된다.

주어진 문자열을 탐색하면서 n에 해당하는 IO패턴의 개수를 카운팅한 후 출력한다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

    int n, m;
    string str;
    vector<int> res;
    int result = 0;
    cin >> n >> m >> str;

    int count = 0;
    bool pass = true;
    for (int i = 0; i < str.size(); i++){
        if ((pass && str[i] == 'I') || (!pass && str[i] == 'O'))
        {
            count++;
            pass = !pass;
        }
        else if(str[i] == 'I')
        {
            if(2*n+1 <= count){
                if(str[i]=='O')
                    count--;
                res.push_back(count);
            }
            count = 1;
            pass = false;
        }else{
            if(2*n+1 <= count){
                if(str[i]=='O')
                    count--;
                res.push_back(count);
            }
            count = 0;
            pass = true;
        }
    }
    if(2*n+1 <= count)
        res.push_back(count);

    for (int i = 0; i < res.size(); i++){
        result += (res[i] - (n * 2 - 1)) / 2;
    }
    cout << result << "\n";
    return 0;
}

1. str splite : substr을 이용해 '['와']'를 제거한 후  getline을 이용해서 받은 문자열을 splite 했다.

2.  명령 문자열(inst)를 순회하면서 reverse여부에 따라 앞에서 pop해야하는 횟수와 뒤에서 pop해야 하는 횟수를 카운팅한다.

3. pop의 횟수가 nums.size()보다 클 경우는 error를 출력한다.

4. 그렇지 않은 경우에는 카운팅한 값을 토대로 pop을 진행한 뒤 result 문자열을 만들어 출력한다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <deque>
#include <sstream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 0;
    cin >> t;
    while(t--){
        string inst, str, buffer;
        char delim = ',';
        deque<string> nums;
        int n, front_count = 0, back_count = 0;
        bool isReverse = false;

        cin >> inst >> n >> str; 

        //str splite
        str = str.substr(1, str.size() - 2);
        stringstream f(str);
        while (getline(f, buffer, delim))
        {
            nums.push_back(buffer);
        }

        //inst 순회하며 카운팅.
        for (int i = 0; i < inst.size(); i++)
        {
            if(inst[i]=='R')
                isReverse = !isReverse;
            else{
                if(isReverse)
                    back_count++;
                else
                    front_count++;
            }
        }

        //result print
        if (back_count + front_count > nums.size())
        {
            cout << "error" << endl;
        }
        else
        {
            string result = "[";
            bool isFirst = true;

            //nums pop
            for (int i = 0; i < front_count; i++)
                nums.pop_front();
            for (int i = 0; i < back_count; i++)
                nums.pop_back();

            //result string 만들기
            if(isReverse){
                for (int i = nums.size() - 1; i >= 0; i--)
                {
                    if(!isFirst){
                        result += ",";
                    }else{
                        isFirst = false;
                    }
                    result += nums[i];
                }
            }else{
                for (int i = 0; i < nums.size(); i++){
                    if(!isFirst){
                        result += ",";
                    }else{
                        isFirst = false;
                    }
                    result += nums[i];
                }
            }
            //print
            result += "]";
            cout << result << "\n";
        }
    }
    return 0;
}

solve() : 전체 그림을 탐색하면서 bfs를 수행하는 횟수를 카운팅한다.

bfs() : 파라미터로 option을 넣어서

0일 경우에는 R / G / B 를 구분하는 탐색을 진행하고

1일 경우에는 R,G / B 를 구분하는 탐색을 진행하도록 했다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n;
int fdx[4] = {0, 0, 1, -1};
int fdy[4] = {1,-1,0,0};
int v[100][100]={0,};
string a[100];

bool checkPosition(int x, int y){
    return x >= 0 && y >= 0 && x < n && y < n ? true : false;
}

void bfs(int sx, int sy, int option){
    queue<pair<char, pair<int,int>>> q;

    q.push({a[sx][sy], {sx,sy}});
    v[sx][sy] = 1;

    while (!q.empty())
    {
        int x = q.front().second.first;
        int y = q.front().second.second;
        char w = q.front().first;
        q.pop();
        for (int i = 0; i < 4; i++){
            int dx = x + fdx[i];
            int dy = y + fdy[i];
            if(checkPosition(dx,dy) && v[dx][dy] == 0){
                bool canPush = false;
                char dw = a[dx][dy];
                if(w == dw){
                    canPush = true;
                }
                if(option == 1){
                    if((w == 'R' || w == 'G' ) && (dw == 'R' || dw == 'G' )){
                       canPush = true; 
                    }
                }
                if(canPush){
                    q.push({dw, {dx, dy}});
                    v[dx][dy] = 1;
                }
            }
        }
    }
}

void solve(){
    int count = 0;
    int countRG = 0;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            if(v[i][j] == 0){
                count++;
                bfs(i,j,0);
            }
        }
    }

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            if(v[i][j] == 0){
                countRG++;
                bfs(i,j,1);
            }
        }
    }
    cout << count << "\n";
    cout << countRG << "\n";
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    solve();
}

recursion 탐색 단계에서 현재 범위의 배열이 같은 숫자로 이루어지지 않은 경우

1. 결과 벡터에'(' push

2. 4범위로 분할하여 recursion

3. 결과 벡터에')' push

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int a[64][64]={0,};
vector<char> v;

void solve(int x, int y, int n){
    int target = a[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++){
            if(target != a[i][j]){
                v.push_back('(');
                solve(x, y, n / 2);
                solve(x, y + n / 2, n / 2);
                solve(x + n / 2, y, n / 2);
                solve(x + n / 2, y + n / 2, n / 2);
                v.push_back(')');
                return;
            }
        }
    }

    char temp = (char)target;
    v.push_back(temp);
    return;
}

int main(){
    int n;
    string str;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> str;
        for (int j = 0; j < n; j++){
            a[i][j] = str[j];
        }
    }

    solve(0,0,n);

    for (int i = 0; i < v.size(); i++){
        cout << v[i];
    }
}