제목 처럼.. 2025.10.02 일하던 회사에서 퇴사를 했다 원래는 안전을 추구하는 편이라 일을 하면서 취업 준비를 해야지.. 라고 생각했지만 일을 하면서 동시에 취업 준비를 할 수 있는 환경이 아니었다 하나의 일에 집중하면 멀티가 잘 안되는 편이기도 하고 면접을 보러 연차를 쓸 수도 없었다 😥

그래서 고민 끝에 다들 말린다는.. '쌩 퇴사' 를 하게 되었다

전략 세우기

그럼 이 차디찬 세상에서 내가 취업하려면...? 어필 포인트를 잡아야 했다 바쁜 일정 속에서 1년 반 회사 다니느라 이력서가 거의 정리가 안되고 프로젝트랑 수치들만 쭉 저장해둔 상황이라 아예 처음부터 다시 작성해야 했다

장점

• 다양한 도메인 경험 (구독, 주문, 결제, 정산, 알림, IoT)
• 비즈니스 협업 경험
• 데이터에 강점 (통계학과 출신)

특히 협업 경험은 어떤 부분을 살릴까 고민하다가 AI로 다른 동료들의 업무 효율 높인 사례 2개 넣었는데 이 부분을 면접에서 의외로 많이 좋게 봐주셨다

구조

도메인이 많아서 아 많이 했네의 느낌은 줄 수 있었는데 대신 이력서의 분량이 너무 길어졌다 이러면 읽다가 지쳐서 넘길 것 같아 전체적인 구조를 문제> 해결과정 > 성과 이런 형식으로 표로 만들었다 그리고 자세히 기술적으로 어필하고 싶은 부분은 경력 기술서 링크를 달아서 이력서 자체는 간결하고 깔끔한 느낌이 들게 했다 총 3장 정도 분량을 맞췄다

지원

이제 이력서와 경력 기술서를 잘 작성했으니... 지원을 해야 했다 회사 퇴사 전에 그래도 어느정도의 문서 작성은 끝내서 물리적으로 지원은 가능했지만

지원이 두려웠다

왜 두렵지? 지금 생각하면 웃기기도 하지만 거절 당하는 것에 대한 두려움이 많이 있었던 것 같다 실제로 총 12곳 지원 밖에 안했기도 하다 지원하는 회사의 기준을 명확히 정해서 할 곳이 별로 없었기도 하다

기준

• 욕심이지만 안해본 도메인을 해보고 싶었다 특히 헬스케어 교육 브랜드 .. 약간 사람들에게 많은 선한(?) 영향 줄 수 있는 도메인 경험해보고 싶었다
• 개발 문화 있는 곳
• 전 회사에 비해 유저/트래픽 많은 곳
• 서비스 회사
• 출퇴근 50분 이내
• 타이머 10분 맞춰두고 회사 홈페이지 + JD를 읽고 5분 내에 지원동기 작성을 시도했다 > 잘 안적히면 패스 (면접 가서 지원동기에서 설득력 없는 상황,,을 없애고 싶었다)
• 잡플래닛 1점대, 2점대 초반은 패스
• 코테 < 과제/코드리뷰에 더 강점이 있다고 생각해 코테는 가볍게 패스했다

지원 결과

• 서류 합격률: 50% (6/12)
• 과제/코드리뷰 합격률: 100% (4/4)
• 1차 기술 면접 합격률: 75% (3/4)
• 2차 임원 면접 합격률: 100% (3/3)

생각보다 수치로 보면 결과가 좋은 편이었다 특히 과제를 진행한 곳들은 1차 면접에서 질문에 대답을 조금 못한 부분이 있어도, 과제로 어느정도 상쇄가 되었다고 생각한다. 만약 다음에 이직을 다시 시도한다면 (먼 미래였으면 좋겠다...) 과제 전형에 많이 도전해볼것 같다

시간을 많이 쓰긴 했지만 과제 하면서 많이 배웠다 특히 다중 인스턴스 환경이라면 어떻게 처리해야 하지? 이 기술 스택 선택을 했는데 내가 선택하려는 이유가 뭐지? 트레이드 오프가 뭐지? 정말 다양하고 치열한 고민들을 과제 하는 내내 할 수 있기에 스트레스도 많이 받지만 (아 이러고 떨어지면 정말 ^_^) 좋은 경험이었다고 생각한다 실제로 이렇게 고생하고 떨어지기 싫어서 밤새워서 과제를 진행했었다

면접

• 기술 면접은 대비하기 위해 정말 많은 공부가 필요했다 .. ㅎ 우선 프로젝트에 대한 질문에 대답을 못하는 일은 죽어도! 없어야 한다고 생각해서 이력서 파생 개념들부터 미친듯이 공부했다 블로그 글들도 찾아보고 특히 클로드 선생님의 도움을 정말 많이 받았다

• 이력 관련 질문이 들어왔을 때도, 이력서 내용처럼 최대한 상황 > 과정 > 성과 > 배운점(임원면접) 순으로 말하기 연습을 했다

• https://excalidraw.com/ 요기에 이력 정리해두는 걸 추천한다 그림으로 그려두면, 말할 때 딱히 스크립트 외울 필요 없이 내용이 잘 떠오른다

• 임원 면접은 솔직히 걱정 별로 안했다 물론 보기 전에 사시나무 떨듯이,,, 긴장했긴 하지만 평소에 어른들이 좋아하게,,, 말하는 법을 잘 안다고 생각한다 그리고 실제로 일했던 내용들이 기술만 파는 사람 < 비즈니스 매출을 올리기 위해 노력한 경험이 더 많아서 임원 면접에서는 조금은 유리했다고 생각한다 또 가치관을 말하는게 중요하다고 느꼈다 사실 정답이 없는 질문들이 많은데, 그럴 때 나는 이런 가치관을 가진 사람이라 이렇게 생각하는 편이다 라고 말하면 꼬리 질문들이 잘 들어오지 않는 것 같다 그리고 회사 조사를 최소 3-4시간 해갔던 것 같다

• 오히려 정말 힘들었던 부분은 지원 후 기다리는 시간이었다 특히 처음 지원했을 때는 열람도 너무 안하고 연락이 안와서 와 이거 퇴사 하면 안됐나 생각을 많이 했었는데 에라 모르겠다 하고 한 6군데 동시에 지원 하니까 거기서 연락이 갑자기 거의 전부.. 와서 놀랐었다 그래서 한 군데 면접을 포기해야 하기도 했다 멘탈 관리가 정말 중요하다,,는 걸 느꼈다

• 일정 조절 관리 실패로 과제 하나 끝나자마자 11/5 ~ 11/11 까지 5연 면접 봤었는데 주말에 생일 껴있어서 정말 스펙타클한 생일을 보냈다 내년 생일은 꼭 푹 쉬는,, 생일을 보내야지

재취업

그래서 어디를 가느냐라는 질문을 한다면 아직 완벽히 마음을 정하지 못했다 붙은 곳 중에 어딜 가더라도 너무 행복할 것 같아서 고민 중이다... 이렇게 남겨둬야 나 스스로 블로그 글을 또 쓰러 오겠지라는 생각에 지금 글을 작성한다 ㅎㅎ

가장 큰 틀의 고민은 네임 벨류 & 다양한 도메인 경험 VS 행복한 워라벨 & 앱의 전체 생애 주기 경험 인 것 같다 고민이 많지만 어떤 선택을 하더라도 내가 만족하고 행복한 개발 생활 할 수 있을 거란 확신이 있다

혹시 누군가 이 글을 보는 사람 중에 개발 이직 때문에 어려워하는 사람이 있다면 .. 특히 임원면접이 어렵다면.... 도움을 줄 수 있으니 (무료.) 메일로 연락해주셔도 감사할 것 같다 첫 회사 이직 당시 많은 도움을 받았어서 그걸 갚아나가고 싶은 마음이 크다

다음에는 꼭 이직 후기로 찾아와야지 😀

자바스크립트는 싱글 스레드 언어로, 동시에 하나의 작업만 실행할 수 있다. 그러나 실제 웹 애플리케이션에서는 다양한 비동기 작업(예: 네트워크 요청, 타이머 등)을 처리해야 한다. => 이 문제를 해결하기 위해 자바스크립트는 이벤트 루프라는 메커니즘을 사용.

호출 스택

• 호출 스택은 현재 실행 중인 함수와 함수 호출을 추적하는 자료 구조.
• 함수가 호출되면 스택의 맨 위에 추가되고, 함수 실행이 끝나면 스택에서 제거.

예시 1: 동기 작업

function first() {
  second();
  console.log("첫 번째");
}

function second() {
  third();
  console.log("두 번째");
}

function third() {
  console.log("세 번째");
}

first();

• 실행 순서: "세 번째" -> "두 번째" -> "첫 번째"
• 호출 스택

  third()
  second()
  first()
  anonymous  # 가상 전역 컨텍스트. 항상 존재

예시 2: 비동기 작업

function run() {
  console.log("3초 후 실행");
}

console.log("시작");
setTimeout(run, 3000);
console.log("끝");

• 실행 순서: "시작" -> "끝" -> "3초 후 실행"
• 이를 호출 스택만으로 이해하기는 무리가 있다 -> 이벤트 루프의 개념이 필요.

백그라운드

• 타이머, 네트워크 요청, I/O 작업 등 비동기 작업을 처리
• 비동기 작업 완료 시 콜백 함수가 테스크 큐로 이동

테스크 큐

• 비동기 작업의 콜백 함수를 대기하는 큐
• 호출 스택이 비어 있을 때 테스크 큐에 있는 콜백 함수가 호출 스택으로 이동되어 실행

이벤트 루프

• 호출 스택과 테스크 큐를 감시하며, 호출 스택이 비어 있으면 테스크 큐에서 대기 중인 콜백 함수를 호출 스택으로 이동시킴. 이를 통해 비동기 작업을 효과적으로 관리
• 이 때 테스크 큐에 Promise의 then/catch/finally 또는 process의 nextTick이 쌓이면 다른 테스크보다 우선 순위가 높아 먼저 호출 스택으로 호출됨. 정확히는 콜백함수들이 마이크로테스크큐에 쌓임.

Promise와 이벤트 루프와의 관계

• 자바스크립트에서 Promise는 비동기 작업을 관리하는 중요한 객체
• Promise의 then/finally/catch 등의 메서드는 비동기 작업이 완료된 후 실행할 콜백 함수를 등록 가능. 이러한 콜백 함수들은 마이크로 테스크 큐에 쌓인다.

console.log("Start");

let promise = new Promise((resolve, reject) => {
  setTimeout(() => {
    resolve("Success");
  }, 1000);
});

promise.then(result => {
  console.log(result); 
});

console.log("End");

• 실행 순서

1) anonymous 함수(전역 컨텍스트)가 호출 스택에 있음. 2) console.log('Start') 실행, 호출 스택에 추가되었다가 제거됨. 3) setTimeout 함수 호출, 호출 스택에 추가되었다가 제거됨. 백그라운드로 타이머가 설정됨. 4) console.log('End') 실행, 호출 스택에 추가되었다가 제거됨. 5) 타이머가 백그라운드에서 1초 후 만료됨. 6) 타이머 만료 후 resolve('Success') 콜백 함수가 테스크 큐로 이동. 7) 이벤트 루프가 호출 스택이 비어 있음을 확인하고, 테스크 큐에서 resolve('Success') 콜백을 호출 스택으로 이동하여 실행. 8) promise.then에 등록된 콜백이 호출 스택으로 이동하여 실행됨. 9) console.log('Success')가 호출 스택에 추가되었다가 제거됨.

마무리

• 이번 글을 통해 자바스크립트의 이벤트 루프와 비동기 작업에 대한 개념을 정리해 보았다. Vue나 React와 같은 프레임워크를 사용하여 화면을 만들 때, 비동기 작업의 작동 원리를 완벽히는 이해하지 못한 채 "이렇게 하면 되겠지"라고 생각하며 코드를 작성했던 경험이 있었던 것 같다.🤒

• 코드가 잘 동작하는 것에 만족하기보다는, 그 동작 원리를 깊이 이해하고 작성하는 습관을 가지는 것이 중요하다는 것을 다시 한 번 깨달았다. :)

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

예제 입력 1

2
6
12

예제 출력 1

3
16

생각

• 이런 문제는 규칙만 찾으면 금방이다,, 생각하고 그려진 삼각형들을 살펴보았다
• 바로 직전에 그린 삼각형의 변의 길이랑 "이전에 그린" 삼각형 하나의 변의 길이를 합쳐서 현재 변의 길이가 그려진다는 것을 깨닫고 "이전에 그린" 삼각형이 몇 step 이전인지를 찾아보았다
• 점화식

  P(N) = P(N-1) + P(N-5), N > 5

  

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Padovan {

    private static final int MAX = 100;
    private static long[] padovan = new long[MAX + 1];

    public long getNthNum(int n) {
        if (n <= 3) {
            return 1;
        } else if (n <= 5) {
            return 2;
        }

        if (padovan[n] != 0) {
            return padovan[n];
        }

        padovan[n] = getNthNum(n - 1) + getNthNum(n - 5);
        return padovan[n];
    }

    public static void main(String[] args) throws IOException {
        Padovan P = new Padovan();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < T; i++) {
            int n = Integer.parseInt(br.readLine());
            System.out.println(P.getNthNum(n));
        }
    }

}

• 재귀로 간단하게 풀 수도 있었지만, 불필요한 반복이 많이 일어날 것 같아서 (+ 시간 제한 1초가 무서웠다,,,!) DP로 구해 보았다!

문제 출처

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항

n은 1 이상 1,000 이하입니다.

입출력 예

생각

• 배열 초기화: 삼각형 모양이 되도록 2차원 동적 배열을 초기화

• 방향 설정: 현재 위치를 기준으로, 달팽이의 이동 방향을 3가지로 정의

  • 아래: (1,0) 행 번호 증가
  • 오른쪽: (0,1) 열 번호 증가
  • 위: (-1, -1) 행, 열 번호 감소

• 방향 전환: 삼각형의 경계를 만나면 방향 directionType 변경.

  directionType = (directionType + 1) % 3;

• 달팽이 이동: 달팽이가 이동할 때마다 원소의 값 num을 1씩 증가

  triangle[x][y] = num++;

• 결과 기록: 전체 원소의 개수 = n (n+ 1) / 2이므로 여기에 동적 배열을 돌면서 결과 기록

코드

public class TriangularSnail {

    static final int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, -1 } }; // 아래, 오른쪽, 위

    public int[] solution(int n) {

        int[][] triangle = new int[n][];
        for (int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
        }

        int num = 1;
        int x = 0, y = 0; // 시작 위치
        int directionType = 0; // 0: 아래, 1: 오른쪽, 2: 위

        while (num <= n * (n + 1) / 2) {
            triangle[x][y] = num++;

            int newX = x + dir[directionType][0];
            int newY = y + dir[directionType][1];

            if (newX >= 0 && newX < n && newY >= 0 && newY <= newX && triangle[newX][newY] == 0) {
                x = newX;
                y = newY;
            } else {
                // 방향 전환
                directionType = (directionType + 1) % 3;
                x = x + dir[directionType][0];
                y = y + dir[directionType][1];
            }
        }

        int[] answer = new int[(n * (n + 1)) / 2];

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

        return answer;
    }
}

정리

• 방향 전환을 구현하는 것이 핵심이었던 문제였다. 처음에는 코드의 이해를 쉽게 하기 위해서 방향을 0, 1, 2가 아닌 BELOW, RIGHT, UP과 같은 String으로 선언하는 방법도 생각해 보았지만, 방향 전환을 위한 새로운 메서드를 생성해야 하는 등 코드의 길이가 불필요하게 길어지는 문제가 발생했다. 결국, 간결성과 효율성을 유지하기 위해 방향을 정수 상수로 사용하는 것이 더 나은 선택이었다고 생각한다.

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.

제한사항

word의 길이는 1 이상 5 이하입니다. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

입출력 예

생각

• DFS를 사용하여 가능한 모든 조합을 탐색 -> target과 일치할 때까지 인덱스 cnt를 증가시킴
• 타깃 일치 또는 글자 길이 5 이상 시 탐색 종료

  DFS(cur #현재까지의 string + c #이번에 탐색할 char)

• 이전에 (약 6개월 전,,,) 동일한 문제를 풀었던 기록 => 모음 사전 이전 풀이이 있어 이전 풀이와도 비교해보았다. 생성 가능한 모든 단어를 리스트에 저장한 뒤 정렬하는 방식이라 확실히 메모리 사용량이 상당히 높았던 풀이라고 생각한다. 풀이가 개선된 걸 볼 때 뿌듯한 것 같다!!

코드

class Solution {
    private static final char[] vowels = {'A', 'E', 'I', 'O', 'U'};
    private boolean found = false;
    private int cnt = 0;


    private void DFS(String cur, String target){
        if (cur.equals(target)){
            found = true;
            return;
        } 
        if (cur.length() >= 5) return;

        for (char c : vowels){
            if (!found){
                cnt++;
                DFS(cur + c, target);
            }
        }
    }

    public int solution(String word) {
        DFS("", word); 
        return cnt;
    }
}

문제 출처

강을 가로지르는 하나의 차선으로 된 다리가 하나 있다. 이 다리를 n 개의 트럭이 건너가려고 한다. 트럭의 순서는 바꿀 수 없으며, 트럭의 무게는 서로 같지 않을 수 있다. 다리 위에는 단지 w 대의 트럭만 동시에 올라갈 수 있다. 다리의 길이는 w 단위길이(unit distance)이며, 각 트럭들은 하나의 단위시간(unit time)에 하나의 단위길이만큼만 이동할 수 있다고 가정한다. 동시에 다리 위에 올라가 있는 트럭들의 무게의 합은 다리의 최대하중인 L보다 작거나 같아야 한다. 참고로, 다리 위에 완전히 올라가지 못한 트럭의 무게는 다리 위의 트럭들의 무게의 합을 계산할 때 포함하지 않는다고 가정한다.

예를 들어, 다리의 길이 w는 2, 다리의 최대하중 L은 10, 다리를 건너려는 트럭이 트럭의 무게가 [7, 4, 5, 6]인 순서대로 다리를 오른쪽에서 왼쪽으로 건넌다고 하자. 이 경우 모든 트럭이 다리를 건너는 최단시간은 아래의 그림에서 보는 것과 같이 8 이다.

다리의 길이와 다리의 최대하중, 그리고 다리를 건너려는 트럭들의 무게가 순서대로 주어졌을 때, 모든 트럭이 다리를 건너는 최단시간을 구하는 프로그램을 작성하라.

입력

입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중을 나타낸다. 입력의 두 번째 줄에는 n개의 정수 a1, a2, ⋯ , an (1 ≤ ai ≤ 10)가 주어지는데, ai는 i번째 트럭의 무게를 나타낸다.

출력

출력은 표준출력을 사용한다. 모든 트럭들이 다리를 건너는 최단시간을 출력하라.

예제 입력 1

4 2 10
7 4 5 6

예제 출력 1

8

예제 입력 2

1 100 100
10

예제 출력 2

101

예제 입력 3

10 100 100
10 10 10 10 10 10 10 10 10 10

예제 출력 3

110

생각

• 트럭들이 다리를 순서대로 지나가고, 다리에 올라갈 수 있는 트럭의 수 제한(w)이 있으니, 다리를 큐로 선언하였다

• 다리의 길이만큼 큐를 0으로 채웠다. 여기서 숫자는 무게를 의미하고, 0은 다리위의 공간에 트럭이 없음을 의미한다

• 시간을 1씩 증가하면서 다리의 맨 앞에서 트럭을 꺼내 현재 다리의 무게를 갱신하고, 새로운 트럭의 무게와의 합이 L 이하이면 다리에 추가하고, 그렇지 않으면 0을 추가

• 🌟 모든 트럭이 다리에 진입하는 순간까지 반복하고, 마지막 트럭이 다리에 완전히 올라온 뒤 다리 길이만큼의 시간을 더해주어 마지막 트럭이 빠져나오는 시간을 구하였다 🌟

• 예시

코드

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

public class Truck {

    public int getMinTime(int n, int w, int L, int[] trucks) {
        Queue<Integer> bridge = new LinkedList<>();
        int currentWeight = 0;
        int time = 0;
        int index = 0;

        while (bridge.size() < w) {
            bridge.add(0);
        }

        while (index < n) {
            time++;
            currentWeight -= bridge.poll();

            if (currentWeight + trucks[index] <= L) {
                bridge.add(trucks[index]);
                currentWeight += trucks[index];
                index++;
            } else {
                bridge.add(0);
            }
        }

        return time + w;

    }

    public static void main(String[] args) throws IOException {
        Truck T = new Truck();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] firstLine = br.readLine().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int w = Integer.parseInt(firstLine[1]);
        int L = Integer.parseInt(firstLine[2]);

        String[] secondLine = br.readLine().split(" ");
        int[] trucks = new int[n];
        for (int i = 0; i < n; i++) {
            trucks[i] = Integer.parseInt(secondLine[i]);
        }

        System.out.println(T.getMinTime(n, w, L, trucks));
    }
}

생각

• 처음에 마지막 트럭이 다리를 빠져나오는 시간이 아닌, 다리위에 올라오는 시간으로 구해서 예제 입력에 대한 답이 맞지 않았었다.
• 문제를 제대로 풀어놓고 마지막에 놓치지 않도록, 꼼꼼하게 살펴봐야겠다고 생각했다!!

문제 출처

농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.

농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성이 높은 동영상을 추천 받을 수 있을 것이다.

존은 두 동영상이 서로 얼마나 가까운 지를 측정하는 단위인 “USADO”를 만들었다. 존은 N-1개의 동영상 쌍을 골라서 직접 두 쌍의 USADO를 계산했다. 그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것이 방해될까 봐 걱정하고 있다! 그래서 그는 K를 적절한 값으로 결정하려고 한다. 농부 존은 어떤 K 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.

입력

입력의 첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ Q ≤ 5,000)

다음 N-1개의 줄에는 농부 존이 직접 잰 두 동영상 쌍의 USADO가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 pi, qi, ri (1 ≤ pi, qi ≤ N, 1 ≤ ri ≤ 1,000,000,000)를 포함하는데, 이는 동영상 pi와 qi가 USADO ri로 서로 연결되어 있음을 뜻한다.

다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 ki와 vi(1 ≤ ki ≤ 1,000,000,000, 1 ≤ vi ≤ N)을 포함하는데, 이는 존의 i번째 질문이 만약 K = ki라면 동영상 vi를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

출력

Q개의 줄을 출력한다. i번째 줄에는 농부 존의 i번째 질문에 대한 답변이 출력되어야 한다.

예제 입력 1

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

예제 출력 1

3
0
2

생각

• 특정 동영상과 연관 동영상은 USADO 라는 측정값에 의해 연결됨으로 이 정보 즉 weight 를 담을 수 있게 새로운 class Edge 를 선언하였다. 연관 동영상의 번호 즉 node와 연관성 weight를 담고 있다.
• 동영상이 조건을 만족하는지 시작 노드로부터 점점 먼 거리로 나가며 탐색하기 때문에 BFS의 사용이 적합하다고 판단하였다.
• 인접 행렬을 사용하기에는 N의 범위가 5000까지 커질 수 있기 때문에 메모리의 낭비가 커서 인접 리스트를 사용하였다.

코드

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

public class MooTube {

    static class Edge {
        private int node;
        private int weight;

        Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    public int BFS(ArrayList<ArrayList<Edge>> graph, int N, int V, int K) {
        boolean[] visited = new boolean[N + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(V);
        visited[V] = true;
        int cnt = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for (Edge edge : graph.get(cur)) {
                if (!visited[edge.node] && edge.weight >= K) {
                    queue.add(edge.node);
                    visited[edge.node] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        MooTube T = new MooTube();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int N = nums[0];
        int Q = nums[1];

        ArrayList<ArrayList<Edge>> graph = new ArrayList<>();

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
        }

        for (int i = 0; i < N - 1; i++) {
            int[] tmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            graph.get(tmp[0]).add(new Edge(tmp[1], tmp[2]));
            graph.get(tmp[1]).add(new Edge(tmp[0], tmp[2]));
        }

        for (int i = 0; i < Q; i++) {
            int[] questions = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

            int K = questions[0];
            int V = questions[1];

            System.out.println(T.BFS(graph, N, V, K));
        }
    }
}

문제 출처

• 한 엔티티가 같은 엔티티의 다른 인스턴스를 참조하는 방식. 조직 구조나 카테고리 계층과 같은 계층적 데이터를 표현할 때 유용

• 하지만 자기 참조 구조는 잘못 관리될 경우 무한 순환 참조라는 문제 발생 가능 -> 데이터베이스 쿼리가 무한 루프에 빠짐

무한 순환 참조 예시

WITH RECURSIVE CategoryPath AS (
    SELECT category_id, name, parent_category_id
    FROM Categories
    WHERE name = '필기구' -- 시작 카테고리

    UNION ALL

    SELECT c.category_id, c.name, c.parent_category_id
    FROM Categories c
    INNER JOIN CategoryPath cp ON cp.parent_category_id = c.category_id
)
SELECT * FROM CategoryPath;

• 위와 같이 필기구 카테고리에서 시작하여 부모 카테고리를 계속해서 추적해 나갈 경우, 필기구의 부모인 도구가 다시 필기구를 부모를 참조하고 있기 떄문에 필기구와 도구가 무한히 반복하여 조회된다.

해결 방법

• 먼저 고객과의 prototype을 기반한 meeting 결과 시스템의 복잡성을 관리하기 위해 카테고리의 최대 깊이를 3으로 제한하였다.
• 또한 카테고리 생성/수정 시에 깊이 제한과, 순환 참조의 발생을 방지하는 로직을 추가하여 데이터의 정합성을 유지하였다.

예시: 카테고리 수정

@Transactional
public CommonRes patchCategory(String categoryCode, CategoryPatch patchInput) {
    Category previousCategory = commonUtil.findCategoryByCode(categoryCode);

    if (patchInput.getParentCategoryCode() != null) {
        Category parentCategory = categoryRepository.findByCategoryCode(patchInput.getParentCategoryCode());
        if (parentCategory == null) {
            return new CommonRes(ResponseCode.NOT_FOUND.getCode(), "부모 카테고리를 찾을 수 없습니다.");
        }
        if (getCategoryDepth(parentCategory) >= 2) {
            return new CommonRes(ResponseCode.BAD_REQUEST.getCode(), "카테고리 깊이가 3을 초과하였습니다.");
        }
        if (isCircularReference(parentCategory, categoryCode)) {
            return new CommonRes(ResponseCode.BAD_REQUEST.getCode(), "서로를 부모 카테고리로 가질 수 없습니다.");
        }
    }
    // 카테고리 업데이트 로직 (생략)
}

    private int getCategoryDepth(Category category) {
        int depth = 0;
        Category current = category;
        while (current.getParentCategory() != null) {
            depth++;
            current = current.getParentCategory();
            if (depth == 2) {
                break;
            }
        }
        return depth;
    }

    private boolean isCircularReference(Category category, String targetCategoryCode) {
        Category current = category;
        while (current != null) {
            if (current.getCategoryCode().equals(targetCategoryCode)) {
                return true;
            }
            current = current.getParentCategory();
        }
        return false;
    }

추가

• 애플리케이션 레벨에서 순환 참조를 방지할 수도 있지만, 데이터베이스 레벨에서도 제약 조건을 설정할 수 있다고 한다.
• 데이터베이스 트리거나 프로시저를 사용하여, 순환 참조나 깊이 제한 로직을 데이터베이스 레벨에서 직접 처리할 수 있다. 이 방법은 코드의 복잡성을 줄여줄 수 있지만, 변경사항을 추적하거나 업데이트하기 어렵고, 디버깅과 테스트가 어렵다는 단점이 존재.

PR 링크: Fix category self recursive error

하루 종일 내리는 비에 세상이 출렁이고 구름이 해를 먹어 밤인지 낮인지 모르는 어느 여름 날

잠 들기 싫어 버티던 호석이는 무거운 눈꺼풀에 패배했다. 정신을 차려보니 바닥에는 격자 모양의 타일이 가득한 세상이었고, 각 타일마다 알파벳 소문자가 하나씩 써있다더라. 두려움에 가득해 미친듯이 앞만 보고 달려 끝을 찾아 헤맸지만 이 세상은 끝이 없었고, 달리다 지쳐 바닥에 드러누우니 하늘에 이런 문구가 핏빛 구름으로 떠다니고 있었다.

• 이 세상은 N행 M열의 격자로 생겼으며, 각 칸에 알파벳이 써있고 환형으로 이어진다. 왼쪽 위를 (1, 1), 오른쪽 아래를 (N, M)이라고 하자.
• 너는 아무 곳에서나 시작해서 상하좌우나 대각선 방향의 칸으로 한 칸씩 이동할 수 있다. 이 때, 이미 지나 왔던 칸들을 다시 방문하는 것은 허용한다.
• 시작하는 격자의 알파벳을 시작으로, 이동할 때마다 각 칸에 써진 알파벳을 이어 붙여서 문자열을 만들 수 있다.
• 이 곳의 신인 내가 좋아하는 문자열을 K 개 알려줄 터이니, 각 문자열 마다 너가 만들 수 있는 경우의 수를 잘 대답해야 너의 세계로 돌아갈 것이다.
• 경우의 수를 셀 때, 방문 순서가 다르면 다른 경우이다. 즉, (1,1)->(1,2) 로 가는 것과 (1,2)->(1,1) 을 가는 것은 서로 다른 경우이다.

호석이는 하늘을 보고서 "환형이 무엇인지는 알려달라!" 며 소리를 지르니 핏빛 구름이 흩어졌다가 모이며 아래와 같은 말을 그렸다.

• 너가 1행에서 위로 가면 N 행으로 가게 되며 반대도 가능하다.
• 너가 1열에서 왼쪽으로 가면 M 열로 가게 되며 반대도 가능하다.
• 대각선 방향에 대해서도 동일한 규칙이 적용된다. 하늘에 아래와 같은 그림을 구름으로 그려줄 터이니 이해해 돕도록 하여라.
• 예를 들어서, 너가 (1, 1)에서 위로 가면 (N, 1)이고, 왼쪽으로 가면 (1, M)이며 왼쪽 위 대각선 방향으로 가면 (N, M)인 것이다.

세상을 이루는 격자의 정보와, K 개의 문자열이 주어졌을 때, 호석이가 대답해야 하는 정답을 구해주도록 하자.

입력

첫번째 줄에 격자의 크기 N, M과 신이 좋아하는 문자열의 개수 K 가 주어진다.

다음에 N개의 줄에 걸쳐서 M개의 알파벳 소문자가 공백없이 주어진다. 여기서의 첫 번째 줄은 1행의 정보이며, N 번째 줄은 N행의 정보이다.

이어서 K개의 줄에 걸쳐서 신이 좋아하는 문자열이 주어진다. 모두 알파벳 소문자로 이루어져 있다.

출력

K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다.

제한

• 3 ≤ N, M ≤ 10, N과 M은 자연수이다.
• 1 ≤ K ≤ 1,000, K는 자연수이다.
• 1 ≤ 신이 좋아하는 문자열의 길이 ≤ 5
• 신이 좋아하는 문자열은 중복될 수도 있다.

예제 입력 1

3 3 2
aaa
aba
aaa
aa
bb

예제 출력 1

56
0

예제 입력 2

3 4 3
abcb
bcaa
abac
aba
abc
cab

예제 출력 2

66
32
38

생각

• 문제가 길고 복잡하게 '환형'에 대해 설명되어 있지만,, 결국 이동 시 map 범위(0N-1, 0M-1) 넘어가면 반대편 끝으로 넘어가면 된다
• 인덱스 1부터 시작하면 헷갈려서 문제 풀 떄 0부터 시작하게 하고 풀었다!
  • (0,0) 위치에서 (-1, -1)만큼 이동 = (-1 + N, -1 + M) 위치로 이동
  • (N-1, M-1) 위치에서 (1, 0)만큼 이동 = (N-1+1 -N, M-1)= (0, M-1) 위치로 이동

    int dx = (x + d[0] + N) % N;
    int dy = (y + d[1] + M) % M;

• target 문자열을 만들 수 있는지 순서대로 check해야 하므로 깊이 우선 탐색(DFS)를 사용하였다
• 문자열의 길이가 최대 5글자라서 혹시,, 메모이제이션 없어도 되나? 하고 시도했으나 바로 시간초과가 발생했다. 그래서 메모이제이션도 적용해보았다.

memo[n][m][l] = (n, m) 위치에서 시작하여 타겟의 l 번째 문자에 도달했을 떄까지의 경우의 수

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class StringHell {

    private static int N, M, K;
    private static char[][] map;
    private static int[][][] memo;
    private static final int MAX_WORD_LENGTH = 5;

    static final int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { 1, -1 }, { -1, 1 }, { -1, -1 } };

    public int DFS(int L, int x, int y, char[] target) {
        if (L == target.length - 1) {
            return 1;
        }
        if (memo[x][y][L] != -1) {
            return memo[x][y][L];
        }

        int cnt = 0;
        for (int[] d : dir) {
            int dx = (x + d[0] + N) % N;
            int dy = (y + d[1] + M) % M;
            if (map[dx][dy] == target[L + 1]) {
                cnt += DFS(L + 1, dx, dy, target);
            }
        }

        memo[x][y][L] = cnt;
        return cnt;
    }

    public static void main(String[] args) throws IOException {
        StringHell T = new StringHell();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] nums = br.readLine().split(" ");
        N = Integer.parseInt(nums[0]);
        M = Integer.parseInt(nums[1]);
        K = Integer.parseInt(nums[2]);

        map = new char[N][M];
        memo = new int[N][M][MAX_WORD_LENGTH];

        for (int n = 0; n < N; n++) {
            char[] words = br.readLine().toCharArray();
            for (int m = 0; m < M; m++) {
                map[n][m] = words[m];
            }
        }

        for (int i = 0; i < K; i++) {
            for (int n = 0; n < N; n++) {
                for (int m = 0; m < M; m++) {
                    for (int l = 0; l < MAX_WORD_LENGTH; l++) {
                        memo[n][m][l] = -1;
                    }
                }
            }
            char[] target = br.readLine().toCharArray();
            int cnt = 0;
            for (int n = 0; n < N; n++) {
                for (int m = 0; m < M; m++) {
                    if (map[n][m] == target[0]) {
                        cnt += T.DFS(0, n, m, target);
                    }
                }
            }
            System.out.println(cnt);
        }
    }

}

• 채점 결과 1행: 메모이제이션 적용 / 2행: 메오이제이션 미적용

문제 출처

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

예제 입력 1

7
1
5
2
10
-99
7
5

예제 출력 1

1
1
2
2
2
2
5

생각

• 매번 정렬 후 중간 값을 찾는 것은 너무 당연하게,, 시간초과가 발생한다. (시간제한:0.1 초)

• 처음에는 priority queue를 하나 선언한 뒤, 수들의앞의 절반을 stack에 잠시 덜어놓았다가 다시 add하는 방법으로 문제를 풀고자 하였으나 시간초과가 발생하였다

• 그래서 우선 순위 큐 2개를 사용하였다. 큐는 index 접근이 안되니, 숫자들의 상위 50%와 하위 50%를 각각 담당하는 우선 순위 큐 (최대힙, 최소힙) 2개를 선언하였다

• 우선순위큐 정의

  1. maxHeap: 숫자들의 하위 50% 담당 최대힙. 정답은 이 maxHeap의 root값에 해당
  2. minHeap: 숫자들의 상위 50% 당당 최소힙

• 두 힙의 사이즈가 같은 경우 maxHeap에 offer, 다를 경우 minHeap에 offer

• minHeap과 maxHeap이 각각 숫자들의 상위 절반과 하위 절반을 담고 있어야 하므로 힙이 비어있지 않고, minHeap.peek() < maxHeap.peek() 라는 잘못된 로직이 성립되는 경우 각 heap의 root값을 교체해주어야 한다

• 항상 maxHeap의 root값을 return

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class TellMiddlePart {

    public String tellMiddle(int[] arr) {

        StringBuilder sb = new StringBuilder();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int i = 0; i < arr.length; i++) {
            if (minHeap.size() == maxHeap.size())
                maxHeap.offer(arr[i]);
            else
                minHeap.offer(arr[i]);

            if (!minHeap.isEmpty() && !maxHeap.isEmpty())
                if (minHeap.peek() < maxHeap.peek()) {
                    int tmp = minHeap.poll();
                    minHeap.offer(maxHeap.poll());
                    maxHeap.offer(tmp);
                }

            sb.append(maxHeap.peek() + "\n");
        }
        return sb.toString();

    }

    public static void main(String[] args) throws IOException {

        TellMiddlePart T = new TellMiddlePart();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(T.tellMiddle(arr));
    }

}

문제 출처

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍멍이보다 키가 작기 때문에 멍멍이를 쓰다듬어줄 수 없다. 원숭이가 멍멍이를 쓰다듬으려면 둘의 키가 같아야 하기 때문이다.

그래서 원숭이는 그 날부터 자신의 키를 조절하기로 마음먹었다. 원숭이는 초능력자이기 때문에 마음대로 키를 늘릴 수 있다. 하지만 안타깝게도 사람이 아니라 동물이기 때문에 하루에 늘릴 수 있는 키의 양을 1cm밖에 조절할 수 없다. 예를 들어 오늘 키를 5cm 만큼 늘렸다면, 내일은 키를 4cm, 5cm, 6cm 중 하나만큼 키를 늘릴 수 있다는 뜻이다. 늘릴 수 있는 키의 양은 음수가 될 수 없다. 그리고 첫째 날과 마지막 날에는 무조건 1cm 만큼 늘릴 수 있다.

현재 원숭이와 멍멍이의 키가 주어졌을 때, 원숭이가 매일 키를 늘려서 멍멍이와 키가 같아지는 최소의 일수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 원숭이의 키 X와 멍멍이의 키 Y가 주어진다. X, Y는 0 ≤ X ≤ Y < 231을 만족하는 정수이다.

출력

첫째 줄에 원숭이가 멍멍이의 키와 같아지게 되는 최소의 일수를 출력한다.

예제 입력 1

45 49

예제 출력 1

3

예제 입력 2

45 50

예제 출력 2

4

생각

• diff = 원숭이의 키와 멍멍이의 키 차이
• diff가 1~3인 경우, 첫날과 마지막날의 키 증가량은 1cm이므로 diff에 해당하는 값이 최소 일수.
• diff가 4 이상인 경우, 키 증가량은 매일 1cm씩 증가할 수 있으므로 cur을 현재 키 증가량의 기준점으로 두고 다음과 같이 계산:
  1. 첫 2일 동안 키 증가량은 각각 1cm. 따라서 minDays를 2로 설정하고, diff에서 2를 빼서 초기화.
  2. cur을 1로 설정하고, 반복문을 시작
  3. diff가 cur + 1 이하인 경우: minDays에 1을 추가, 반복 종료
  4. diff가 (cur + 1) * 2보다 작은 경우: minDays에 2를 추가, 반복 종료
  5. diff가 (cur + 1) * 2 이상인 경우: cur을 1씩 증가 (키 증가량을 증가시킴). minDays에 2를 추가하고, diff에서 해당 키 증가량을 빼는 방식으로 반복.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class PettingPuppy {

    public int getMinNumberOfDays(int monkey, int puppy) {

        int diff = puppy - monkey;
        if (diff <= 3)
            return diff;

        int minDays = 2;
        diff -= 2;
        int cur = 1;

        while (diff > 0) {
            if (diff <= (cur + 1) * 2) {
                minDays++;
                if (diff > cur + 1) {
                    minDays++;
                }
                break;
            } else {
                diff = diff - (cur + 1) * 2;
                minDays += 2;
                cur++;
            }
        }

        return minDays;
    }

    public static void main(String[] args) throws IOException {
        PettingPuppy T = new PettingPuppy();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] line = br.readLine().split(" ");
        System.out.println(T.getMinNumberOfDays(Integer.parseInt(line[0]), Integer.parseInt(line[1])));
    }

}

추가

• 다른 사람의 풀이들을 살펴보니 대부분 제곱수(ex 4, 9, 16...)를 사용해서 문제를 풀었다: 참조한 다른 사람의 블로그
• 제곱수보다 1 커졌을 때 항상 minDays가 1일 이용한다는 규칙을 사용해서 diff보다 작거나 같은 최대 제곱수를 찾고, 그 이후를 계산하는 방식이다. 시간 복잡도를 줄일 수 있다는 점에서 좋은 방식이라고 생각하였다!

문제 출처

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

예제 입력 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

4 3

생각

• 백준 1012번 유기농 배추 문제 생각이 났다. R과 G를 같게 보는 case와 다르게 보는 case 2가지가 있다는 점을 제외하면 거의 완벽히 동일한 문제이다
• BFS로 문제를 풀어보았다. 적록색약인 경우(R=G)와 적록색약이 아닌 경우(R!=G)를 구분하기 위해 flag isGlaze값을 사용하였다.
• 적록색약인 경우와 아닌 경우 각각 normalDist, glazeDist 2차원 배열을 선언해서 구역의 개수를 BFS로 탐색하며 저장하였다:

코드

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

public class RedGreenGlaze {

    static int N;
    static char[][] map;
    static int[][] normalDist;
    static int[][] glazeDist;
    static int normalCnt = 0;
    static int glazeCnt = 0;

    static final int[][] DIR = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private void BFS(int[][] dist, int x, int y, boolean isGlaze, int cnt) {
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x, y));
        dist[x][y] = cnt;

        while (!Q.isEmpty()) {
            Point cur = Q.poll();

            for (int[] d : DIR) {
                int dx = cur.x + d[0];
                int dy = cur.y + d[1];

                if (dx >= 0 && dx < N && dy >= 0 && dy < N && dist[dx][dy] == 0) {
                    boolean shouldAdd = !isGlaze
                            ? map[dx][dy] == map[cur.x][cur.y]
                            : !isDifferent(dx, dy, cur.x, cur.y);

                    if (shouldAdd) {
                        dist[dx][dy] = cnt;
                        Q.offer(new Point(dx, dy));
                    }
                }
            }
        }
    }

    private boolean isDifferent(int x, int y, int dx, int dy) {
        return map[x][y] == 'B' && map[dx][dy] != 'B'
                || map[x][y] != 'B' && map[dx][dy] == 'B';
    }

    public static void main(String[] args) throws IOException {
        RedGreenGlaze T = new RedGreenGlaze();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        normalDist = new int[N][N];
        glazeDist = new int[N][N];

        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                map[i][j] = line[j];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (normalDist[i][j] == 0) {
                    normalCnt++;
                    T.BFS(normalDist, i, j, false, normalCnt);
                }

                if (glazeDist[i][j] == 0) {
                    glazeCnt++;
                    T.BFS(glazeDist, i, j, true, glazeCnt);
                }
            }
        }

        System.out.println(normalCnt + " " + glazeCnt);
    }
}

추가

• 처음 normalDist와 glazeDist 배열을 선언한 이유는 여기에 구역 번호를 붙여 구역 번호의 최댓값을 가져오기 위함이었다
• 하지만, 구역 번호의 최댓값을 구하기 위해 또 2차원 배열을 탐색하면 시간 복잡도가 늘어나기에 normalCnt와 glazeCnt 2개의 카운터를 사용해서 구역의 수를 구하였다
• 이에 normalDist와 glazeDist를 선언하는 대신 normalVisited와 glazeVisited 변수를 선언하여 방문 여부만 기록하여 개선할 수 있겠다는 생각이 들었다!

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

public class RedGreenGlaze {

    static int N;
    static char[][] map;
    static boolean[][] normalVisited;
    static boolean[][] glazeVisited;

    static final int[][] DIR = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };

    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private void BFS(boolean[][] visited, int x, int y, boolean isGlaze) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point cur = queue.poll();

            for (int[] d : DIR) {
                int dx = cur.x + d[0];
                int dy = cur.y + d[1];

                if (dx >= 0 && dx < N && dy >= 0 && dy < N && !visited[dx][dy]) {
                    boolean isSame = !isGlaze
                        ? map[dx][dy] == map[cur.x][cur.y]
                        : !isDifferent(dx, dy, cur.x, cur.y);

                    if (isSame) {
                        visited[dx][dy] = true;
                        queue.offer(new Point(dx, dy));
                    }
                }
            }
        }
    }

    private boolean isDifferent(int x, int y, int curX, int curY) {
        return (map[x][y] == 'B' && map[curX][curY] != 'B') 
                || (map[x][y] != 'B' && map[curX][curY] == 'B');
    }

    public static void main(String[] args) throws IOException {
        RedGreenGlaze T = new RedGreenGlaze();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        normalVisited = new boolean[N][N];
        glazeVisited = new boolean[N][N];

        int normalCnt = 0;
        int glazeCnt = 0;

        for (int i = 0; i < N; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < N; j++) {
                map[i][j] = line[j];
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!normalVisited[i][j]) {
                    normalCnt++;
                    T.BFS(normalVisited, i, j, false);
                }

                if (!glazeVisited[i][j]) {
                    glazeCnt++;
                    T.BFS(glazeVisited, i, j, true);
                }
            }
        }

        System.out.println(normalCnt + " " + glazeCnt);
    }
}

• 1행이 개선 후(visited 사용), 2행이 개선 전이다(dist 사용) 메모리와 실행 속도 측면에서 약간의 개선이 되었음을 확인 할 수 있었다. : )

문제 출처

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.

하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.

우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.

자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다. 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다. 이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.

아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?

입력

첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.

각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.

20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.

모든 테스트 케이스는 독립적이다.

출력

각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

예제 입력 1

4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919

예제 출력 1

1 0
2 190
3 19
4 171

생각

• 2번째 사람부터 키 순으로 자신의 위치를 찾아 삽입하는 방식이므로 삽입 정렬을 구현하면 되는 문제였다
• 자신보다 큰 최초의 위치를 찾고(pos, 만약 못 찾으면 자기 자신) 자신 ~ pos까지의 위치를 뒤로 한 칸씩 밀어 line[j] = line[j - 1]; 삽입 정렬을 구현하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class LineUp {

    public int getMoveBackCnt(int[] tc) {
        int[] line = new int[21];
        int backCnt = 0;

        for (int i = 1; i <= 20; i++) {
            int cur = tc[i];
            int pos = 1;
            while (pos < i && line[pos] < cur) {
                pos++;
            }

            for (int j = i; j > pos; j--) {
                line[j] = line[j - 1];
            }

            line[pos] = cur;
            backCnt += (i - pos);
        }

        return backCnt;
    }

    public static void main(String[] args) throws IOException {
        LineUp T = new LineUp();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int P = Integer.parseInt(br.readLine());

        for (int i = 0; i < P; i++) {
            int[] tc = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            System.out.println(tc[0] + " " + T.getMoveBackCnt(tc));
        }

    }
}

정리

• 삽입 정렬 알고리즘

1. 배열의 첫 번째 요소를 이미 정렬된 것으로 간주
2. 다음 요소를 선택하고 이미 정렬된 배열 부분에서 올바른 위치를 찾아 삽입
3. 모든 요소 선택될때까지 2단계 반복

• 삽입 정렬 시간 복잡도 최악의 경우 O(N^2)에 해당. 최악의 경우 모든 이전 요소와 비교를 해야 한다. 하지만 배열이 거의 정렬된 경우, O(N) 의 최선의 시간 복잡도를 가질 수 있다

• 작언 데이터 set나 거의 정렬된 데이터를 대상으로 효율적이나, 데이터의 사이즈가 크거나, 정렬이 잘 되어있지 않은 경우 퀵 정렬 등의 다른 알고리즘을 사용하는 것이 더 효율적!

문제 출처

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1

3
10
20
40

예제 출력 1

100

생각

• 카드의 최소 비교 횟수를 구하기 위해서는 매 순간 가장 작은 두 묶음의 카드를 합쳐야 한다. 이를 위해 매번 새로 정렬할 수 없으니(1 ≤ N ≤ 100,000), 우선 순위 큐를 사용

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class CardSorting {

    public int getMinCnt(int N, int[] nums) {

        int minCnt = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int n : nums) {
            pq.offer(n);
        }

        while (pq.size() > 1) {
            int leastSum = pq.poll() + pq.poll();
            minCnt += leastSum;
            pq.offer(leastSum);
        }

        return minCnt;
    }

    public static void main(String[] args) throws IOException {
        CardSorting T = new CardSorting();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N];

        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(T.getMinCnt(N, nums));
    }
}

문제 출처

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

1+1+1+1
2+1+1 (1+1+2, 1+2+1)
2+2
1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

예제 입력 1

3
4
7
10

예제 출력 1

4
8
14

생각

• 만약에 합을 이루고 있는 수의 순서가 다른 것을 다른 것으로 친다면, 이는 DP로 아주 간단하게 풀 수 있는 문제이다 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
• 하지만 수의 순서만 다른 것을 같은 것으로 여기기 때문에, DP로 풀 때 3가지 경우로 나누어서 구해보았다. 현재 숫자 n보다 1 작을 때 1 중복 없이 더하는 경우, n 보다 2 작을 때 2를 중복 없이 더하는 경우, n보다 3 작을 때 3을 중복 없이 더하는 경우를 아래 표와 같이 나누어 구하였고, 점화식도 구해보았다!
• 마지막에 return할 때는 3가지 경우의 수를 모두 더해서 return하였다.

  dp[n][k] = n을 만들기 위해서 k를 마지막으로 더하는 경우의 수

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class OneTwoThreePlusFour {

    public int cntWays(int n) {

        if (n < 4) return n;

        int[][] dp = new int[n + 1][4];
        dp[1][1] = 1;
        dp[2][1] = 1;
        dp[2][2] = 1;
        dp[3][1] = 1;
        dp[3][2] = 1;
        dp[3][3] = 1;

        for (int i = 4; i <= n; i++) {
            dp[i][1] = dp[i - 1][1];
            dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
            dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
        }
        return dp[n][1] + dp[n][2] + dp[n][3];
    }

    public static void main(String[] args) throws IOException {
        OneTwoThreePlusFour T = new OneTwoThreePlusFour();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < num; i++) {
            int N = Integer.parseInt(br.readLine());
            System.out.println(T.cntWays(N));
        }
    }
}

• 시간초과 안나고 한번에 통과하였다,,,😚😚 확실히 DP를 사용하면 중복 계산을 피해서 연산 횟수를 대폭 감소시킬 수 있는 것 같다!

문제 출처

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

예제 입력 1

4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력 1

0

예제 입력 2

6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

예제 출력 2

2

생각

• 팀의 능력치 차의 최솟값을 구하려면 모든 팀 분배의 경우의 수를 다 구해봐야 한다 => DFS 로 풀어야겠다고 생각했다
• N개의 사람들 중에 N/2명은 스타트, N/2명은 링크 팀이니 두 팀의 구분을 visited[] 배열로 구분하였다.
• visited에 체크된 사람의 수가 N/2명이 되면 두 팀의 능력치 차이를 비교한 뒤 최솟값으로 갱신하였다
• 이 때 중복해서 팀을 나누지 않도록 DFS()에 parameter넘겨줄 때 현재 선택한 사람 번호보다 +1 더 큰 값을 넘겨주었다 (start 변수)

• 여담이지만,,,, Sij와 Sji가 왜 다를 수 있는지는 이해가 되지 않았다,,, 너무 문제를 위한 조건이지 않나ㅠ 라는 생각이 들었다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class StartLink {

    static int N;
    static int[][] S;
    static int[] visited;
    static int minDiff = Integer.MAX_VALUE;

    public void DFS(int L, int start) {
        if (minDiff == 0)
            return;

        if (L == N / 2) {
            int s = 0, l = 0;
            for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < N; j++) {
                    if (visited[i] == 1 && visited[j] == 1) {
                        s += S[i][j] + S[j][i];
                    } else if (visited[i] == 0 && visited[j] == 0) {
                        l += S[i][j] + S[j][i];
                    }
                }
            }
            minDiff = Math.min(minDiff, Math.abs(s - l));
        } else {
            for (int i = start; i < N; i++) {
                if (visited[i] == 0) {
                    visited[i] = 1;
                    DFS(L + 1, i + 1);
                    visited[i] = 0;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StartLink T = new StartLink();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        visited = new int[N];
        S = new int[N][N];

        for (int i = 0; i < N; i++) {
            int[] lines = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < N; j++) {
                S[i][j] = lines[j];
            }
        }

        T.DFS(0, 0);
        System.out.println(minDiff);
    }
}

추가

• 확실히 Scanner를 이용해서 input을 받을 때보다 BufferedReader를 사용하는 것이 시간 초과가 덜 발생하는 것 같다 다양한 종류의 input을 BufferedReader로 받을 수 있도록 꾸준히 연습해봐야겠다! : )

문제 출처

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

예제 입력 1

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력 1

[2,1]
error
[1,2,3,5,8]
error

생각

• 함수 여러 개 진행할 때마다 배열을 뒤집거나, 원소를 제거하는 것은 시간 복잡도가 지나치게 높아질 수 있다고 생각했다
  • 배열의 크기인 n의 범위가 (0 ≤ n ≤ 100,000)이기 때문
• 그래서 함수 (R 또는 D) 마다 새로운 배열 지정 대신, 2개의 포인터와 하나의 boolean값을 이용해 로직을 구성해보았다!

코드 (Two Pointer)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class AC {

    public String getResult(String p, int[] arr) {
        int start = 0, end = arr.length - 1;
        boolean reverse = false;

        for (char c : p.toCharArray()) {
            if (c == 'R') {
                reverse = !reverse;
            } else {
                if (end < start)
                    return "error";
                if (reverse)
                    end--;
                else
                    start++;
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        if (reverse) {
            for (int i = end; i >= start; i--) {
                sb.append(arr[i]);
                if (i > start)
                    sb.append(",");
            }
        } else {
            for (int i = start; i <= end; i++) {
                sb.append(arr[i]);
                if (i < end)
                    sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) throws IOException {
        AC ac = new AC();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < T; i++) {
            String p = br.readLine();
            int n = Integer.parseInt(br.readLine());

            String arrString = br.readLine().replace("[",
                    "").replace("]", "");

            int[] arr = new int[n];
            if (arrString.length() > 0) {
                arr = Arrays.stream(arrString.split(",")).mapToInt(Integer::parseInt)
                        .toArray();

            }
            System.out.println(ac.getResult(p, arr));
        }
    }
}

Deque 사용

• 문제를 다 풀고 나서 알고리즘 분류를 확인했더니 예상과 다르게 two pointer가 없었다,,! 찾아보니 Deque 즉 Double-Ended Queue를 이용하면 양쪽 끝에서 요소를 추가하거나 제거할 수 있다고 하여, Deque 방식으로 다시 풀어보았다 :)

  import java.util.ArrayDeque;
  import java.util.Deque;

  public String getResult(String p, int[] arr) {
        Deque<Integer> deque = new ArrayDeque<>();
        for (int value : arr) {
            deque.addLast(value);
        }

        boolean reverse = false;
        for (char c : p.toCharArray()) {
            if (c == 'R') {
                reverse = !reverse;
            } else {
                if (deque.isEmpty()) {
                    return "error";
                }
                if (reverse) {
                    deque.removeLast();
                } else {
                    deque.removeFirst();
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (!deque.isEmpty()) {
            sb.append(reverse ? deque.removeLast() : deque.removeFirst());
            if (!deque.isEmpty()) {
                sb.append(",");
            }
        }
        sb.append("]");
        return sb.toString();
    }

• Deque 추가적인 자료구조를 사용하여 공간 복잡도가 조금 더 복잡하긴 하지만 코드가 더 직관적이고, 확장에 유리할 것 같다는 생각이 들었다!!

• 실제로 Deque를 이용한 풀이(1행)이 Two Pointer를 사용한 풀이(2행)보다 메모리 사용량이 더 큰 것을 확인할 수 있다.

문제 출처

조규현과 백승환은 터렛에 근무하는 직원이다. 하지만 워낙 존재감이 없어서 인구수는 차지하지 않는다.

이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다.

조규현의 좌표 $(x_1, y_1)$와 백승환의 좌표 $(x_2, y_2)$가 주어지고, 조규현이 계산한 류재명과의 거리 $r_1$과 백승환이 계산한 류재명과의 거리 $r_2$가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

한 줄에 공백으로 구분 된 여섯 정수 $x_1$, $y_1$, $r_1$, $x_2$, $y_2$, $r_2$가 주어진다.

출력

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다.

제한

  $-10,000 ≤ x_1, y_1, x_2, y_2 ≤ 10,000$  $1 ≤ r_1, r_2 ≤ 10,000$ 

입력 1

3
0 0 13 40 0 37
0 0 3 0 7 4
1 1 1 1 1 5

예제 출력 1

2
1
0

생각

• 각 친구의 좌표를 원의 중심으로, 친구로부터 적의 거리를 원의 반지름으로 생각하고 보면, 원의 접점의 개수를 구하는 문제로 변하게 된다. (두 원의 위치 관계)
• 두 친구가 같은 위치에 서있을 때와 그렇지 않을 때(중심이 다를 때)를 크게 나누고 case를 아래 사진과 같이 나눠 조건을 분기하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Turret {

    static class Point {
        private int x;
        private int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static double getDistance(Point p1, Point p2) {
        int dx = p1.x - p2.x;
        int dy = p1.y - p2.y;

        return Math.sqrt(dx * dx + dy * dy);

    }

    public int cntPoint(Point p1, int r1, Point p2, int r2) {

        double d = getDistance(p1, p2);

        if (d == 0) {
            if (r1 == r2)
                return -1;
        } else {
            if (d == Math.abs(r1 - r2) || d == r1 + r2)
                return 1;
            else if (d > Math.abs(r1 - r2) && d < r1 + r2)
                return 2;
        }
        return 0;
    }

    public static void main(String[] args) throws IOException {
        Turret T = new Turret();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        for (int i = 0; i < N; i++) {
            int[] lines = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            Point p1 = new Point(lines[0], lines[1]);
            int r1 = lines[2];
            Point p2 = new Point(lines[3], lines[4]);
            int r2 = lines[5];

            System.out.println(T.cntPoint(p1, r1, p2, r2));
        }

    }
}

정리

• 오랜만에 푸는 수학 문제였다,,, 수학 문제 풀 때 Math 라이브러리를 종종 사용하는데 double 타입을 반환하는 경우가 있음을 기억하자

double 형 반환하는 Math 라이브러리 메서드

- Math.sqrt(a) // 제곱근 반환
- Math.sin(a), Math.cos(a), Math.tan(a) // 삼각함수값 반환
- Math.log(a) // 자연로그 a
- Math.exp(a)  // e^a
- Math.pow(a,b) // a^b

문제 출처

Scanner

입력받은 데이터(바이트)를 다양한 타입으로 변환하여 반환하는 클래스

• 사용이 간편하고 다양한 형태의 입력(문자열, 정수, 실수) 등을 쉽게 처리 가능. 하지만, 대량의 데이터 처리에는 속도가 다소 느린 편

예시

• 문자열 입력

  Scanner scanner = new Scanner(System.in);
  String line = scanner.nextLine();
  System.out.println("입력받은 문자열: " + line);
  

- 정수 배열, 실수 입력
```java
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); 
dobule m = scanner.nextDouble;
int[] numbers = new int[n];
for (int i = 0; i < n; i++) {
    numbers[i] = scanner.nextInt();
}
System.out.println(Arrays.toString(numbers));
System.out.println(m);

BufferedReader

데이터를 한번에 읽어와 버퍼에 보관한 후 버퍼에서 데이터를 읽어오는 방식으로 동작하는 클래스

• 버퍼를 사용하여 입력을 받기 때문에 대량의 데이터 빠르게 처리.
• 단, 문자열 입력만 직접적으로 지원하기 때문에 숫자와 같은 다른 타입의 입력을 처리하기 위해서는 추가적인 파싱 작업이 필요

예시

• 문자열 입력

  BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  String line = reader.readLine();
  System.out.println("입력받은 문자열: " + line);

• 정수 배열, 실수 입력

  BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  int n = Integer.parseInt(reader.readLine()); 
  double m = Double.parseDouble(reader.readLine());
  int[] numbers = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
  System.out.println(Arrays.toString(numbers));
  System.out.println("입력받은 실수: " + m);

  정리

• 간단한 입력 처리나 코드의 가독성이 좋은 경우에는 Scanner를 사용하는 것이 좋고, 대량의 데이터 처리 속도가 중요한 어플리케이션에서는 BufferedReader를 사용하는 것이 더 효율적이다.
• 그동안 입력을 받을 때는 주로 Scanner만 사용했었는데, 상황에 따라서 BufferedReader를 통한 입력도 고려해봐야겠다!!

참조

• 백준 > 언어 별 input 방식에 따른 입력 속도 비교

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

• X가 3으로 나누어 떨어지면, 3으로 나눈다.
• X가 2로 나누어 떨어지면, 2로 나눈다.
• 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

생각

• 숫자가 커질 수록 연산의 중복이 많아진다 예를 들어 10을 만들기 위해서는 10 -> 9 -> 3 -> 1 이렇게 3번의 연산이 필요한데, 9를 만드는데, 3을 만드는데 이미 연산의 횟수를 계산했었다. 이를 DP를 이용해 중복을 줄여보자!

• 점화식

코드

import java.util.Scanner;

public class MakeOne {
    static int N;
    static int[] dp;

    public int getMinOperationCnt(int N) {

        dp[1] = 0;

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i % 2 == 0)
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            if (i % 3 == 0)
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
        }
        return dp[N];
    }

    public static void main(String[] args) {
        MakeOne T = new MakeOne();
        Scanner kb = new Scanner(System.in);

        N = kb.nextInt();
        dp = new int[N + 1];

        System.out.println(T.getMinOperationCnt(N));
        kb.close();
    }
}

생각

• DP 문제 처음 봤을 때는 어려웠는데 확실히 숫자가 커져도 중복 계산을 피하기 위해 이전 계산 결과를 저장하기 때문에 OOM이 덜 발생하는 것 같다.
• 초기화 조건과 점화식만 잘 생각해서 DP로 문제를 풀수 없는지 검토를 해봐야겠다,,!

문제 출처