재시민

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner?&utm_source=clipboard&utm_medium=text

중요포인트

행과 열을 헷갈리지 말자!!

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <iomanip>

using namespace std;

struct Player {
    int y, x, howmany;
};

int N, M, K, exitY, exitX, maze[11][11], player[11][11], dy[4] = { -1,1,0,0 }, dx[4] = { 0,0,-1,1 }, totalDis = 0;

void printMaze() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << setw(3) << maze[i][j];
        }
        cout << "\n";
    }
}

bool oob(int y, int x) {
    return y < 1 || x < 1 || y > N || x > N;
}

void rotate(tuple<int, int, int> pointWithSize) {
    int size = get<2>(pointWithSize);
    vector<vector<int>> tmp(size + 1, vector<int>(size + 1, 0));
    int row = get<0>(pointWithSize), col = get<1>(pointWithSize);

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            tmp[j][size - i + 1] = maze[row + i - 1][col + j - 1];
            if (tmp[j][size - i + 1] > 0) tmp[j][size - i + 1]--;
        }
    }

    for (int i = 1; i <= size; i++) {
        for (int j = 1; j <= size; j++) {
            maze[row + i - 1][col + j - 1] = tmp[i][j];
        }
    }
}

tuple<int, int, int> findSmallSqure() {
    tuple<int, int, int> pointWithSize;
    int eY, eX;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (maze[i][j] == -11) {
                eY = i;
                eX = j;
            }
        }
    }

    for (int size = 2; size <= N; size++) {
        for (int i = 1; i <= N - size + 1; i++) {
            for (int j = 1; j <= N - size + 1; j++) {
                int peopleCount = 0;
                bool hasExit = false;

                for (int row = i; row < i + size; row++) {
                    for (int col = j; col < j + size; col++) {
                        if (maze[row][col] == -11) hasExit = true;
                        else if (-10 <= maze[row][col] && maze[row][col] <= -1) peopleCount += -1 * maze[row][col];
                    }
                }

                if (hasExit && peopleCount >= 1) {
                    pointWithSize = {i, j, size};
                    return pointWithSize;
                }
            }
        }
    }
    return pointWithSize;
}

void move() {
    int eY, eX, tmp[21][21];
    queue<pair<int, int>> q;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            tmp[i][j] = 0;
            if (maze[i][j] == -11) {
                eY = i;
                eX = j;
            } else if (maze[i][j] <= -1 && -10 <= maze[i][j]) {
                q.push({i, j});
            }
        }
    }

    while (!q.empty()) {
        int curY = q.front().first, curX = q.front().second;
        q.pop();
        int moveY = 0, moveX = 0, exitDis = abs(eY - curY) + abs(eX - curX);

        for (int d = 0; d < 4; d++) {
            int ny = curY + dy[d], nx = curX + dx[d];
            if (oob(ny, nx) || maze[ny][nx] > 0) continue;
            int dis = abs(ny - eY) + abs(nx - eX) + 1;
            if (exitDis < dis) continue;
            else if (exitDis == dis) {
                if ((eY - curY > 0 && ny - curY > 0) || (eY - curY < 0 && ny - curY < 0) || maze[ny][nx] == -11) {
                    moveY = ny;
                    moveX = nx;
                } else if (moveY == 0) {
                    moveY = ny;
                    moveX = nx;
                }
            }
        }

        if (moveY != 0) {
            totalDis += maze[curY][curX] * -1;
            if (maze[moveY][moveX] != -11) tmp[moveY][moveX] += maze[curY][curX];
            maze[curY][curX] = 0;
        }
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (tmp[i][j] != 0) maze[i][j] += tmp[i][j];
        }
    }
}

bool isAllEmpty() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (-10 <= maze[i][j] && maze[i][j] <= -1) return false;
        }
    }
    return true;
}

int main() {
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> maze[i][j];
        }
    }

    for (int i = 0; i < M; i++) {
        int y, x;
        cin >> y >> x;
        maze[y][x] -= 1;
    }

    cin >> exitY >> exitX;
    maze[exitY][exitX] = -11;

    while (K--) {
        if (isAllEmpty()) break;
        move();
        tuple<int, int, int> pointWithSize = findSmallSqure();
        rotate(pointWithSize);
    }

    cout << totalDis << "\n";
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (maze[i][j] == -11) cout << i << " " << j;
        }
    }
    return 0;
}

https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration?&utm_source=clipboard&utm_medium=text

문제 로직

1. 골렘이 남쪽으로 갈 수 있을 때까지 내려간다.
2. 골렘이 왼쪽 그리고 왼쪽 아래쪽으로 갈수있다면 왼쪽으로 구른다.
3. 왼쪽으로 가지 못한다면, 골렘이 오른쪽 그리고 오른쪽 아래쪽으로 갈 수 있다면 오른쪽으로 구른다.
4. 아래, 왼쪽 & 왼쪽아래, 오른쪽 & 오른쪽아래 세곳 모두 움직이지 못한다면 골렘의 숲을 탐색한다.

계속되는 실수

구른 뒤 중력을 생각했어야지

문제를 잘못 이해해서 왼쪽으로 구른다는 것을 골렘의 현재 위치 (y,x) -> 구른 뒤 위치 (y+1,x-1) 로 이해했다.

여기서 중요한 점은 (y,x) -> (y+1, x-1) 이 아닌 (y+n, x-1) ( n : 아래쪽으로 내려갈 수 있는 최대 값) 이라는 것이다.

계속 왼쪽한칸 아래한칸 만 움직이니 답이 제대로 나올리가 없었다.

애매한 위치 저장 방법

기존 코드는 탈출구 저장을 이상하게 했다. 탐색하고자 하는 위치를 기준으로 4방향 중 음수인 값이 탈출구이므로 그때 방향을 알게되는 것.

이렇게 되면 방향을 잘못 설정할 수 가 있다는 것이다. 따라서, 나는 Golem 이라는 구조체하나를 생성해서 방향 관리를 하게 되었다.

정답 코드

int main() {
    // 여기에 코드를 작성해주세요.

    cin >> R >> C >> K;
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int sRow, dir;
        cin >> sRow >> dir;
        //인덱스 0 으로 맞추기위한 빼기
        //0 북 1 동 2 남 3 서
        sRow -= 1;

        int curY = 1;
        int curX = sRow;

        Golem golem;
        golem.num = i + 1;
        golem.y = curY;
        golem.x = curX;
        golem.dir = dir;

        while (canMoveDown(golem)) {}

        while(canMoveRL(golem)){}

        if (isFull()) {
            fill(&map[0][0], &map[0][0] + 80 * 80, 0);
        }
        else {
            ans += bfs(golem);
        }
    }
    cout << ans;
    return 0;
}

1. 골렘의 생성위치와 골렘의 번호 및 방향을 붙여 관리
2. 해당 골렘이 canMoveDown을 통해 밑으로 갈 수 있을 만큼 가고
3. canMoveRL 을 통해 왼쪽으로 오른쪽으로 구를 수 있을만큼 구른 후
4. 위치한 골렘이 맵을 벗어나면 초기화하거나
5. 그렇지않다면 골렘의 숲을 탐색한다.

개선점

canMoveDown 과 canMoveRL을 지금보면 합칠 수 있을 것 같다. 하지만, 귀찮아서 나중에할래 ㅎㅎ

전체 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include<queue>
using namespace std;

int R, C, K;
int map[80][80];

struct Golem {
    int y, x;
    int num;
    int dir;
};

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

bool oob(int y, int x) {
    return y < 0 || x < 0 || y >= R + 3 || x >= C;
}

void print() {
    for (int i = 0; i < R + 3; i++) {
        for (int j = 0; j < C; j++) {
            cout << map[i][j] << "  ";
        }
        cout << "\n";
    }
}
void clearMap(int y, int x) {
    map[y][x] = 0;
    for (int d = 0; d < 4; d++) {
        int ny = y + dy[d];
        int nx = x + dx[d];
        map[ny][nx] = 0;
    }
}

bool canMove(Golem &golem, int ey, int ex) {

    //초기위치 초기화
    clearMap(golem.y, golem.x);

    //다음 움직일 곳으로 갈수 있는지?
    for (int d = 0; d < 4; d++) {
        int ny = ey + dy[d];
        int nx = ex + dx[d];

        if (map[ny][nx] != 0 || oob(ny, nx)) {
            int sy = golem.y; int sx = golem.x;
            map[sy][sx] = golem.num;
            for (int dd = 0; dd < 4; dd++) {
                int nny = sy + dy[dd];
                int nnx = sx + dx[dd];
                map[nny][nnx] = golem.num;
            }
            map[sy + dy[golem.dir]][sx + dx[golem.dir]] = golem.num * -1;
            return false;
        }
    }

    // 움직일 수 있따면
    int sy = golem.y; int sx = golem.x;
    map[sy][sx] = golem.num;
    for (int dd = 0; dd < 4; dd++) {
        int nny = sy + dy[dd];
        int nnx = sx + dx[dd];
        map[nny][nnx] = golem.num;
    }
    map[sy + dy[golem.dir]][sx + dx[golem.dir]] = golem.num * -1;
    return true;
}

void setMap(Golem & golem,int lr) {
    //cout << "setMap " << ey << ex << num<<"\n";
    clearMap(golem.y, golem.x);

    if (lr == 1) {//right
        golem.dir = (golem.dir + 1) % 4;
        golem.x += 1;
        golem.y += 1;
    }
    else if (lr == 2) { golem.dir = (golem.dir + 3) % 4; 
    golem.x -= 1;
    golem.y += 1;
    }
    else if(lr == 0) {
        golem.y += 1;
    }
    else if (lr == -1) {

    }


    int ey = golem.y;
    int ex = golem.x;

    //움직이고자 하는 위치에 맵 저장
    map[ey][ex] = golem.num;
    for (int dir = 0; dir < 4; dir++) {
        int ny = ey + dy[dir];
        int nx = ex + dx[dir];
        map[ny][nx] = golem.num;
    }
    map[ey + dy[golem.dir]][ex + dx[golem.dir]] = golem.num * -1;

}
bool canMoveDown(Golem &golem) {
    int dy = golem.y + 1;
    int dx = golem.x;

    if (canMove(golem,  dy, dx)) {
        setMap(golem, 0);
        return true;
    }

    return false;
}

bool canMoveRL(Golem &golem) {


    //현재 위치에서 오른쪽 왼쪽 갈수있는지

    int y = golem.y;
    int x = golem.x;


    int ly = y;
    int lx = x - 1;
    while (canMoveDown(golem)) {}

    if (canMove(golem, ly, lx) && canMove(golem, ly + 1, lx)) {
        setMap(golem, 2);
        while (canMoveDown(golem)) {}
        //cout << "move left\n";
        return true;
    }

    setMap(golem,-1);

    //move right
    int ry = y;
    int rx = x + 1;

    if (canMove(golem, ry, rx) && canMove(golem, ry + 1, rx)) {
        setMap(golem, 1);
        while (canMoveDown(golem)) {}
        //cout << "move right\n";
        return true;
    }
    setMap(golem,-1);
    return false;
}


bool isFull() {
    for (int i = 0; i < C; i++) {
        if (map[2][i] != 0) {
            return true;
        }
    }
    return false;
}

int bfs(Golem &golem) {
    queue<pair<int, int>> q;
    int maxDepth = 0;
    q.push({ golem.y, golem.x });
    bool v[80][80];
    fill(&v[0][0], &v[0][0] + 80 * 80, false);
    v[golem.y][golem.x] = true;

    //print();
    while (!q.empty()) {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        for (int d = 0; d < 4; d++) {
            int ny = yy + dy[d];
            int nx = xx + dx[d];
            if (oob(ny, nx) || v[ny][nx])continue;
            if (map[ny][nx] == 0)continue;
            if (map[yy][xx] > 0) {
                if (map[ny][nx] > 0) {
                    if (map[ny][nx] != map[yy][xx])continue;
                }
                else if (map[ny][nx] < 0) {
                    if (map[ny][nx] != -1 * map[yy][xx])continue;
                }
                //cout << yy << " " << xx << " " << map[ny][nx] << "-\n";
                q.push({ ny,nx });
                v[ny][nx] = true;
                maxDepth = max(maxDepth, ny);
            }
            else if (map[yy][xx] < 0) {
                //cout << yy << " " << xx << " " << map[yy][xx] << " " << map[ny][nx] << "-\n";
                q.push({ ny,nx });
                v[ny][nx] = true;
                maxDepth = max(maxDepth, ny);
            }
        }
    }
    //cout << "값 : " << maxDepth - 2 <<"\n";
    return maxDepth - 2;
}


int main() {
    // 여기에 코드를 작성해주세요.

    cin >> R >> C >> K;
    int ans = 0;
    for (int i = 0; i < K; i++) {
        int sRow, dir;
        cin >> sRow >> dir;
        //인덱스 0 으로 맞추기위한 빼기
        //0 북 1 동 2 남 3 서
        sRow -= 1;

        int curY = 1;
        int curX = sRow;

        Golem golem;
        golem.num = i + 1;
        golem.y = curY;
        golem.x = curX;
        golem.dir = dir;

        while (canMoveDown(golem)) {}

        while(canMoveRL(golem)){}

        if (isFull()) {
            fill(&map[0][0], &map[0][0] + 80 * 80, 0);
        }
        else {
            ans += bfs(golem);
        }
    }
    cout << ans;
    return 0;
}

나의 스펙

• 서울 중위권
• 학점 : 3.9
• 프로젝트 경험 : 웹 2, 앱 2, 임베디드 1
• 어학 : 오픽 IH
• 자격증 : none
• 인턴 : none,,

배경

졸업 준비를 하면서 아직 신입 개발자가 되기까지 경험이 부족하다고 생각했고 마침 11기 모집을 하기에 싸피에 지원하게 되었다. 싸피 지원 프로세스는 총 3가지로 나뉜다.

진행방법

1. 지원서 및 에세이 작성
2. SW적성진단
3. 인터뷰

3가지 순서로 11기 모집을 한다.

지원서 및 에세이 작성

일반적인 회사 공고 자기소개서와는 달리 교육을 목적으로 하는 기관에서의 자기소개이기 때문에 내가 왜 싸피를 들어야하는가? 싸피가 왜 필요한가? 에 대한 고민이 필요한 것 같다. 따라서, 에세이에 싸피가 꼭 필요한 이유 등 어필할 수 있는 내용으로 채워야 한다고 생각한다.

질문 향후 어떤 SW 개발자로 성장하고 싶은지 SW 관련 경험을 토대로 기술하고, SSAFY에 지원하신 동기에 대해서도 작성 바랍니다.

에세이는

• 경험의 부재
• 싸피가 가져오는 이점

위 두 항목을 기준으로 작성했다.

SW적성진단

전공자 입장에서 SW적성진단은 코딩테스트를 치룬다. 비전공자들은 GSAT 같은 시험을 봤다고하는데 정확하지는 않다. 코딩테스트는 꾸준히 문제를 풀어보고 대중적인 알고리즘에 대한 기본 문제를 쉽게 풀 수 있다면 무리없이 통과할 수 있다.

플랫폼은 SWEA 에서 보기때문에 SWEA 에서 제공하는 D1~D3 문제들을 풀어가며 준비를 했다.

위와 같이 준비한 덕분에 코딩테스트는 무난하게 통과했다.

인터뷰

인터뷰 대상자가 되면서 제일 먼저 한 일은 스터디를 찾는 것이었다. 면접 및 PT 에 대해서는 1도 준비한 적이 없었기 때문에 혼자 준비하기가 힘들었고, 또 내 개인적인 특성상 강제력 없이는 준비를 잘 안하기 때문에 환경을 조성하기 위해서라도 하려고 했다.

인터뷰 준비기간이 되면 오픈채팅방이 하나 생긴다. 그 오픈채팅방에 들어가면 여러 사람들이 면접스터디를 구한다. 거기서 두 개의 면접 스터디를 진행했다.

면접 스터디를 진행하면서 주로 PT 에 대해 많이 준비했던 것 같다. 어떤식으로 면접이 진행될지 몰라 구글링을 통해 IT 뉴스를 읽고 내용에 대해 서술하는 방식으로 진행했다. 그리고 다양한 IT 키워드에 대해 개념을 준비했다.

면접 준비는 인성 면접으로 준비했고, 에세이에서 질문할 만한 질문리스트를 만들거나 흔히 알려져있는 인성면접 질문 리스트를 이용했다.

인성 관련

1. 성격의 장단점
2. 개발자가 되고 싶은 이유
3. 어떤 개발자가 되고 싶은지
4. 본인은 리더인지 팔로워인지
5. 팀을 위해 희생한 경험
6. 최종적으로 원하는 직무
7. 실패나 어려움을 겪고 극복한 사례 / 도전정신이 드러나는 사례
8. 본인의 경쟁력
9. 마지막으로 할 말
10. 개발 동아리 / 관련 프로그램을 하시면서 힘들었던 적이 있다면 말씀해주세요
11. 책임자로써 팀원간의 불화가 있을 때 어떻게 대처할 것인가요?
12. 협업을 해본 경험이 있나요?
13. 최근에 읽은 IT 기사를 소개해주세요
14. 현재 본인의 전공을 선택한 계기가 무엇인가요?
15. 취업을 하기에 부족하다고 느끼는 이유가 무엇인가요
16. 팀플을 진행하면서 어려웠던 점이 있나요?
17. 추후에 개발자가 되었을 때 어떠한 프로그램을 개발하고 싶으신지?

또, 프로젝트 질문도 나올 것 같아 프로젝트에 대한 질문도 준비해 갔다.

프로젝트 관련

1. 프로젝트 내 역활
2. 개발 과정
3. 사용기술과 선택 이유
4. 프로젝트 진행 중 겪은 갈등 상황과 해결 방법
5. (에세이에 작성한) (’’’) 프로젝트가 무엇인가요?
6. (에세이에 작성한) (’’’) 프로젝트를 진행하면서 본인이 주도한 역할을 위주로 말씀해주세요.
7. 프로젝트를 진행하며 기술적인 어려움을 겪은 적이 있었나요? 어떻게 해결했나요?
8. 기재한 프로젝트 동작과정에 대해 말씀해주세요

인터뷰 후기

결과는 불합격..

면접은 괜찮게 봤다고 생각했지만 역시 진리의 면까몰,, 좀 슬프긴했지만 다음날 인턴 면접이 잡혀있어 정신이 없었다..
하지만, 다음날 면접 준비할때도 30분에 한번씩 결과를 다시 보면서 현실을 부정하기 반복이었다.. ㅋ

추가합격이 될거라는 희망을 가지고 기다려보았지만 기회는 없었다. 두개의 면접스터디를 하면서 70%의 스터디원들은 합격한 것 같다. 축하드린다.. 더 열심히 해서 취업 혹은 소프트웨어 마에스트로에 합격하고 싶다..