1월

• 알고리즘 공부 (1일 1커밋의 시작)
• 삼성SDS 알고리즘 특강 수강

2월

• 정보처리기사 필기 공부
• SQLD 공부

3월

• 코로나 걸림 😷
• 정보처리기사 필기 공부 및 합격
• SQLD 공부 및 합격
• 토익스피킹 레벨6 취득

4월

• 정보처리기사 실기 공부
• SQLD 취득

5월

• 정보처리기사 실기 공부
• GSAT 준비 (SCSA 시험)

6월

• 삼성SDS 면접 준비
• 정보처리기사 취득
• 삼성SDS 최종탈락: 이로 인해 하반기 취준까지 하게 됩니다.. 🥲

7월

• SSAFY 8기 입과, 대전 자취 시작

8~10월

• SSAFY 과정 몰두
• 꾸준히 입사 지원

11월

• SSAFY 파이널 프로젝트 진행
• 국민은행 외 2개 기업 1차 면접

12월

• 국민은행 외 2개 기업 최종 면접
• ⭐️ 국민은행 외 1개 기업 최종합격 ⭐️

총결산

상반기

서류 지원 39개 서류 합격 6개 (현대오토에버, KT, 삼성SDS, CJ ENM, BGF네트웍스, SSAFY) 인적성 합격 1개 (삼성SDS) 코테 합격 1개 (SSAFY) - 코테 준비가 아예 안되어 있긴 했지만 정말 처참하다 😂 면접 합격 0개 (SSAFY는 추가합격)

하반기

서류 지원 22개 서류 합격 6개 (삼성SDS, 우리FIS, CJ 올리브네트웍스, kt ds, 국민은행, 카카오뱅크) 코딩테스트 합격 3개 면접 합격 2개

2022

1일 1커밋을 꾸준히 하다가 SSAFY 입과 후 초반에 정신없이 지내며 다소 주춤했다. 이후 SSAFY에서 다시 문제풀이를 시작하며 본격적으로 알고리즘 역량을 쌓았다. 덕분에 코딩테스트 합격률이 정말 처참했는데 많이 증가했다. (떨어진 것도 풀기는 다 풀었다... 크흡) 열심히 살았다 증말..~!

새해에 썼던 다짐인데, 다행히 지키게 되었다. 이렇게 취준일기를 마무리하고자 한다 🙂 영원히 끝나지 않을 줄 알았는데... 취준은 정말 99패를 하더라도 1승만 하면 된다는 것을 몸소 깨달았다.

이제 내년부터는 국민은행의 개발자로 근무하게 되었다. 어제부터 연수를 시작했는데 아직도 실감이 안 난다. ㅎㅎㅎ 당분간은 업무를 배우는 데 집중하겠지만, 진행하고 있던 토이프로젝트도 계속 참여하고, 개발 공부도 꾸준히 할 예정이다. 다음에는 기술 관련 포스팅으로 찾아뵙고자 한다. :)

그동안 고생했다 나 자신~ 🥰

2022년 7월, SSAFY(삼성 청년 SW 아카데미) 8기에 합격하였다. 9기 모집 소식을 들을때부터 합격후기를 남기고 싶었지만 현생에 밀리고 밀려 이제서야 후기를 쓰게 되었다. 어느덧 2022년의 끝에 다다랐고 이제 최종 발표까지 난 걸로 알아서, 당장 도움은 안되겠지만 미래 10기들을 위해ㅎㅎ(머쓱), 그리고 1학기를 수료하고 느낀점 위주로 작성해 보고자 한다.

필자의 지원 당시 상태

• 컴퓨터공학과를 복수전공하였기에, 전공/비전공 둘 다 선택이 가능했음
• 7기를 비전공자반으로 지원했다가, 에세이 및 적성진단 분야에서 불합격함
• 알고리즘은 solved 기준으로 티어 실버 초중반정도였던 걸로 기억함 (bfs, dfs도 개념만 알지, 문제 풀이는 못했던 수준)

에세이

지원동기, 향후 어떤 개발자로 성장하고 싶은지 SW관련경험 토대로 작성할 것(관련학습, 관련자격증, 교내외 플젝경험, 서비스사용경험, 관련기사구독 및 영상시청 등)

내가 지원할때 당시 문항은 위와 같았는데, 7기 때도 똑같았고... 9기도 비슷한 걸로 알고 있다. 아이러니하게도 7기 당시에는 에세이에 정말 많은 심혈을 기울였으며 SSAFY 오픈카톡방에서도 많은 첨삭을 받았으나 떨어졌고, 8기는 마감 1시간 전에 혼자서 급하게 적어서 냈는데 붙었다. 여기서 내가 느낀 점은 2가지이다.

• SSAFY는 교육기관이다. 나의 경험을 자랑하는 게 아니라, 나에게 왜 교육이 필요한지에 대해 납득시켜야 한다. 따라서 잘하는 점만 내세우지 않고, 부족한 점을 인정하며 어떤 식으로 성장하고 싶은지에 대해 서술하는 것이 좋다.
• 평소에 자소서 쓰는 습관을 들이자. SSAFY가 첫 자소서라면 많은 시간을 쏟고 최대한 많은 사람에게 첨삭을 받는 게 맞다. 하지만, 시간이 최고의 무기이다..! 최대한 많이 입사 지원을 해보며 자소서를 작성하게 되면 점점 자소서가 다듬어지고 최종적인 형태로 완성된다. 그렇기에 필자가 1시간 만에 작성한 8기 자소서가 7기 때보다 더 좋은 평가를 받을 수 있었다고 생각한다. (내가 보기에도 8기 자소서가 훨씬 나았음)

이 두가지만 잘 생각하며 자소서를 쓴다면 에세이에는 큰 문제가 없을 것이다.

적성진단

다음으로는 7기에서 비전공, 8기에서 전공으로 지원했던 경험을 토대로 두가지 적성진단고사에 대한 의견을 적어보려 한다.

비전공 (수추리, CT)

지삿 하위호환버전의 수리/추리 문제와, Computational Thinking 문제(이하 컴띵)가 나온다. 준비는 그때당시 해커스 GSAT 파랑이랑 하양이로 했는데 그정도면 충분하다. 요즘은 싸피 전용 문제집도 많이 나오는걸로 알고 있는데 그걸 봐도 좋을 듯 하다. 컴띵은 알고리즘잡스에서 제공해주는 유튜브 '무료' 영상, 백준 문제 코딩 안하고 풀기 정도로 준비하면 될 것 같다. 돈을 주고 싸피특별반 등에 들어가는 건 절대비추! 그정도로 안 해도 된다. 비전공 시험은 사실 7기 지원 때 본거라 잘 기억은 안나지만,,, 긴장되는데 문제수가 너무 많아서, 긴장을 많이 하는 나에게는 최악이었다 ㅎㅎ 포스팅 하단에 따로 적을 거지만, 비전공/전공 선택할 수 있으면 정말이지 무족권...! 전공반으로 넣는 걸 추천한다. 그 이유는.....!!!

전공 (코딩테스트)

코딩테스트가 정말 쉬운 편이다. 필자가 코딩테스트 볼 때는 체감난이도 브론즈 한문제, 골드 한문제 정도로 나왔다. 그래서 브론즈 하나 풀고, 골드는 당시 풀지못했는데 합격했다,,, ㅎㅎㅎㅎ 9기에서 조금 어려워졌다고는 들었다만, 2문제 중 1문제만 풀면 거의 합격선이기 때문에 큰 문제 없을 것이다.

인터뷰

인터뷰는 pt면접을 준비해 가야 한다. 말해뭐해... pt면접 바이블 하나 첨부한다. https://youtu.be/DOvCIrwMPbQ (강민혁 강사님 짱 👍) 면접스터디를 하면 좋긴 한데 안해도 할만하다. 필자는 취업준비때문에 바빠서 스터디 안하고 혼자 준비했다. (다른 기업 면접 경험이 있기도 했다) 4차산업혁명 기술에 대한 IT뉴스 많이 보고, 위 유튜브 보며 아이템 하나씩 준비해가면 된다. ai, 블록체인, 클라우드, 빅데이터에 대한 아이템 하나씩 챙겨가기! 그리고 PT발표도 중요하기야 하겠지만, 내가 왜 SSAFY가 필요한지를 어필하는게 가장 중요하다고 생각한다. 어떤 면접이든 가장 중요한건 로열티..!!

전공? 비전공?

전공, 비전공 선택이 모두 가능할 경우 무조건!!! 전공반을 선택하는 것을 강력추천한다. 다음과 같은 이유 때문이다.

1. 코딩테스트를 아예 준비해본 경험이 없다고 해도 2주~1달 정도의 준비시간이 있는 걸로 아는데, 그 기간동안 집중적으로 준비한다면 1문제는 충분히 풀 수 있을 것이다.
2. SSAFY를 준비하는 것은 결국 개발자를 목표로 하는 것이기 때문에, 앞으로의 취업 준비 과정과 거의 관련이 없는 적성고사 준비보다는 코딩테스트를 준비하는 게 더 효율이 높다고 생각이 든다.
3. 개인적인 체감상 전공반이 비전공반보다 추가합격이 훨~~씬 많이 돈다.

이러한 이유들로 둘 다 선택이 가능하면 전공으로 선택하길 추천한다.

추가합격

필자는 추가합격을 통해 SSAFY에 입과하게 되었다. 추가합격은 최종발표 후부터 스타트캠프 끝나기 전까지 도는 걸로 알고있다. 스타트캠프는 아마 공식적인 시작 후 일주일동안 이뤄졌던 것 같은데 확실히는 기억이 안난다.. 😅 필자는 스타트캠프 딱 끝나고 들어와 바로 정규수업에 참여하게 되었고, 그 기간동안 쫄리긴 했지만 타이밍 상으로는 정말 좋았던 것 같다 ㅎㅎㅎ (스타트캠프가 정말 괴롭다는 소문이) 추가합격 결과는 전화로 오는데, 계속 못받다가 3번째에 받았던 기억이 난다. 굉장히 자비로운 편이기 때문에 전화 한 통에 너무 조급해하지 않아도 된다.

그렇지만! 추가합격만을 기다리며 아무것도 하지 않는 것은 추천하지 않는다. 추가합격은 말 그대로 추가적으로 주어지는 기회이기 때문에 최종 합격보다는 확률이 높지 않다. 적은 확률에 모든 걸 걸지 않고 자신의 할 일을 하다가, 기회가 찾아온다면 잡는 걸로 하자 :)

1학기 수료 후 느낀 점 (+중도퇴소)

이렇게 소중한 기회를 받아 입과하였지만, 필자는 1학기 수료 후 취업을 하게 되어 중도퇴소하였다. 정말 재밌는게, 들어가기 전까지는 모두가 간절하게 입과를 희망하지만 입과 후에는 모두가 간절하게 퇴소를 희망한다 ㅋㅋㅋㅋㅋ 화장실 들어갈때랑 나올때 다르다더니 🤪 이를 흔히 '싸탈'이라고 하는데, 결국 우리의 최종 목표는 취업이고, SSAFY 또한 적극적으로 지원을 하며 취업을 바라고 있기 때문에 나쁜 건 절대 아니다 ㅎㅎ

1학기는 java, 백엔드, 프론트엔드, 알고리즘 등의 개발 역량을 쌓을 수 있는 교육을 듣고 2학기는 반 사람들과 팀을 짜서 프로젝트를 진행하게 된다. 2학기는 경험하지 못했지만, 1학기를 수료하고 느낀 점은... 당연한 말일 수도 있지만 '열심히 한 만큼 얻어간다' 라는 것이다. 필자는 알고리즘을 배우는 주간에 알고리즘에 큰 재미를 느끼고 정말 많은 문제를 풀었다. 어느덧 상위 100문제가 모두 골드 문제로 채워졌고 티어는 골드1까지 올라갔다. 플레문제를 한문제도 풀지 못한건 아쉽지만,,, 웬만한 기업의 코딩테스트를 보면서 불합격보다 합격하는 경우가 점점 더 많아졌고, 덕분에 좋은 결실을 맺었다 ㅎㅎ 이후 다른 과목을 들을때도 열심히 참여하지 않은 건 아니지만, 알고리즘 주간에 가장 열심히 했던 건 분명한 사실이다. 그리고 내가 가장 많이 얻어간 것 또한 알고리즘이다. 오히려 알고리즘에 너무 힘을 쏟아서 알고리즘이 끝나자 다른 과목에는 그만큼 불태울 수 없었던 것 같기도 하다. 그래서 필자가 SSAFY 과정에서 당부하고 싶은 내용은 다음과 같다.

1. SSAFY는 장기전임을 잊지 말고 템포관리하기. 또는, 자신이 필요한 분야를 특히 집중적으로 선택과 집중 하기
2. 결국 목표는 취업이기 때문에, SSAFY과정에만 집중하지 않고 스터디 등 취약분야도 함께 준비하기
3. 열심히 한만큼 얻어가기 때문에 6개월 동안 죽었다고 생각하고 최선을 다하기
4. 본인이 준비가 덜 됐다고 생각되더라도 입사 지원도 꾸준히 하기

1번과 3번이 상충된다고 느낄 수도 있겠지만,, 본인이 할 수 있는 최선을 다 하는 상태에서 템포관리를 하라고 말하고 싶다! SSAFY를 하는 기간이 결코 짧은 기간이 아니니 최대한 노력해서 많은 걸 얻어갔으면 하는 마음이다. 그리고 아무리 준비가 부족하다고 느껴도 입사지원을 꾸준히 했으면 한다. 자소서든 코테는 면접이든 하면 할수록 늘고, 그러다 보면 좋은 기회가 생길 수도 있다 😚 (저처럼,,)

마무리

쓰다 보니 굉장히 길어졌다. 이 글을 읽는 모두가 싸피에 입과하고, 또 싸탈할 수 있었으면 좋겠다 ㅎㅎ 요즘 취업난이나 뭐다 말이 많지만 늘 들리는 말이고,, 또 열심히 하는 사람들에게는 해당되지 않는 말이라고 생각한다! 여기까지 읽으신 분 모두 좋은 기운이 가득하길! 🔥

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

풀이

BFS를 두번 하면 풀린다. 다음과 같은 2단계로 나눠서 풀었다.

1. 섬 파악하기 (현재 섬과 다른 섬을 연결해야 함 -> 111 222 333 으로 구분하자)
2. 섬 사이에 다리 다 놓아보면서 최소거리 구하기 (1 기준으로 2, 3, 4, && 2 기준으로 3, 4 , ...)

   import java.io.BufferedReader;
   import java.io.FileInputStream;
   import java.io.IOException;
   import java.io.InputStreamReader;
   import java.util.LinkedList;
   import java.util.Queue;
   import java.util.StringTokenizer;
   

public class Boj2146 { static class Bridge { int r, c, dist;

    public Bridge(int r, int c, int dist) {
        this.r = r;
        this.c = c;
        this.dist = dist;
    }
}
static int n, islands, minBridge;
static int[][] map;
static boolean[][] vis;
static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("src/input.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    n = Integer.parseInt(br.readLine());
    map = new int[n][n];

    for (int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < n; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    // 섬 파악하고 카운팅하기
    islands = 1;
    vis = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!vis[i][j] && map[i][j] == 1) {
                findIsland(i, j);
            }
        }
    }

    // 섬 사이에 다리 다 놔보면서 최소거리 구하기
    minBridge = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] > 0) {
                bridgeTest(i, j);
            }
        }
    }

    System.out.println(minBridge);
}

// 섬 사이에 다리 다 놔보면서 최소거리 구하는 메서드
static void bridgeTest(int r, int c) {
    vis = new boolean[n][n];

    Queue<Bridge> q = new LinkedList<>();
    q.add(new Bridge(r, c, 0));
    vis[r][c] = true;

    while (!q.isEmpty()) {
        Bridge now = q.poll();
        int row = now.r;
        int col = now.c;
        int dist = now.dist;

        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                if (!vis[nr][nc]) {
                    if (map[nr][nc] == 0) {
                        q.add(new Bridge(nr, nc, dist + 1));
                        vis[nr][nc] = true;
                    }
                    else if (map[nr][nc] > map[r][c]) {
                        minBridge = Math.min(minBridge, dist);
                        return; // 어차피 처음 도달한 값이 최솟값
                    }
                }
            }
        }

    }
}

// 섬을 파악하고 구분짓는 메서드
static void findIsland(int r, int c) {
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[] {r, c});
    vis[r][c] = true;
    map[r][c] = islands;

    while (!q.isEmpty()) {
        int[] now = q.poll();
        int row = now[0];
        int col = now[1];

        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = col + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                if (!vis[nr][nc] && map[nr][nc] == 1) {
                    q.add(new int[] {nr, nc});
                    vis[nr][nc] = true;
                    map[nr][nc] = islands;
                }
            }
        }

    }

    islands++;
}

static void print(int[][] map) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.print(map[i][j] + " ");
        }
        System.out.println();
    }
    System.out.println("---------------");
}

}

```

분명 맞게는 풀었는데, 코드가 돌아가는 시간이 너무 오래 걸렸다. 시간 초과는 아니지만 시간을 줄이고 싶어서 여러 방법을 알아보았고 BFS로 구한다면 어차피 가장 먼저 도착한 경우가 그 상황에서의 최단거리이기 때문에 최솟값을 갱신하고 바로 return하면 된다는 사실을 알게되었다!

그렇게 처리해준 결과 시간이 1/5 가량으로 줄어들었다. 최단경로를 구해주는 BFS 알고리즘인만큼 효율적으로 사용하도록 노력해야겠다.

🚨 실력이 뛰어나지 않아 코드가 다소 지저분할 수 있습니다! 🚨

문제

삼성에서 개발한 최신 모바일 프로세서 멕시노스는 가로 N개 x 세로 N개의 cell로 구성되어 있다.

1개의 cell에는 1개의 Core 혹은 1개의 전선이 올 수 있다.

멕시노스의 가장 자리에는 전원이 흐르고 있다.

Core와 전원을 연결하는 전선은 직선으로만 설치가 가능하며,

전선은 절대로 교차해서는 안 된다.

초기 상태로는 아래와 같이 전선을 연결하기 전 상태의 멕시노스 정보가 주어진다.

(멕시노스의 가장자리에 위치한 Core는 이미 전원이 연결된 것으로 간주한다.)

최대한 많은 Core에 전원을 연결하였을 경우, 전선 길이의 합을 구하고자 한다.

단, 여러 방법이 있을 경우, 전선 길이의 합이 최소가 되는 값을 구하라.

위 예제의 정답은 12가 된다.

제약 사항

1. 7 ≤ N ≤ 12

2. Core의 개수는 최소 1개 이상 12개 이하이다.

3. 최대한 많은 Core에 전원을 연결해도, 전원이 연결되지 않는 Core가 존재할 수 있다.

입력

입력의 가장 첫 줄에는 총 테스트 케이스의 개수 T가 주어지며 그 다음 줄부터 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 N값이 주어지며, 다음 N줄에 걸쳐서 멕시노스의 초기 상태가 N x N 배열로 주어진다.

0은 빈 cell을 의미하며, 1은 core를 의미하고, 그 외의 숫자는 주어지지 않는다.

출력

각 테스트 케이스마다 '#X'를 찍고, 한 칸 띄고, 정답을 출력한다.

(X는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

풀이

문제를 잘 이해하고 주어진 조건대로 차근차근 구현한다면 크게 어렵진 않다. 다만 까다로운 부분이 꽤 있는 편이다.

• 가능한 경우의 전선은 모두 배치해보는 백트래킹으로 문제를 풀었다.
• 코어가 최대로 많을 때의 최소 전선 길이를 구해야 한다. 즉, 전선 길이는 더 길더라도, 연결한 코어가 더 많다면 새로 갱신해야 한다.
• 코어의 크기가 같다면 전선의 최소 길이를 갱신한다.
• 테두리에 닿아있는 코어는 전선을 연결하지 않아도 이미 연결된 상태이기 때문에 넘어간다.
• 많은 백트래킹이 일어나기 때문에 방문체크에 유의한다. (전선 깔고, 되돌리는 과정)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Swea1767 {
    static int n, maxCore, minLine;
    static int[][] map;
    static ArrayList<int[]> cores;
    static int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
    /*
    가장자리의 코어는 이미 연결된 상태
    '최대'한 많은 코어를 연결했을 때의 '최소' 전선 길이를 구하자.
     */
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= t; tc++) {
            n = Integer.parseInt(br.readLine());
            map = new int[n][n];
            cores = new ArrayList<>();

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 1) cores.add(new int[] {i, j});
                }
            }

            maxCore = Integer.MIN_VALUE;
            minLine = Integer.MAX_VALUE;
            check(0, 0, 0);

            sb.append("#").append(tc).append(" ");
            sb.append(minLine).append("\n");
        }
        System.out.println(sb);
    }

    /*
    1. 맨 위, 왼쪽부터 보며 1일 경우 전선을 연결해본다.
    1-1. 코어가 0행 || n-1행 || 0열 || n-1열 일 경우 바로 다음 코어로 넘어간다. (전체 코어에 더하고 -> 일단생략)
    2. 상하좌우 가능한 방법으로 모두 수행해 본 후 가능할 경우 다음 코어로 백트래킹
    3. 마지막 코어까지 연결을 마치면, 전체 코어 개수를 확인하고, 최댓값을 갱신한다.
    4. 만약 현재 코어수가 최댓값이라면, 거리의 최솟값을 갱신한다.
     */

    static void check(int idx, int coreCnt, int lineCnt) {
        // 3. 마지막 코어까지 연결을 마치면,
        if (idx == cores.size()) {
            // 3-1. 전체 코어 개수를 확인하고, 최댓값을 갱신한다.
            if (coreCnt > maxCore) {
                maxCore = coreCnt;
                minLine = lineCnt;
            }
            // 4. 만약 현재 코어수가 최댓값이라면, 거리의 최솟값을 갱신한다.
            else if (coreCnt == maxCore) {
                minLine = Math.min(minLine, lineCnt);
            }
            return;
        }

        // 1. 맨 위, 왼쪽부터 보며 1일 경우를 살펴본다.
        int[] core = cores.get(idx);
        int r = core[0];
        int c = core[1];

        // 1-1. 현재 코어가 테투리와 닿아 있다면, 다음 코어로 넘어간다.
        if (r == 0 || c == 0 || r == n - 1 || c == n - 1) {
            check(idx + 1, coreCnt, lineCnt);
        }
        // 1-2. 닿아있지 않다면, 상하좌우 탐색 진행
        else {
            for (int i = 0; i < 4; i++) {

                boolean flag = false;
                int cnt = 0;

                int curR = r, curC = c;
                int nr, nc;
                while (true) {
                    nr = curR + dr[i];
                    nc = curC + dc[i];

                    // 테두리에 닿으면 좋료
                    if (nc < 0 || nc >= n || nr < 0 || nr >= n) break;

                    // 빈칸이면 전선 놓기
                    if (map[nr][nc] == 0) {
                        map[nr][nc] = 2;
                        cnt++;
                    }
                    // 코어가 있거나, 전선이 있다면 더이상 탐색할 필요 없다
                    else {
                        flag = true;
                        break;
                    }

                    curR = nr; curC = nc;
                }

                // 코어, 전선과 마주치지 않고 무사히 탐색을 끝냈다면, 카운트를 추가해서 다음값으로 넘겨준다
                if (!flag) {
                    check(idx + 1, coreCnt + 1, lineCnt + cnt);
                    rollback(nr - dr[i], nc - dc[i], i); // 되돌리기
                }
                // 코어, 전선과 마주쳤다면, 깔았던 전선을 모두 회수한 후 다음 값으로 넘어간다
                else {
                    rollback(nr - dr[i], nc - dc[i], i); // 되돌리기
                    check(idx + 1, coreCnt, lineCnt);
                }
            }
        }
    }

    // 되돌리기
    static void rollback(int nr, int nc, int i) {
        while (map[nr][nc] == 2) {
            map[nr][nc] = 0;
            nr -= dr[i];
            nc -= dc[i];
        }
    }
}

구현+백트래킹 문제는 정말 번거롭긴 하지만 풀고 나면 정말 뿌듯하다 ㅎㅎ 시간초과에 대한 개념이 아직 부족해서 시간초과가 날까 걱정했는데 다행히 통과했다. 시간초과는 어느 경우에 일어나는지도 알아봐야겠다.

🚨 실력이 뛰어나지 않아 코드가 다소 지저분할 수 있습니다! 🚨

문제

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다. 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 아기 상어의 이동은 1초 걸리고, 물고기를 먹는데 걸리는 시간은 없다고 가정한다. 즉, 아기 상어가 먹을 수 있는 물고기가 있는 칸으로 이동했다면, 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.

아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 예를 들어, 크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3이 된다.

공간의 상태가 주어졌을 때, 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

0: 빈 칸 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기 9: 아기 상어의 위치 아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

풀이

• 먹이 우선순위는 Comparable 인터페이스를 이용하여 구현 (거리 > row > col)
• BFS를 통해 상어가 현재 위치에서 가능한 곳으로 모두 이동, 먹을 수 있는 물고기는 다 리스트에 담아 놓음
• 먹을 수 있는 물고기 리스트를 정렬해서 가장 가까운 것을 먹고, 성장할 수 있을 경우 성장한 후, 리스트 비우기
• 2, 3번째 과정 반복

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Boj16236 {
    /*
     * 처음 아기상어의 크기는 2
     * 1초에 한칸씩 사방탐색
     * 자신의 크기보다 큰 물고기는 못지나감
     * 크기가 같은 물고기는 지나갈 수 있지만, 먹을 수 없음
     * 크기가 작은 물고기는 지나갈 수 있고, 먹을 수 있음
     *
     * 먹을 수 있는 물고기가 많다면 가장 가까운 것을 먹으러 감 (거리: 물고기까지 가야 하는 칸)
     * 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기, 그런 고기도 많다면 가장 왼쪽에 있는 물고기 먹는다
     * 자신의 크기와 같은 수의 물고기를 먹을때마다 크기가 1 증가한다
     * 더이상 먹을 수 있는 물고기가 없으면 종료
     */

    static class Fish implements Comparable<Fish> {
        int r, c, dist;

        public Fish(int r, int c, int dist) {
            this.r = r;
            this.c = c;
            this.dist = dist;
        }

        public int compareTo(Fish o) {
            // 0. 거리가 가까운 것부터
            if (this.dist == o.dist) {
                    // 1. 가장 위쪽 (row 비교)
                    if (this.r == o.r) {
                        // 2. 가장 왼쪽 (col 비교)
                        return this.c - o.c;
                    }
                    return this.r - o.r;
            }
            return this.dist - o.dist;
        }
    }

    static int n, ans, size = 2, eatCnt = 0; // ans: 상어의 시간 저장
    static int[] dr = {-1, 0, 1, 0}, dc = {0, -1, 0, 1};
    static int[][] map;
    static Fish shk;
    static ArrayList<Fish> fishes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    shk = new Fish(i, j, 0);
                    map[i][j] = 0;
                }
            }
        }

        babyShark();
        System.out.println(ans);

    }

    static void babyShark() {
        Queue<Fish> shark = new LinkedList<>();
        boolean[][] vis = new boolean[n][n];
        shark.add(shk);
        vis[shk.r][shk.c] = true;

        while (true) {
            while (!shark.isEmpty()) {
                // 1. BFS를 통해 현재 위치에서 먹을 수 있는 물고기 탐색 (자신보다 크기 작은 것) && 거리 기록
                Fish now = shark.poll();

                for (int i = 0; i < 4; i++) {
                    int nr = now.r + dr[i];
                    int nc = now.c + dc[i];

                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && !vis[nr][nc]) {
                        // 이동 가능
                        if (map[nr][nc] <= size) {
                            shark.add(new Fish(nr, nc, now.dist + 1));
                            vis[nr][nc] = true;

                            // 먹기 가능
                            if (map[nr][nc] >= 1 && map[nr][nc] < size) {
                                fishes.add(new Fish(nr, nc, now.dist + 1));
                            }
                        }
                    }
                }
            }

            // 거리 순 나열
            if (!fishes.isEmpty()) {
                eat();
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        vis[i][j] = false;
                    }
                }
                shark.add(shk);
            } else return;
        }
    }

    static void eat() {
        // 2. 물고기 중 거리 재서 가장 가까운 거 먹기
        Collections.sort(fishes);

        Fish f = fishes.get(0);

        // 먹기
        shk.r = f.r;
        shk.c = f.c;
        ans += f.dist;
        map[f.r][f.c] = 0;

        if (++eatCnt == size) {
            size++;
            eatCnt = 0;
        }

        fishes.clear();
    }

}

처음에는 상어가 물고기를 탐색하고, 먹는 과정을 모두 하나의 메서드에 넣었는데 알듯말듯한 오차가 조금씩 생겨서 몇시간을 고생했다... 기능별로 모듈화를 하니 보다 깔끔하게 구현할 수 있었다. 객체지향언어를 사용하는 만큼 앞으로도 잘 활용해보도록 하자~! ^ㅁ^

🚨 실력이 뛰어나지 않아 코드가 지저분할 수 있습니다! 🚨

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. (4 ≤ N, M ≤ 500)

둘째 줄부터 N개의 줄에 종이에 쓰여 있는 수가 주어진다. i번째 줄의 j번째 수는 위에서부터 i번째 칸, 왼쪽에서부터 j번째 칸에 쓰여 있는 수이다. 입력으로 주어지는 수는 1,000을 넘지 않는 자연수이다.

출력

첫째 줄에 테트로미노가 놓인 칸에 쓰인 수들의 합의 최댓값을 출력한다.

풀이 (빡구현)

• 총 19가지 경우의 수 빡 구현........ 대칭도 된다는걸 나중에 알아서 이런 무모한 짓을 했다 하하하하 회전만 있는 줄 알았지...^^
• 3, 5번째 모형(ㄴ, ㅜ)은 거의 비슷하고 꼭다리 하나를 어디 붙이느냐 차이여서 같은 메서드에서 구현했다.
• 여기 반례만 체크한다면 통과 가능할 것! 작성자분 정말 감사합니다 덕분에 풀었습니다,,

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj14500 {
    static int n, m, ans = Integer.MIN_VALUE;
    static int[][] map;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                tetromino(i, j);
            }
        }

        System.out.println(ans);
    }

    /*
    각 모양 하나씩 회전, 대칭해보며
    가능할 경우 다 계산하고, 최댓값 비교 및 갱신
     */

    static void tetromino(int r, int c) {
        one(r, c); // 1번째 모형 (일자)
        two(r, c); // 2번째 모형 (정사각형)
        threeFive(r, c); // 3, 5번째 모형 (ㄴ, ㅜ)
        four(r, c); // 4번째 모형(z)
    }

    static void one(int r, int c) {
        // 1-1. 가로
        int sum = 0;
        int nc = c + 3;
        if (nc < m) {
            for (int i = c; i <= nc; i++) {
                sum += map[r][i];
            }
        }
        ans = Math.max(ans, sum);

        // 1-2. 세로
        sum = 0;
        int nr = r + 3;
        if (nr < n) {
            for (int i = r; i <= nr; i++) {
                sum += map[i][c];
            }
        }
        ans = Math.max(ans, sum);
    }

    static void two(int r, int c) {
        int sum = 0;
        if (r + 1 < n && c + 1 < m) {
            for (int i = r; i <= r + 1; i++) {
                for (int j = c; j <= c + 1; j++) {
                    sum += map[i][j];
                }
            }
        }
        ans = Math.max(ans, sum);
    }

    static void threeFive(int r, int c) {
        // 3-1. 원래 모형
        int nr = r + 2;
        int nc = c + 1;
        int sum = 0;
        int sum2 = 0;
        int sum3 = 0;
        if (nr < n && nc < m) {
            for (int i = r; i <= nr; i++) {
                sum += map[i][c];
                sum3 += map[i][nc];
            }
            sum3 += map[nr][c];
            sum2 = sum + map[r + 1][nc];
            sum += map[nr][nc];
        }
        ans = Math.max(ans, sum);
        ans = Math.max(ans, sum2);
        ans = Math.max(ans, sum3);

        // 3-2. 시계방향 90도
        nr = r + 1;
        nc = c + 2;
        sum = 0;
        sum3 = map[r][c];
        if (nr < n && nc < m) {
            for (int i = c; i <= nc; i++) {
                sum += map[r][i];
                sum3 += map[nr][i];
            }
            sum2 = sum + map[nr][c + 1];
            sum += map[nr][c];
        }
        ans = Math.max(ans, sum);
        ans = Math.max(ans, sum2);
        ans = Math.max(ans, sum3);

        // 3-3. 시계방향 180도
        nr = r + 2;
        nc = c + 1;
        sum = 0;
        sum3 = 0;
        if (nr < n && nc < m) {
            for (int i = r; i <= nr; i++) {
                sum += map[i][nc];
                sum3 += map[i][c];
            }
            sum3 += map[r][nc];
            sum2 = sum + map[r + 1][c];
            sum += map[r][c];
        }
        ans = Math.max(ans, sum);
        ans = Math.max(ans, sum2);
        ans = Math.max(ans, sum3);

        // 3-4. 시계방향 270도
        nr = r - 1;
        nc = c + 2;
        sum = 0;
        if (nr >= 0 && nc < m) {
            for (int i = c; i <= nc; i++) {
                sum += map[r][i];
            }
            if (r + 1 < n) sum3 = sum + map[r + 1][nc];
            sum2 = sum + map[nr][c + 1];
            sum += map[nr][nc];
        }
        ans = Math.max(ans, sum);
        ans = Math.max(ans, sum2);
        ans = Math.max(ans, sum3);
    }

    static void four(int r, int c) {
        // 4-1. 원래 모형
        int nr = r + 2;
        int nc = c + 1;
        int sum = 0;
        int sum2 = 0;
        if (nr < n) {
            if (nc < m) {
                for (int i = r; i < nr; i++) {
                    sum += map[i][c];
                }
                for (int i = nr - 1; i <= nr; i++) {
                    sum += map[i][nc];
                }
            }
            nc = c - 1;
            if (nc >= 0) {
                for (int i = r; i < nr; i++) {
                    sum2 += map[i][c];
                }
                for (int i = nr - 1; i <= nr; i++) {
                    sum2 += map[i][nc];
                }
            }
        }
        ans = Math.max(ans, sum);
        ans = Math.max(ans, sum2);

        // 4-2. 시계방향 90도
        nr = r - 1;
        nc = c + 2;
        sum = 0;
        sum2 = 0;
        if (nc < m) {
            if (nr >= 0) {
                for (int i = c; i < nc; i++) {
                    sum += map[r][i];
                }
                for (int i = nc - 1; i <= nc; i++) {
                    sum += map[nr][i];
                }
            }
            nr = r + 1;
            if (nr < n) {
                for (int i = c; i < nc; i++) {
                    sum2 += map[r][i];
                }
                for (int i = nc - 1; i <= nc; i++) {
                    sum2 += map[nr][i];
                }
            }
        }
        ans = Math.max(ans, sum);
        ans = Math.max(ans, sum2);
    }
}

결론... 어찌보면 정말 무식하게 풀었다. 빡구현은 정말 힘들고 오랜 시간이 걸리고 오류 잡기도 어렵다. 😭 다른 분들 풀이 보니까 DFS로 풀던데 크흠,,, 그 방법으로도 시도해 봐야겠다. 그래도 풀긴 풀었네 껄껄

풀이 (DFS)

++ 2022.10.10 dfs 코드 추가

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Boj14500_2 {
    /*
    테트로미노 하나를 적절히 놓아서 놓인 칸에 쓰여 있는 수의 합을 최대로 해보자!
    테트로미노는 회전, 대칭이 가능하다
     */
    static int n, m, ans;
    static int[][] map;
    static boolean[][] vis;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        ans = Integer.MIN_VALUE;
        vis = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vis[i][j] = true;
                dfs(i, j, 1, map[i][j]);

                if (i+1 < n && j+2 < m) one(i, j); // ㅜ
                if (i-1 >= 0 && j+2 < m) two(i, j); // ㅗ
                if (i-1 >= 0 && i+1 < n && j+1 < m) three(i, j); // ㅓ
                if (i-1 >= 0 && i+1 < n && j-1 >= 0) four(i, j); // ㅏ
                vis[i][j] = false;
            }
        }
        System.out.println(ans);
    }

    // ㅜ
    static void one(int r, int c) {
        int sum = map[r][c] + map[r][c+1] + map[r][c+2] + map[r+1][c+1];
        ans = Math.max(ans, sum);
    }

    // ㅗ
    static void two(int r, int c) {
        int sum = map[r][c] + map[r][c+1] + map[r][c+2] + map[r-1][c+1];
        ans = Math.max(ans, sum);
    }

    // ㅓ
    static void three(int r, int c) {
        int sum = map[r][c] + map[r][c+1] + map[r-1][c+1] + map[r+1][c+1];
        ans = Math.max(ans, sum);
    }

    // ㅏ
    static void four(int r, int c) {
        int sum = map[r][c] + map[r][c-1] + map[r-1][c-1] + map[r+1][c-1];
        ans = Math.max(ans, sum);
    }

    static void dfs(int r, int c, int cnt, int sum) {
        if (cnt == 4) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && !vis[nr][nc]) {
                vis[nr][nc] = true;
                dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
                vis[nr][nc] = false;
            }
        }
    }
}

한 달 반이 지나고, dfs로 다시 풀어봤다. 아무래도 속도는 쌩구현이 조금 더 빠르긴 하다. 다만 시험에서는 오류잡기도 빡세고 구현이 더 쉬운 dfs로 푸는 게 맞다고 본다. 한 달 반 전에는 dfs로 어떻게 구현할지도 감이 안왔는데 뿌듯하다!!!!! 많이 성장한 나에게 박수,,, 👏

문제

아래는 비상연락망을 나타낸 그림이다.

각 원은 개개인을 의미하며, 원 안의 숫자는 그사람의 번호를 나타내고 빨간원은 연락을 시작하는 당번을 의미한다.

화살표는 연락이 가능한 방향을 의미한다.

위의 예시에서는 7번과 1번은 서로 연락이 가능하다,

하지만 2번과 7번의 경우 2번은 7번에게 연락할 수 있지만 7번은 2번에게 연락할 수 없다.

비상연락망이 가동되면 아래 그림과 같이 연락을 시작하는 당번인 2번은 연락 가능한 7번과 15번에 동시에 연락을 취한다 (다자 간 통화를 사용한다고 가정).

그 다음 아래와 같이 7번은 1번에게, 15번은 4번에게 연락을 취한다 (이 과정은 동시에 일어난다고 가정한다).

그 다음 아래와 같이 1번은 8번과 17번에게 동시에 연락하며, 이와 동시에 4번은 10번에게 연락한다.

7번과 2번의 경우는 이미 연락을 받은 상태이기 때문에 다시 연락하지 않는다.

위의 모습이 연락이 끝난 마지막 모습이 되며, 마지막에 동시에 연락 받은 사람은 8번, 10번, 17번의 세 명이다.

이 중에서 가장 숫자가 큰 사람은 17번이므로 17을 반환하면 된다.

※ 3, 6, 11, 22번은 시간이 지나도 연락을 받지 못한다.

[제약 사항]

연락 인원은 최대 100명이며, 부여될 수 있는 번호는 1이상, 100이하이다.

단, 예시에서 5번이 존재하지 않듯이 중간 중간에 비어있는 번호가 있을 수 있다.

한 명의 사람이 다수의 사람에게 연락이 가능한 경우 항상 다자 간 통화를 통해 동시에 전달한다.

연락이 퍼지는 속도는 항상 일정하다 (전화를 받은 사람이 다음사람에게 전화를 거는 속도는 동일).

비상연락망 정보는 사전에 공유되며 한 번 연락을 받은 사람에게 다시 연락을 하는 일은 없다.

예시에서의 3, 6, 11, 22번과 같이 연락을 받을 수 없는 사람도 존재할 수 있다.

입력

입력의 첫 번째 줄에는 입력 받는 데이터의 길이와 시작점이 주어진다.

그 다음 줄에 입력받는 데이터는 {from, to, from, to, …} 의 순서로 해석되며 예시의 경우는 {2, 7, 11, 6, 6, 2, 2, 15, 15, 4, 4, 2, 4, 10, 7, 1, 1, 7, 1, 8, 1, 17, 3, 22}와 같다.

그런데 순서에는 상관이 없으므로 다음과 같이 주어진 인풋도 동일한 비상연락망을 나타낸다 (같은 비상연락망을 표현하는 다양한 인풋이 존재 가능하다).

{1, 17, 3, 22, 1, 8, 1, 7, 7, 1, 2, 7, 2, 15, 15, 4, 6, 2, 11, 6, 4, 10, 4, 2}

다음과 같이 동일한 {from, to}쌍이 여러 번 반복되는 경우도 있으며, 한 번 기록된 경우와 여러 번 기록된 경우의 차이는 없다.

{1, 17, 1, 17, 1, 17, 3, 22, 1, 8, 1, 7, 7, 1, 2, 7, 2, 15, 15, 4, 6, 2, 11, 6, 4, 10, 11, 6, 4, 2}

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스에 대한 답을 출력한다.

풀이

• BFS 이용
• 현재 큐의 사이즈만큼 poll하며 레벨을 저장한다.
• BFS가 끝난 후, 기록된 가장 높은 레벨의 원소 중 가장 큰 값이 정답!

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Swea1238 {
    // 가장 마지막에 연락을 받는 사람 중 번호가 가장 큰 사람 구하기
    static ArrayList<Integer>[] people;
    static int[] check;
    static int ans, cnt = 0;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= 10; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int len = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());

            check = new int[101];
            ans = Integer.MIN_VALUE;
            people = new ArrayList[101];

            for (int i = 1; i <= 100; i++) {
                people[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());

            for (int i = 0; i < len / 2; i++) {
                int from = Integer.parseInt(st.nextToken());
                int to = Integer.parseInt(st.nextToken());

                if (!people[from].contains(to)) {
                    people[from].add(to);
                }
            }

            bfs(start);
            for (int i = 1; i <= 100; i++) {
                if (check[i] == cnt - 1) {
                    ans = Math.max(ans, i);
                }
            }

            sb.append("#" + tc + " " + ans + "\n");
        }
        System.out.println(sb);

    }

    static void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        q.add(node);
        check[node] = 1;


        while (!q.isEmpty()) {
            for (int j = q.size() - 1; j >= 0; j--) {
                int now = q.poll();

                for (int i = 0; i < people[now].size(); i++) {
                    int person = people[now].get(i);

                    if (check[person] == 0) {
                        check[person] = cnt + 1;
                        q.add(person);
                    }
                }
            }
            cnt++;

        }
    }

}

DFS가 아닌 BFS에서 레벨을 기록하는 방식은 처음이라 메모메모...! 지금까지 비슷한 문제를 풀 때 poll을 하자마자 add를 하는데 분기(?)를 어떻게 구분하지 하는 고민이 있었는데 간단하게 해결이 되었다. 큰 깨달음을 얻은 하루!

🚨 실력이 뛰어나지 않아 코드가 지저분할 수 있습니다! 🚨

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

풀이

• 백트래킹을 통해 가능한 영역에 모두 울타리를 세운다.
• 울타리를 3개 세우면 바이러스를 모두 퍼트려보고 안전영역을 계산한다.
• 계산한 값과 기록된 최댓값을 비교해 최댓값을 갱신한다.

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Boj14502 {
    /*
    1. 3개를 백트래킹으로 가능한 영역에 모두 세우고,
    2. 3개 다 세우면 바이러스 다 퍼트려본후
    3. 안전영역 계산해서 최댓값 비교
     */
    static int n, m, ans = Integer.MIN_VALUE;
    static int[][] map;
    static int[] dr = {-1, 1, 0, 0,};
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        fence(0, 0, 0);
        System.out.println(ans);
    }

    static void fence(int r, int c, int cnt) {
        if (cnt == 3) {
            // 바이러스 다 퍼트려보기
            int[][] newMap = new int[n][m];
            Queue<int[]> vs = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    newMap[i][j] = map[i][j];
                    if (map[i][j] == 2) {
                        vs.add(new int[] {i, j});
                    }
                }
            }

            virus(newMap, vs);
            return;
        }

        if (r >= n) return;

        if (c >= m) {
            fence(r + 1, 0, cnt);
            return;
        }

        if (map[r][c] == 0) {
            map[r][c] = 1;
            fence(r, c + 1, cnt + 1);
            map[r][c] = 0;
        }

        fence(r, c + 1, cnt);
    }

    private static void virus(int[][] newMap, Queue<int[]> vs) {
        while (!vs.isEmpty()) {
            int[] now = vs.poll();

            for (int i = 0; i < 4; i++) {
                int nr = now[0] + dr[i];
                int nc = now[1] + dc[i];

                if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                    if (newMap[nr][nc] == 0) {
                        newMap[nr][nc] = 2;
                        vs.add(new int[] {nr, nc});
                    }
                }
            }
        }

        // 안전영역 구하기
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (newMap[i][j] == 0) cnt++;
            }
        }

        ans = Math.max(ans, cnt);
    }

}

40분만에 풀어서 기분이 아주 좋았던 문제! 좀 더 실력이 향상되면 코드를 깔끔하게 작성하는 방법에 대해서도 고민해봐야겠다...ㅎㅎ

오랜만의 포스팅. 그간 정말 많은 일이 있었지만, 정말 인상깊은 문제를 풀어서 기억이 날아가기 전에 얼른 기록하고자 글을 적어본다...

🚨 실력이 뛰어나지 않아 코드가 지저분할 수 있습니다! 🚨

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

풀이

• 궁사의 조합을 구하고(m개 중 3개를 뽑는 조합), 각 조합을 모두 게임에 넣어보며 최대로 적을 죽일 수 있는 경우를 구한다.

  import java.io.BufferedReader;
  import java.io.FileInputStream;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.StringTokenizer;
  

public class Boj17135 { /* * 각 칸에 포함된 적의 수는 최대 하나 * n + 1칸에는 성이 있다, 궁수 3명을 배치해야 한다. * 각 궁수는 턴마다 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. * 궁수가 공격하는 적은 거리가 d 이하인 적 중에서 가장 가까운 적. 여럿일 경우에는 가장 왼쪽에 있는 적. * 같은 적이 여러 궁수에게 공격당할 수 있으며, 공격받으면 게임에서 제외된다. * 궁수의 공격이 끝나면 적이 이동한다. 아래로 한 칸 이동하며, 성이 있는 칸으로 이동하면 게임에서 제외 * 모두 제외되면 게임 끝 * 궁수의 공격으로 제거할 수 있는 적의 최대 수 계산 * 거리 계산은 Math.abs(r1 - r2) + Math.abs(c1 - c2) */

static int[] sel;
static int n, m, d, ans;
static int[][] map;

public static void main(String[] args) throws IOException {
    System.setIn(new FileInputStream("src/input.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    d = Integer.parseInt(st.nextToken()); // 궁수의 공격거리 제한
    map = new int[n][m];

    for (int i = 0; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < m; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    sel = new int[3];
    combination(0, 0);
    System.out.println(ans);
}

static void combination(int idx, int cnt) {
    if (cnt == sel.length) {
        // 게임 진행
        // 궁사의 행은 n, 열은 sel[i]

        int[][] archer = new int[3][2];
        for (int i = 0; i < 3; i++) {
            archer[i][0] = n;
            archer[i][1] = sel[i];
        }

        int[][] nowMap = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nowMap[i][j] = map[i][j];
            }
        }

        game(archer, nowMap);
        return;
    }

    for (int i = idx; i < m; i++) {
        sel[cnt] = i;
        combination(i + 1, cnt + 1);
    }

}

static void game(int[][] ac, int[][] nowMap) {
    int enemyCnt = 0;

    while (true) {
        // 궁수의 배치는 -> m 중에 3개 조합 -> ac로 가져옴

        // 매 턴마다 궁수는 적 하나를 공격한다.
        // 아랫즐 왼쪽부터 보면서 값이 1일 경우 거리 비교 후 최솟값 기록 (같은거 x 더 작은거 o)
        // 본 줄에서 적이 있으면 윗줄 볼필요 x 적이 없으면 계속 진행 (~ 거리가 d 이하일때까지)
        Queue<int[]> enemy = new LinkedList<>();

        for (int k = 0; k < 3; k++) {
            int[] nowAc = ac[k];
            int min = Integer.MAX_VALUE;
            int minR = -1, minC = Integer.MIN_VALUE;
            for (int i = n - 1; i >= 0; i--) {
                for (int j = 0; j < m; j++) {
                    if (nowMap[i][j] == 1) {
                        int dist = Math.abs(nowAc[0] - i) + Math.abs(nowAc[1] - j);
                        if (dist <= d) {
                            if (dist < min) {
                                min = dist;
                                minR = i; minC = j;
                            } else if (dist == min) {
                                if (minC > j) {
                                    minR = i; minC = j;
                                }
                                // 현재 열이 minLeft보다 크면 갱신하지 않는다
                            }
                        }
                    }
                }
            }

            if (minR != -1 && minC != -1) {
                enemy.add(new int[] {minR, minC});
            }
        }

        while (!enemy.isEmpty()) {
            int[] nowEn = enemy.poll();

            int r = nowEn[0];
            int c = nowEn[1];

            if (nowMap[r][c] == 1) {
                nowMap[r][c] = 0;
                enemyCnt++;
            }
        }

        // 한 분기가 지날 때마다 적은 아래로 한 칸 이동
        int sum = 0;
        for (int i = n - 1; i >= 1; i--) {
            for (int j = 0; j < m; j++) {
                nowMap[i][j] = nowMap[i - 1][j];
                sum += nowMap[i][j];
            }
        }

        // n+1로 이동할 경우 게임에서 제외
        for (int j = 0; j < m; j++) {
            nowMap[0][j] = 0;
        }

        // 모든 적이 제외되면 게임 끝
        if (sum <= 0) break;
    }

    ans = Math.max(ans, enemyCnt);
}

}

교수님께서 구현 문제가 코테에서 나오면 가장 마지막에 풀라는 이유를 알 수 있었던 문제였다...
딱 보기에는 금방 구현할 수 있을 것 같으면서도, 은근 까다로워 정~~말 오랜 시간에 걸쳐 풀었다. 3시간은 걸린듯... ^^
명심하자. **구현문제는 맨 마지막에 풀기!**
코드가 다소 더럽긴 하지만 그래도 이제는 골드3 문제도 스스로 풀 수 있는 내 자신 칭찬해~! 많이컸다..! 👍

놀랍게도 동차합격에 성공했다...!!!!

하지만 이번에는 공부 방법은 남기지 못할 것 같다. 😅 왜냐하면

너무나도 턱걸이로 합격했기 때문 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 사실 기대도 안하고 있었다... 더 중요한 시험이 있어서 그거 준비하다가 실기 시험 전날에만 빡공해 봤는데 가채점을 할때도 잘 쳐줘야 55점이여서,,, 역시 하루로는 힘들구나,,, 세상은 가혹해,,, 하고 있었는데 🥲 채점을 후하게 해준것같다 ㅠㅠㅠㅠㅠㅠㅠㅠ 넘나 다행...!

시험 전날에는 1시까진 다른 공부하다가, 점심 먹고 나서부터 정처기 공부에 돌입해 새벽 4시까지 했다. 종료시간이 저런 이유는 아침에 일어나서도 더 공부를 해서 그런것 같당 이전에는 시험보자마자 기억 짱짱할때 공부방법 다 적어놨는데, 이번엔 정말 불합격이라 생각해서 아무것도 안적어놨다... 그래서 하루종일 뭘 했나 기억을 되내어봤는데 시나공 책에서 빈출 단원들만 읽으면서 달달 외웠던 것 같다. (네트워크 7계층, 결합도응집도, 디자인패턴 등) 근데 이거 하나도 안나옴 ㅋㅋㅋㅋ,,, 그냥 코딩문제 많았고, 전공자가 알만한 문제가 많았던 것 같다. 수제비카페에서도 통수라고 말이 많았다. 필기 때 문제집을 통으로 읽으며 외웠던 지식이 있었고, 시험에서도 코딩문제, sql문제가 많았던 게 신의 한수였던 것 같다. 코딩이랑 sql은 꼭 마스터해서 가시길!!!!!

아무튼 다행이다 정말정말 ㅎㅎㅎ 이렇게 정처기 취준일기는 끝이 났다!! 이제 정말 취업뿐이야

두 알고리즘은 다음과 같이 동작한다.

DFS

• 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식
• 재귀, 스택으로 구현
• 백트래킹에도 사용

    static void DFS(int x) {
        visit[x] = true;
        sb.append(x).append(' ');
        for (int y: adj[x]) {
            if (visit[y]) continue;
            DFS(y);
        }
    }

BFS

• 시작 정점의 인접 정점을 순서대로 방문하여 탐색하는 방식

• 큐(Queue)로 구현

• 검색속도는 BFS가 DFS보다 더 빠름

  static void BFS(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visit[x] = true;
  
        while(!q.isEmpty()) {
            x = q.poll();
            sb.append(x).append(' ');
            for (int y: adj[x]) {
                if (visit[y]) continue;
                q.add(y);
                visit[y] = true;
            }
        }
    }

시간복잡도, 공간복잡도

그래프를 순회하는 시간복잡도는 DFS, BFS 모두 동일하며, 그래프를 저장하는 방식으로 인접 행렬을 사용하냐 인접 리스트를 사용하냐에 따라 차이가 있다.

인접 행렬

• 그래프의 연결 관계를 2차원 배열로 나타내는 방식

• 두 정점이 연결됐을 경우 1, 가중치가 있을 경우 가중치로 표현
• 구현이 쉬움
• 차지하는 공간에 비해 사용하는 공간이 굉장이 낮아 활용도가 적음

  인접 리스트

  

• 그래프의 연결 관계를 2차원 ArrayList로 나타내는 방식
• 기준 정점과 연결된 정점만을 기록
• 각 정점에 기록된 원소의 수는 해당 정점의 차수와 같음

• 정점 A의 차수(deg(A)) : 정점 A에 연결된 간선의 수

• 모든 정점의 차수의 합 == 모든 간선의 개수 * 2

정점의 개수를 V, 간선의 개수를 E라고 할 때

• A와 B의 연결 여부 또는 가중치를 확인할 때 인접 행렬은 adj[A][B]로 바로 확인, 인접 리스트는 A의 ArrayList 원소를 모두 확인
• A에서 갈 수 있는 정점을 확인할 경우 인접 행렬은 A행의 모든 열을 확인, 인접 리스트는 A의 ArrayList 원소를 모두 확인

-> 주로 인접리스트를 이용하지만, 연결 여부를 확인하는 경우 인접 행렬을 쓰는 게 시간복잡도가 빠르다. 즉 상황에 따라 사용 방식이 다르므로 두가지 경우를 다 잘 알아두자. -> 다만, 연결 여부를 확인하는 문제이더라도 간선의 수가 많다면 인접 행렬의 공간복잡도는 O(V^2)로 메모리 초과가 날 수도 있으니 공간복잡도도 반드시 고려할 것!

어떤 상황에 어떤 방식을 적용해야 할까?

DFS

• 각 경로의 특징을 저장해야 할 때
• 그래프의 규모가 클 때 (비교적 공간을 적게 사용함)

BFS

• 두 노드 사이의 최단 경로를 찾고 싶을 때 (BFS: 기준 노드에서부터 시작하여, 가장 빨리 도착하는 경우가 최단 경로 <-> DFS: 모든 노드를 다 살펴봐야 함)
• 검색 시작 지점에서부터 찾고자 하는 대상이 멀지 않을 때

둘 다 상관 없는 경우

• 그래프의 모든 정점을 방문해야 할 때

출처

https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89 https://itwiki.kr/w/%EA%B7%B8%EB%9E%98%ED%94%84

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<Integer> [] graph;
    static int[] parent;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        graph = new ArrayList[n + 1];
        visit = new boolean[n + 1];
        parent = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int to = Integer.parseInt(st.nextToken());
            int from = Integer.parseInt(st.nextToken());
            graph[to].add(from);
            graph[from].add(to);
        }

        dfs(1);
        for (int i = 2; i <= n; i++)
            System.out.println(parent[i]);
    }

    static void dfs(int start) {
        for (int child : graph[start]) {
            if (visit[child]) continue;
            parent[child] = start;
            visit[child] = true;
            dfs(child);
        }
    }

}

• n의 최대값이 100,000이므로 인접 행렬로 구현할 경우 100,000*100,000 .. 런타임 에러가 발생한다. 인접 리스트로 구현해주자.
• 이전에는 잘 풀지 못했던 트리 순회 문제도 dfs가 나름 익숙해지니 잘 풀리는 게 신기해서 기록해둔다 ㅎㅎ

DFS, BFS 두가지 방법으로 모두 풀어봤다.

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

풀이

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static int[][] dir = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            map = new int[m][n];
            visited = new boolean[m][n];

            while (k-- > 0) {
                st = new StringTokenizer(br.readLine());
                int row = Integer.parseInt(st.nextToken());
                int col = Integer.parseInt(st.nextToken());
                map[row][col] = 1;
            }

            int ans = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (map[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j);
                        ans++;
                    }
                }
            }
            sb.append(ans).append("\n");
        }
        System.out.println(sb);

    }

    static void dfs(int row, int col) {
        visited[row][col] = true;

        for (int i = 0; i < 4; i++) {
            int nr = row + dir[i][0];
            int nc = col + dir[i][1];

            if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
            if (map[nr][nc] == 0) continue;
            if (visited[nr][nc]) continue;

            dfs(nr, nc);
        }
    }

    static void bfs(int row, int col) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {row, col});
        visited[row][col] = true;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int r = now[0];
            int c = now[1];
            for (int i = 0; i < 4; i++) {
                int nr = r + dir[i][0];
                int nc = c + dir[i][1];

                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                if (map[nr][nc] == 0) continue;
                if (visited[nr][nc]) continue;

                q.add(new int[] {nr, nc});
                visited[nr][nc] = true;
            }
        }
   }
}

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        HashSet<String> listen = new HashSet<String>();
        ArrayList<String> listenHear = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            listen.add(br.readLine());
        }

        while (m-- > 0) {
            String s = br.readLine();
            if (listen.contains(s))
                listenHear.add(s);
        }

        listenHear.sort((s1, s2) -> (s1).compareTo(s2));
        bw.write(listenHear.size()+"\n");

        for (String name : listenHear) {
            bw.write(name+"\n");
        }
        bw.flush();
        bw.close();
    }
}

처음에는 ArrayList로 풀었다가 시간초과가 나서 찾아보니 HashSet을 사용해야 풀 수 있는 문제였다. HashSet의 contains()는 map을 기반으로 구현되어 O(1), ArrayList의 contains()는 indexOf()를 사용하기에 O(n)의 시간복잡도를 가진다! 포함여부를 묻는 문제에선 ArrayList보단 HashSet을 사용해야 한다는 깨달음을 얻은 문제였다. 또 Hash 문제를 여러개 풀어보며, HashSet과 HashMap의 차이도 알게 되었다.

[부록] HashSet과 HashMap의 차이

• HashSet : 해시 메커니즘을 사용하여 요소를 저장. 성공적으로 추가되면 true를, 중복된 객체가 들어오면 false를 리턴 HashMap에 비해 느림
• HashMap : key-value 형식의 데이터 저장. 중복 객체 마찬가지로 안받음 unique key를 이용하여 데이터에 바로 접근하므로 HashSet에 비해서 빠름

문제

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다. 인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다. 1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

입력

첫째 줄에 N, M, B가 주어진다. (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107)

둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이가 주어진다. (i + 2)번째 줄의 (j + 1)번째 수는 좌표 (i, j)에서의 땅의 높이를 나타낸다. 땅의 높이는 256보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 땅을 고르는 데 걸리는 시간과 땅의 높이를 출력하시오. 답이 여러 개 있다면 그중에서 땅의 높이가 가장 높은 것을 출력하시오.

풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); // 행
        int m = Integer.parseInt(st.nextToken()); // 열
        int b = Integer.parseInt(st.nextToken()); // 인벤토리

        int[][] map = new int[n][m];
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        // 지도 채우기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                min = Integer.min(min, map[i][j]);
                max = Integer.max(max, map[i][j]);
            }
        }

        // 최소 ~ 최대 블록까지 걸리는 시간 비교해서 가장 작은 시간 도출
        // 블록 제거 == 2초 & 블록 쌓기 == 1초
        // 인벤토리에 든 값을 확인해줘야함
        int time = Integer.MAX_VALUE;
        int floor = 0;
        for (int i = min; i <= max; i++) {
            int total = 0;
            int inventory = b;
            for (int j = 0; j < n; j++) {
                for (int z = 0; z < m; z++) {
                    // 기준값보다 현재값이 작으면 -> 블록 쌓기
                    if (map[j][z] < i) {
                        total += i - map[j][z];
                        inventory -= i - map[j][z];
                    }
                    // 기준값보다 현재값이 크면 -> 블록 제거
                    else if (map[j][z] > i) { 
                        total += (map[j][z] - i) * 2;
                        inventory += map[j][z] - i;
                    }
                }
            }

            // 인벤토리가 음수가 아니고, 걸린 시간이 기록된 시간보다 적으면 최솟값 교체
            if (inventory >= 0 && total <= time) {
                time = total;
                floor = i;
            }
        }
        System.out.println(time + " " + floor);
    }
}

• 지도에 나와있는 최솟값 ~ 최댓값까지 모든 경우를 따져서 최소 시간을 구한다.
• total - inventory를 변수에 따로 저장하고, 절댓값으로 더해주거나 빼는 방법도 있음
• 다 돌고나서 inventory의 값이 음수라면 불가능한 경우이므로 제외 (이부분에서 애먹었는데 꽤나 간단한 방법이었다..)
• 답이 여러개 있다면 가장 땅의 높이가 높은 것을 출력하므로 최솟값 비교는 <=로!

공부법

내 공부법은 모두 제이크 선생님으로부터 나온다. 토스 독학러들에게 매우 유명한 그 제이크 토익스피킹 선생님 맞다! 제이크쌤 짱!!!!! 제이크 선생님의 보라책으로 공부했고, 유튜브를 보며 각 파트의 유형을 익혔다. https://youtube.com/playlist?list=PLi5ZeXp0sQKgLj-osJnJkB4HjLD9BHZbX 여기에 파트별로 정리가 잘 되어있다.

한 일주일 공부했는데 5일간은 엄청 공부 하기 싫어하면서 각 파트가 무엇인지, 문제유형은 어떤 게 나오는지 설렁 설렁 보았고 시험일 전날에 파트 1~5 다시 보면서 부족한 부분을 보충했다. 부족하다고 느끼는 부분은 제이크 쌤의 유튜브 중 실전문제를 반복적으로 풀었다. 👇 난 영작을 필요로 하는 파트 3, 5(이전 파트6)이 어렵게 느껴져 그부분을 중심적으로 보았다!

시험일 당일은 저녁시험이라 시간이 좀 남았는데, 보라책 뒷면에 수록된 모의고사를 3회 돌렸다. 모의고사를 돌리면서 느낀점은 역시 실전이 중요하다는 것이었다. 유형 파악도 중요하지만, 이 글을 읽는 분이 있다면 꼭 유형파악보다 모의고사에 많은 시간을 쓰길 추천한다! 유형파악은 빠르게 넘어가고 부딪혀보자.

문제 정리

아래는 시험 치고 온 당일에 적은 문제 정리이다.

1-2

무난 자신감 있게 읽으려 노력했고, 강세와 발음에 가장 신경썼다. 다만 둘다 한두번씩 절었다. 🥲 이정도는 봐주길 바랄 뿐,,,

3-4

나쁘지 않게 본 편인 것 같다.

3번 회사에서 찍힌 사진이다 (a office라고 함,,) 4명의 사람이 있다 가장 먼저 보이는 건 책을 읽고 있는 여자 그녀는 안경을 썼다 (a glasses 라고 함 ㅠㅠ) 그녀 옆에는 어떤 남자가 무언가를 보고 있다 핸드폰인것 같다 (이 말을 했나 안했나 기억이 안남) 사진의 왼쪽에는 두명이 서로 대화중이다 I thint this picture was taken in a office. There are four people in the picture. The first thing I can see is a women reading a book. She is wearing a glasses. Next to her, a man is looking at something. It seems like a phone. On the left side of the picture, two people are talking to each other.

4번 아웃도어 마켓에서 찍힌 사진이다 두명의 사람이 있다 가장 먼저 보이는 건 돈을 건네고 있는 남자 파란 셔츠를 입었다 (블랙? 블루 셔츠라고 한번 더듬음) 사진의 왼쪽에는 여자가 달걀을 포장중이다 사진의 가운데에는 달걀들이 쌓여있다. I think this picture was taken in ... an outdoor market. There are two people in the picure. The first thing I can see is a man handing over a dollar. He is wearing a black... blue shirt. _In _ the left side of the picture, a women is packing some eggs. In the middle of the picture, some eggs are stacked.

5-7

5번 그냥 묻는 그대로 1문장 답함

6번 절었음 ㅠ 혼자사길원하냐? 뉘앙스의 질문 난 혼자 살길 원한다. 혼자의 공간은 나에게 comforable을 준다. (뭔소리야,,😭)

7번 완전 절었음 ㅠㅠㅠㅠ 멘붕.. 룸메이트가 있길 원하냐 아님 없길 원하냐 난 혼자 살길 원하다.. 어쩌구하다가 마지막에 윗아웃 룸메이트 한마디,,, ^^

8-10

8번 첫번째 강의가 언제냐? -> The lecture will lead by 인물 at 10 am. 묻는대로 한문장 답합. 보라책에서 lecture은 뭔가 lead로 한다고 했던것같아서 저렇게했는데 끝나고 보니 lead도 아니더라 그냥 배운대로 held할걸 haha

9번 Q. 원금 50달러 그대로 내야하냐? A. You can get discount 25 dollars in advance. 잘 맞게 이해한지 모르겠어서 좀 얼렁뚱땅 한문장 말함 ㅠ 어흑

10번 There is two scheduled sessions. First, 인물 will give a 강연 on 주제 at 시간. Secont, 강연 on 주제 will be conducted by 인물 at 시간.

11

Q. 치과의사가 되는것의 장점?

치과의사로 일하는건 좋다고 생각한다 무엇보다도 돈을 많이 번다 내 삼촌의 경우에 의하면 그는 치과의사이다. 그는 부유하다 그리고 우리가족한테 선물도 많이준다 그러므로 치과의사로 일하는건 좋다고 생각한다

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ하 세상 잼민이처럼 편하고 단순한 문장으로 말함 ㅠ... 답변 다하고 시간이 남은건 처음이었다 (그래서 뒤늦게 therefore로 덧붙였지만, 똑같은 문장 반복이나 다름없어서 살짝 걱정된다) 지금 생각하면 더 좋은 뒷받침 의견이 많은데 아쉽다. 그래도 이제와서 뭘 어쩌겠어.. 사실 11번은 제대로 답을 만들어 본 적도 없고, 운에 맡겼는데 기승전결은,,, 정말 비루하지만 있긴하니까 이정도에 감사해야겠다~~!

결론

6, 7 절었고 9번 살짝 애매하게 한문장으로만 답 11번 세상 초간단하게 버벅이며 대답

결과

150점 레벨6! 첫 토스라 감이 안 오긴 했지만 레벨5를 예상했는데 너무 높은 점수로 6을 받아서 놀랍다.. 토스 점수가 후한 편이라고는 들었는데 정말 인심이 너무 좋은듯 사실 150점 받으니까 살짝 아쉽기도 ㅎ 10점만 더받았으면 레벨 7이었는데.. 😊 증말 인간의 욕심은 끝이 없닼ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 그래도 개발자로선 나쁘지 않은 점수라고 생각하고, 레벨6과 7 사이엔 큰 벽이 있다고 생각하기에 미련 없이 토스는 끝내려고 한다!!

기나긴 토스의 대장정... 이제 끝이다 (계속 여러 일정이 겹치고, 준비가 부족하다고 느껴 취소했다) 일요일 12시에 공개됩니다 그래도 레벨 5는 나오지 않을까 생각즁,,, ㅎㅎ 따라서 내 토스 대장정은 여기서 끝... 더는 못하겠다 6이 턱걸이로 나오면 좋겠지만 5가 나와도 그냥 여기서 만족하자!!

그래 저렇게 생각하던 나도 있었네 수고많았다 나 자신!!!! 이제 토스는 끝!!!!

포스팅에 앞서

SQLD를 준비하는 나의 상태는 다음과 같았다.

• 소프트웨어 학과 복수전공

• 일주일 전에 정처기 필기 시험 봄 (문제집 5회 정독)
• 대학교에서 데이터베이스 강의 수강했었음 (but 기억 하나도 안 남)
• 기본적인 프로그래밍 지식은 있으나, SQL은 사용해 본 적 아예 없음

정보처리기사 필기 과목 중 데이터베이스가 있기 때문에, 겹치는 내용이 많아 함께 취득하면 좋을 것 같아 신청했다. 결국 공부 병행은 못하고, 정처기가 끝나고 나서야 급하게 SQLD 공부를 시작했지만 정말 겹치는 부분이 많았다!! 사실 SQLD는 그닥 중요한 자격증은 아니라고 생각하지만, 딴다면 정처기랑 SQLD 같이 따는 거 강추 👍 시험 날짜도 비슷해서 좋다.

공부 기간

단 5일.. 3월 5일에 정처기 시험 보고, 다음날까지 쉬고ㅎㅎㅎ 시험이 있는 주 월요일부터 금요일까지 빡공했다.

총 공부시간은 거의 40시간.. 매일매일 SQLD만 붙잡고 있었다.. 10, 11일엔 정말 죽고 싶었다 ㅋㅋㅋㅋㅋㅋ 찐 전공자가 아니라면 2주 정도는 잡는 걸 추천,,,

(물론 필자는 SQL에 대한 공부를 목표로 시작한 자격증이라 좀더 가성비 없이 공부한 감이 있다. 늦게 시작하기도 했고)

공부 수단

• SQL 자격검정 실전문제 (일명 노랭이)
• 무.조.건* 풀어야 한다. 이번 시험에서도 4-5문제 가량이 그대로 출제되었다. 비슷한 형식의 문제도 많이 나오고, SQLD를 준비하는 사람들이 입을 모아 추천하는 이유가 있다! 또 SQLP도 함께 대비하는 문제집이라 어려운 편인데 이걸 풀고 시험을 보면 아주 쉽게 느껴진다. 한바퀴는 무조건 돌리시길,,
• 이기적 SQLD 기본서 노랭이가 좋다고는 하지만 문제집이기 때문에 기본서가 필요하다고 생각해 당근으로 구했다. 보기 쉽게 정리는 되어 있으나 너무 쉬운 내용만 담은 느낌이다. 거의 안 봤다. 시험 직전에 정리된 걸 빠르게 훑기엔 좋았다!
• 데이터온에어 데이터가이드 개념서 필요 없고, 여기 있는 내용 다 읽으면 된다! 양이 많긴 하지만 필수로 정독해야 한다. 출제기관인 Kdata에서 제공하는 내용들이다. 5만원 정도 한다는 개념서의 내용이 그대로 담겨 있는 걸로 알고 있다. 다만 sql문이 가독성이 아주 떨어져서 2과목에서 많이 애먹었다 ^^...
• 유튜브 강의 유튜브 강의의 도움을 많이 받았다. 자세한 내용은 아래 공부 방법에 서술하겠다.

공부 방법

1과목

1과목은 데이터가이드의 가독성이 너무 떨어져서 유튜브의 도움을 받았다.

실제 교수님이신 것 같은데 무심하게 툭툭 드립치시는 게 아주 취향저격당해서 재밌게 봤다. 이 재생목록에서 <SQLD 선행학습> 부분만 다 보면 어느 정도 1과목에 대한 감이 온다. 가볍게 유튜브를 보고 나서 노랭이를 풀고 맞은 문제, 틀린 문제 모두 답지와 함께 다시 보았다.

2과목

2과목도 유튜브 강의가 많긴 한데, 난 그냥 확실히 하기 위해 데이터가이드 내용을 정독했다. 12번째 게시글인 <관계형 데이터베이스 개요>부터 28번째 게시글인 <절차형 DCL>까지 읽으면 된다. 난 노랭이만 보고 SQL 최적화 기본 원리까지 봐야 하는 줄 알았는데 최근 들어 최적화 부분의 출제는 지양한다고 한다. 실제로 이번 시험엔 한 문제도 안나옴!

SQL 기본, 활용 과목별로 정독 후에는 노랭이를 풀었고, 모든 문제에 대해서 답지와 함께 전광철 선생님의 유튜브 문제 풀이를 보았다. 이 재생목록을 보면 2과목의 모든 문제를 풀어주셨다. 심지어 중간중간에 개념 설명도 해주시면서 진행하신다,,, 그저 빛,,, 2과목이 살짝 막막하기도 했는데 너무너무 큰 도움이 되었다! 강력 추천!!!

계층형 쿼리는 조금 틀리게 설명하셔서(후에 정정하셨지만, 다소 헷갈렸기에) 정미나 선생님의 유튜브를 참고하였다. 정미나 선생님은 실습 환경과 함께 풀이를 제공하셔서 더 직관적인 이해가 가능하다. 정미나 선생님 유튜브도 추천!

시험 당일

시험 당일에는 김강민 선생님의 최종 정리 영상을 보며 아침을 먹었다. 1과목, SQL 활용 과목의 함수 정리가 되어 있는데 빈출 유형만 쏙쏙 집어주셔서 아주 좋다! 시험 직전에 본건데 정말 큰 도움이 되었다. 실제로 이 영상 덕에 2문제 정도 더 맞춘듯! SQL 기본에 관한 영상도 있는데, 길어서 둘 중 하나만 봐야 했고 SQL 구문은 당일에 본다고 큰 변화가 없을 것 같아 위 영상을 봤다. 상황에 따라 보기를 추천. 둘 다 봐도 좋을 것 같다. 시험 당일 최고의 선택이라고 생각한다.

결과

평균은 72점! 그렇게 높은 점수는 아니지만 나름 만족스럽다 ㅎㅎ 웃긴게 총점은 같은데,,, 사전발표에서 2과목 한문제가 1과목으로 가있었다면서 최종발표 후 1과목에서 2점이 2과목으로 옮겨갔다. 이러한 사태 때문에 합격이었다가 불합격이 된 사람도 꽤 있었다 ㅠㅠ 일처리가 왜 이래요,,,

포스팅을 정리해 보니 정말 많은 선생님의 도움을 받았다 ㅋㅋㅋㅋㅋ 다들 감사합니다.. 다른 사람들의 말을 들어봐도 44회 시험은 유독 쉽게 나온 감이 있는 것 같다. 특히 계층형 쿼리에 대해 걱정이 컸는데 매우 쉽게 나왔고, 긴 쿼리 문제도 나오지 않았다. 역시 시험은 운이 가장 중요하다...는 생각이 들었지만, 위에 적힌 대로만 공부하면 절대 떨어질 일은 없을 것이다! SQL에 무지했던 나도 5일 짧고 굵게 공부해 자격증을 땄으니..! 이 글을 읽는 여러분도 할 수 있다! 화이팅! :)

정리

1. 데이터가이드 정독하고, 노랭이 꼭 푸세요
2. 劉처사, 전광철, 정미나, 김강민 선생님 유튜브 꼭 보세요
3. 2-3과목인 SQL 최적화는 안 나옵니당

나 또한... 5과목을 보며 실소가 터져나왔다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 20문제 중 내가 확실하게 아는 건 단 4문제... ⭐️ 16문제를 찍어야 하는 상황이라,, 자칫하면 과락이 나올수도 있었다. 나름 유추해가며 합리적으로 찍고, 몇 번이 많이 나왔는지 효율도 따지며 찍은 결과 ㅎㅎ,,,는 맨 밑에!

준비 중 코로나도 걸리고 참 다사다난했지만 결과는 나쁘지 않게 나와서 다행이다. 나중에 보면 재밌을 것 같아 추억 기록 겸, 공부 방법을 공유해보고자 한다 :)

포스팅에 앞서

필자는 컴공 비슷한 소프트웨어를 복수전공한 반전공 인간이다. 개발자 쪽으로 방향을 잡고, 개발한 지도 꽤 되었다. 하지만 공학적 지식은 비전공자나 다름 없으며(기만 아님) 그렇기 때문에 차근차근 정처기를 준비하였다.

공부 기간

2월 7일 월요일부터 했으니 거의 한달이지만, 중간에 코로나도 걸렸어서 3~4일 정도는 공백이 있다. 월요일부터 토요일까지 하루에 적게는 4시간, 많게는 7시간 공부했고 보통 5시간 정도 했다. 그리고 일요일은 아예 쉬었다 ㅎㅎㅎ 쉬는 날도 있어야지 그렇기 때문에 3주 반 정도라고 보면 될 것 같다! 자격증을 취득하는 게 가장 큰 목표였지만 컴퓨터 공학 지식 공부의 목적도 컸기 때문에 오래 기간을 잡았다. 결과적으론 좋은 선택이었다. 늘 계획한 대로 흘러가진 않으니, 넓게 기간을 잡는 게 좋다고 생각한다. 또 필기와 실기 범위가 겹치기 때문에 빡세게 필기를 준비하는 건 무조건 도움이 된다! 자세한 내용은 밑에서,,,,

공부 수단

• 시나공 정보처리기사 필기 문제집
• • 강력 추천한다**! 두껍긴 하지만, 그만큼 많은 내용이 알차게 담겨있다. 중요도에 따라 A, B, C, D로 나눠져 있고 중간중간 확인문제가 기출문제로 수록되어있어서 좋았다. 수제비 책과 많은 고민을 했는데, 수제비는 다소 함축적인 경향이 있는 것 같아서 제대로 공부하고 싶은 마음에 시나공 책을 구매하였다. 또 수제비는 카페에서도 충분히 많은 정보를 얻을 수 있다 ㅎㅎ,,

• 수제비 카페 정처기에 대한 정보를 가장 빠르게 얻을 수 있다. 나는 카페에 있는 데일리 문제를 자투리 시간에 틈틈이 풀었다. 족보문제도 명중률이 좋다던데 그것까진 풀 시간이 없었다.
• 시나공 기억상자 시나공 책을 구매하면 제공하는 서비스이다. 핸드폰으로도 간편하게 볼 수 있어 시험 1주전부터 틈틈이 보았고 꽤 효과가 있었다.

공부 방법

위 공부 수단에서 세 가지를 적었지만 시나공 문제집이 95%의 비중을 차지한다. 꼭 하고 싶은 말은, 반드시 문제집을 정독하라는 것이다. 아무리 두껍고 읽기 싫어도,,, 합격하겠다는 의지로,,, 정처기는 이제 문제은행이 아니다. 반드시 정독해야한다!!!!

• 나는 3주간 문제집을 정독했다. 암기보단 이해 중심으로 읽었다. 중간에 일도 많았고, 책에 써진 모든 글자를 읽고 이해한다는 생각으로 임하다 보니 3주나 걸렸다.. 솔직히 3주는 길고 2주안에 3번정도 정독하길 추천! 한 과목 당 2일씩 잡아 10일 안에 정독하는 걸 목표로 했는데 왜 이렇게 늘어졌는진 모르겠다 ^^... 그러니까 다들 일찍 시작하세요 도무지 이해가 가지 않는 부분은 유튜브에 해당 키워드를 검색해서 관련 영상을 찾아봤다. 그렇게 꼭 이해를 하고 넘어갔다.
• 남은 1주간은 기출문제를 풀고 풀이를 보며 공부했다. 2020 개정 이후 기출문제 개수가 많지 않아서 충분히 다 풀 수 있다.
• 기출문제를 풀면서, 시나공 모의고사도 풀었는데 기출문제는 평균 7585 정도 나올때 모의고사는 5060점 나오더라,,, 근데 기출문제와 많이 다른 느낌이었다. 그닥 추천은 안함!

결과

80/90/100/85/75, 평균 86 으로 합격했다!

2과목은 가채점했을 땐 95점이었는데,,, 마킹 실수인지 도중에 마킹을 바꾼건진 모르겠다 ㅠㅠ 100점도 처음 나왔고, 무엇보다 5과목에서 찍은 16문제 중 11개가 맞아 나도 너무 신기했다 ㅋㅋㅋㅋ

솔직히 정독만 했을 뿐인데 기출문제가 잘 풀려서 놀랐다. 기간을 넓게 잡고 문제집을 한단원씩 정독했던 게 컸던 것 같다. 또 올해 시험을 치뤄본 결과 기출문제만 풀고선 도저히 붙을 수 없었을 것 같다. 기출문제에선 한 번도 보지 못했던 V모델, 블루재킹, HoneyPot 등을 보며 시험보는 내내 곤혹스러웠다,,, 기출을 풀 때는 평균 75~85 정도 나와서 가벼운 마음으로 보러 갔는데, 정말 땀 뻘뻘 흘리며 나왔다. 4과목의 코딩 문제도 기출문제보다 훨씬 어렵게 나왔다. 평소에 개발을 하지 않는 사람이라면 매우 힘들었을 거라고 생각한다,,,

정리

1. 어떤 문제집이든 정독하세요!!! 기출만 풀지 마십쇼
2. 당일 오후 6시에 답안 나오긴 하는데, 그 전에 수제비에서 복원시트로 가답안 만드는것도 99% 정확합니다. 애간장 타니 카페에서 미리 확인하세용
3. 코딩문제가 점점 어려워지는듯. 프로그래밍 경험이 없다면 정말 일찍 시작하시길,,

실기 1차도 한번에 붙어서 또 포스팅을 하러 온다면 좋겠다. 이 글을 보게 된 모든 사람들이 합격하길 기원하며,, 하나둘셋 화이팅~~!

이날을 기억하고 싶어서 부끄럽지만 적어본다,, 오늘은 골드 문제를 처음으로 혼자 푼 날이다 🥺 사실 골드치곤 좀 쉬운것 같은 문제긴 한데 그래도,,, ^^ 알고리즘 특강을 들으면서도 많이 버거웠는데, 포기하지 않고 노력한 결과일까..? 조금이나마 성장한 것 같아 기분이 좋다 ㅎㅎㅎㅎ

아직 갈 길이 멀지만 더 열심히 공부하기 위한 원동력을 얻게 된 하루였다! 남은 특강도 열심히 듣고 열심히 복습해야겠다 :) 그리고 이 마음가짐 그대로 특강이 끝나고 나서도 열심히 살아야겠다. 아좌좌 화이팅!!

유클리드 호제법

• 두 개의 자연수의 최대공약수를 구하는 알고리즘
• a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. a % b = r, gcd(a, b) = gcd(b, r)

gcd(36, 24) = 12 gcd(24, 12) = 0 -> 0이 나올 때 b의 값이 최대공약수. (딱 나눠떨어지므로) 즉 36과 24의 최대공약수는 12

코드로는 다음과 같이 표현할 수 있겠다.

    // gcd(a, b) == gcd(b, a%b)를 이용, a % b == 0 일 때 반복 멈추기
    static int gcd(int a, int b) {
        while (b!=0) { // 딱 나눠 떨어졀 때까지 반복
            int r = a % b; // a를 b로 나눈 나머지
            a = b;
            b = r; // b에 나머지 대입
        }
        return a;
    }
}

코드 상으로 b=0이라 a가 최대공약수가 되었지만 반복문 직전에 b를 a에 대입한 걸 볼 수 있다!

또한 유클리드 호제법에 따르면 a, b, c의 최대공약수는 (a, b)의 공약수와 c의 최대공약수와 같다. 이를 이용해서 다음과 같이 재귀적으로 사용할 수도 있다.

gcd(gcd(a, b), c) // 이전 코드와는 무관

여기까진 나름 쉽다! 그런데 어질어질한 '확장' 유클리드 호제법이 날 기다리고 있었다,,, 확장 유클리드 호제법에 들어가기 전에 알아두면 좋은 정수론을 조금 훑고 가자

정수론

부정 방정식

• 해가 무수히 많은 방정식

  디오판토스 방정식

• 해가 정수인 경우의 부정 방정식 (ex: 3x+2y = 5)

베주 항등식

정수 x, y의 최대공약수 gcd(x, y)가 있을 때 확장 유클리드 호제법을 이용하여 ax + by = gcd(x, y)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다. (이 때 a, b 중 한개는 보통 음수가 됨) 이 식을 베주의 항등식이라고 한다.

*=> ax+by=gcd(x, y)이면 방정식의 해를 찾을 수 있다. ==> ⭐️ 방정식의 해가 반드시 존재한다 ⭐️ *

확장 유클리드 호제법

ax + by = c 에서 as + bt = r 이라는 식을 만들었다. (원래 식에서 a, b만 가져온 형태)

ex) 9x + 5y = 2 -> 9s + 5t = r

이 식을 만족하는 숫자 3개를 만들어 보고자 한다. 9s + 5t = r을 만족하는 가장 작은 r을 찾아보자.

1. s = 1, t = 0일 경우 r = a
2. s = 0, t = 1일 경우 r = b

두가지 식은 언제나 성립한다. 이 특징을 이용해서 s = 1, t = 0을 대입하면 r = a = 9가 된다. s = 0, t = 1을 대입하면 r = b = 5가 된다.

현재 두 가지 조합을 찾았다! 다음 조합도 찾아보자.

9를 5로 나누면 4가 남는다. -> 5를 4로 나누면 1이 남는다. -> 4를 1로 나누면 0이 남는다.

이 과정을 자세히 보면

9를 5로 나누는 과정 = 5(나눈 수)에 1(몫)을 곱하고 9에서 빼준다. (9-5=4)

임을 알 수 있다. 여기서 1은 별뜻 없는 게 아니고 9를 5로 나눈 몫이다!!!! 즉 원래 수 - 나눈수*몫 이라는 뜻! 값에 1을 곱하고 원래 값에서 빼 주는 같은 방식으로 표의 빈 공간을 채워보자. (헷갈리지 않게 몫을 뜻하는 q의 값을 표에 추가하였다)

1에 1을 곱하고 0에서 빼준다. => 0 - 1 = -1 0에 1을 곱하고 1에서 빼준다. => 1 - 0 = 1

새로운 행이 완성되었다! 이 표의 값을 원래 식에 대입하면 성립할까?

91 + 5\(-1) = 4 => 9 - 5 = 4

성립한다!! 식을 만족하는 s, t, r을 또 하나 찾은 셈이다. (해를 찾은 건 아니다)

한 번 더 표의 빈 부분을 채워보자. 이번에는 한 줄 내려와 a = 5, b = 4, r = 1이 된다. 따라서 q는 5 / 4 = 1 이다.

-1에 1을 곱하고 1에서 빼준다. => 1 + 1 = 2 1에 1을 곱하고 0에서 빼준다. => 0 - 1 = -1

이렇게 찾아낸 값을 또 원래 식에 대입해 보자.

9(-1) + 5\2 = 1 => -9 + 10 = 1

역시 성립한다. 새로운 s, t, r을 찾았다.

한 번 더 해보자! q는 4 / 1 = 4이며, r(나머지)는 0이다. 0이 됐다는 건, 딱 나눠떨어진다는 뜻이고 이를 나눈 값인 1이 gcd라는 뜻이 된다. 베주 항등식에서, ax + by = gcd(a, b)일 경우 해가 반드시 존재한다고 했었다. 여기서 다시 한 번 표를 보자. (거의 반복학습 ㅋㅋㅋ)

우리는 식을 as + bt = r로 만든 후 구했고 현재 식을 만족하는 gcd는 1이다. (r = 1) r = 1을 만족할 수 있게 만드는 x, y는 s, t에 해당하는 -1, 2이다. 또 9(-1) + 5\2 = 1 이 성립함도 확인했다.

아직 해는 구하지 못했다! 우리가 해를 구하려던 방정식은 9x + 5y = 2 이었다. s, t, r을 대입하여 나온 9(-1) + 5\2 = 1 식을 위와 같이 만들기 위해서는 전체*2를 해 줘야 한다.

[9(-1) + 5\2 = 1] * 2 = 9x + 5y = 2와 같다.

따라서 x = -2, y = 4임을 알 수 있다! 길고 길었지만 마침내 해를 구했다 👏

최대공약수

유클리드 호제법을 이용하여 구한다.

최소공배수

두 수의 곱 / 최대공약수

정리

s, t, r의 조합을 찾는다는 생각으로 계속하여 유클리드 호제법을 이용해서 계산하고, r이 gcd가 되는 순간 원래 방정식과 비교하여 해를 구할 수 있다. 포스팅을 하다보니 또 머리에서 정리가 된 것 같다! 이걸 코드로 구현할 수 있을지는... (먼산) 아무튼 오늘 포스팅은 끝 ㅎㅎㅎ