Computer Science Knowledge Storage

✨ 공부하며 성장하는 기록 공간입니다.
아직 부족한 점이 많고 배워야 할 것도 많지만, 그만큼 배우는 즐거움도 큽니다.
틀리거나 부족한 내용이 있다면 언제든지 편하게 지적해 주세요 😁

이 블로그는 SSAFY에서 공부한 내용들을 기록하는 공간입니다.
처음보다 성장해 있는 나 자신을 기대하며 꾸준히 기록해나가겠습니다!

긴장 그리고 자극

SSAFY에서의 첫 주가 마무리되었다. 사실 시작 전에는 기대감이 컸지만, 실제 입과하여
여러 과정을 진행하면서 실제로 긴장이 되고, 자극이 되는 것을 하루하루 체감하고 있다.

여러가지 규칙

SSAFY에서는 다소 엄격한 규칙이 존재한다고 생각한다. 오프라인 수업임에도, 출석체크, 시간 엄수 등 재수학원을 방불케하는 느낌이 들었다.

하지만 학습하러 오는 공간이라고 생각했을 때, 또한 취업을 준비하는 우리에게는 사칙에 대해 미리 준비하는 느낌이라는 생각에 당연하겠다라고도 생각이 들었다.

이러한 규칙은 오히려 나를 더 집중하게 만들고 마음가짐을 보다 더 굳건하게 다지는 계기가 되었다.

분반 테스트

분반 테스트는 나에게 약간의 스트레스를 안겨주었다. 잘 봐야 더 높은 반에 편성되고, 더 많은 것을 배울 수 있을 거라는 생각이 들었기 때문이다. 그래서 '이번 시험은 무조건 잘 봐야 한다'는 부담을 스스로 안고 있었다.

처음에는 "이걸 코딩 테스트처럼 알고리즘 위주로 준비해야 하나?"라는 고민도 들었다. 나는 컴퓨터 공학적인 지식에는 어느 정도 자신이 있었기 때문에, 이번 기회에 알고리즘 실력을 좀 더 다져야겠다고 다짐했었다. 하지만 전날 잠을 거의 자지 못한 탓에, 결국 공부는 계획처럼 되지 않았다. 스스로 핑계를 댔지만, 마음 한 켠에서는 아쉬움이 남았다.

다행히도, 분반 테스트는 단순히 반을 나누기 위한 평가가 아니라, 수준을 골고루 분배하기 위한 목적이라는 이야기를 듣고는 마음이 조금 놓였다. 시험을 치르는 내내 부담보다는 편안한 마음으로 임할 수 있었고, 알고리즘 중심의 문제라기보다는 기본적인 이해도를 확인하는 형식이라 오히려 나와 잘 맞는 구성이라고 느꼈다.

몇몇가지의 특강

이번 SSAFY 14기를 맞아, AI 수업이 추가되었다. 다양한 AI를 활용하는 수업이 있다보니 그에 따라 AI관련 특강도 많이 추가되었다고 한다. 그 중에서는 프롬프트 엔지니어링 특강이 특히 기억이 난다.

Chat GPT를 여태까지 사용하면서 귀찮다는 이유로 한글로 물어보고, 나 편한대로 질문을 했지만, 질문자의 프롬프트의 따라 결과값이 천차만별이라는 것도 나에게는 신선한 충격이였다. 이를 통해 여태까지 내가 사용했던 GPT를 더 잘 사용할 수 있겠다는 생각이 들었다.

선배들의 프로젝트 시연

이전 기수들의 프로젝트 발표를 하는 시간도 있었는데, 수준이 꽤나 높아서 흥미롭게 보았다. 나는 전공자임에도 완성도 높은 결과물에 놀라웠고, 대단했다. 특히 디자인, 사용자 경험, 기술 스택까지 완성도 높은 프로덕트를 실제로 사용하면서 "나는 더 완성도 높은 프로젝트를 만들어야겠다" 라는 목표가 생겼다.

AI 아이디어톤

이번 SSAFY 첫 주에는 단순한 교육을 넘어, AI를 활용해 문제를 정의하고 해결방안을 설계하는 ‘아이디어톤’ 활동이 있었다. 기존의 아이디어톤과 다른 점은, 단순히 아이디어를 떠올리는 데서 끝나는 것이 아니라 AI를 중심 도구로 삼아 아이디어를 구체화하고 실현 가능한 방향으로 설계하는 과정이 포함되어 있었다는 점이다.

특히 페르소나 설정 과정에서는, 단순히 '누구를 위한 서비스인가?'를 넘어서 그 사용자가 어떤 감정을 느끼고, 어떤 문제를 실제로 겪는지를 깊이 있게 고민해야 했다. 평소에 소프트웨어를 만들 때 기능 구현에만 집중했던 나에게는, 사용자 중심의 사고를 훈련하는 아주 신선한 경험이었다.

중간중간 팀별로 피드백을 주고받으며, 다른 팀들이 문제를 접근하는 시각과 해결방식을 공유하는 시간도 매우 유익했다. "아, 저런 방향으로도 생각할 수 있구나", "그 요소는 왜 중요하게 봤을까?" 같은 질문들이 자연스럽게 생기면서, 아이디어의 폭이 훨씬 넓어지는 것을 느꼈다.

비록 결과적으로는 수상까지 이어지진 않았지만, 발표의 구조를 어떻게 짜야 하는지, 청중을 어떻게 설득해야 하는지에 대해 실질적인 감을 잡을 수 있었다. 이 경험은 향후 프로젝트 발표나 데모데이 같은 중요한 자리에서 큰 자산이 될 것이라 생각한다.

무엇보다도, 아이디어톤 내내 강사님께서 해주신 “완성도보다는 사고의 방향이 중요하다”, “지금 단계에서는 시도하는 것 자체가 의미 있다”는 말씀들이 큰 동기부여가 되었다. 단순히 결과 중심의 사고에서 벗어나, 과정을 통한 성장을 경험할 수 있는 소중한 시간이었다.

마무리하며

이번 첫 주를 포함해 다음 주까지는 오리엔테이션 형식의 프로그램으로 진행된다고 한다. 짧은 시간이었지만, 다양한 활동과 강의들을 통해 느슨해졌던 취업 준비에 대한 마음가짐을 다시 붙잡을 수 있었다. 무엇보다 SSAFY라는 새로운 환경 속에서, 비슷한 목표를 가진 동료들과 함께 시간을 보내며 나 자신을 다시 한번 다잡게 되는 계기가 되었다.

매일 아침 9시부터 저녁 6시까지 이어지는 타이트한 일정 속에서도, 각자의 자리에서 열심히 임하는 사람들을 보며 긍정적인 자극을 받을 수 있었다. 앞으로 이들과 함께 의미 있는 프로젝트를 만들어가고, 개발자로서뿐만 아니라 사람 대 사람으로도 좋은 관계를 이어가며 성장해 나갈 것이다.

✨ 공부하며 성장하는 기록 공간입니다.
아직 부족한 점이 많고 배워야 할 것도 많지만, 그만큼 배우는 즐거움도 큽니다.
틀리거나 부족한 내용이 있다면 언제든지 편하게 지적해 주세요 😁

이 블로그는 오픈소스 프로젝트 githru-vscode-extension을 공부하고 기여한 내용을 정리한 공간입니다.
처음보다 성장해 있는 나 자신을 기대하며 꾸준히 기록해나가겠습니다!

작년에 이어, 올해도 오픈소스 컨트리뷰션 아카데미에 참여하였다.

작년에는 체험형으로 Redis의 구조에 대해서 학습은 하였지만 실제 기여로 이어지지 않았던 것에 대한 아쉬움이 남아

올해 다시한번 신청하게 되었고, 운이 좋게 합격하여 이번 발대식을 다녀왔다.

이번 발대식은 한국과학기술회관에서 진행되었다. 비록 사진은 못찍었지만, 들어가자마자 엄청 큰 전광판이
우리를 환영해주었으며, 지하에는 다양한 다과가 준비되어있었다.(커피까지 주는 지 모르고 커피를 사갔던...)

또한 드론을 통한 선물뽑기 기계와 어떤 게임(?)과 같은 것이 있어, 역시 SW관련 대외활동에 참여한 것을 실감하였다.

강연

발대식이 진행하였고, 주관 기관에 오프닝을 시작으로 발대식이 시작되었다. 그 중에서 인상깊었던 것은 글로벌 Maintainer의 강연이였다.

실제로, 외국 개발자의 강연을 처음들어서 압도당하는 것도 있었지만, 취준을 오래 진행해오고 있는 나에게는 여러가지 인사이트를 주었다.

그 중에서는 Hype Curve에 대한 것이 있었다.

비록 오픈소스에 대한 것이였지만, 인생에서도 마찬가지라고 생각이 들었다. 강연자님의 프로젝트를 요약하면

• 과대기대의 정점에 도달하려 애쓰는 과정에서 방향이 틀어질 수 있음.
• 환멸의 골짜기는 피할 수 없으며, 대비가 필요함.

이 것인데, 현재의 내 상황같아서 마음을 다잡게 되었다.

또한 국내 15년차 개발자분의 오픈소스의 대한 조언을 들었다.

기존 내가 오픈소스를 기여한 적이 있었지만, 그 부분에 대한 것들이 많았다.

테스트의 중요성, 파편화된 커밋, 커밋 메시지의 중요성 등.. 해당 부분들을 모두 지킨다면 훌륭한 컨트리뷰터가 되겠다라는 생각이 들었다.

팀 오리엔테이션

그 이후 각 팀과의 만남을 가졌다.

멘토님과의 인사하는 시간을 가졌고, 우리가 기여할 프로젝트의 개요와, 앞으로 어떻게 진행하게 될 것인지 등에 대해 설명해주셨고,

또한 멘티들의 3분 자기소개 시간을 가졌다.

새로운 사람들을 많이 만나는 것이 오랜만이라 조금 낯설기도 하였지만, 각자 어떠한 마음가짐으로 오픈소스 기여에 참여하게 되었는지, 무엇을 좋아하는지, 무엇을 하고 있는지 등 다양한 곳의 사람들을 만나면서 동기부여가 확실하게 되었다.

또한 비슷한 고민을 하고있는, 혹은 했었던 사람들과 만나다보니 다양한 인사이트를 얻을 수 있었다.

내가 OSSCA를 하는 다른 이유(인적 네트워킹)도 얻어갈 수 있을 것 같아 좋은 시간이였다.

후기

이젠 실제로 내가 기여를 할 차례이다. 내가 맡은 githru를 분석하면서 성능 및 기능 개발에 힘쓸 것이다.
처음 접하는 코드라 어렵고 낯설 수 있지만, 이해하려는 과정에서 많이 배우게 될 것이라 기대하고 있다.

단순히 코드만 보는 것이 아니라, 기존 기여자들의 커밋 메시지, 이슈 내용, PR 흐름 등을 분석하면서 프로젝트의 문화와 방향성도 함께 익히려고 한다.

이번 OSSCA 활동을 통해 단순히 기술적인 성장뿐 아니라, 오픈소스 생태계에서의 커뮤니케이션, 협업, 그리고 지속적인 학습의 자세도 키우고 싶다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 1812 수정이의 타일자르기입니다.

포인트

개인적으로 해당 문제가 조금 어려웠습니다.

타일을 자를때 하나의 타일에서 여러 타일을 만들 수도 있고, 못만드는 경우를 고려해야합니다.

그래서 저는 잘랐을 때의 타일을 저장하기로 하였습니다.

PriorityQueue를 활용하여 가장 큰 길이를 가진 타일을 나오도록 만들었습니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Q1812 {
    static class Tile implements Comparable<Tile> {

        int min, max;

        public Tile(int a, int b) {
            this.min = Math.min(a, b);
            this.max = Math.max(a, b);
        }

        @Override
        public int compareTo(Tile o) {
            return Integer.compare(o.min, this.min);
        }
    }
    private static int tc, N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            Integer[] length = new Integer[N];
            for (int i = 0; i < N; i++) {
                int b = Integer.parseInt(st.nextToken());
                length[i] = b;
            }
            Arrays.sort(length, Collections.reverseOrder());
            PriorityQueue<Tile> pq = new PriorityQueue<>();
            int ans = 1;
            pq.add(new Tile(M, M));
            for (int i = 0; i < N; i++) {
                Tile tile = pq.poll();
                int len = (1 << length[i]);
                if (tile.min >= len) {
                    pq.add(new Tile(tile.max - len, tile.min));
                    pq.add(new Tile(tile.min - len, len));
                } else {
                    pq.add(tile);
                    pq.add(new Tile(M - len, len));
                    pq.add(new Tile(M, M - len));
                    ans++;
                }
            }

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

코드 설명

static class Tile implements Comparable<Tile> {
    int min, max;

    public Tile(int a, int b) {
        this.min = Math.min(a, b);
        this.max = Math.max(a, b);
    }

    @Override
    public int compareTo(Tile o) {
        return Integer.compare(o.min, this.min); // 큰 min부터 우선
    }
}

• Tile 클래스 정의
  • 분할된 타일의 가로 세로를 담고, min 기준으로 내림차순 정렬되게 Comparable을 구성받아 구현하였습니다.
  • PriorityQueue에서 가장 적절한 위치에 타일을 배치하기 위한 기준입니다.

Arrays.sort(length, Collections.reverseOrder()); // 큰 타일부터 먼저 배치
PriorityQueue<Tile> pq = new PriorityQueue<>();
int ans = 1;
pq.add(new Tile(M, M));

• 입력받은 length[i]는 타일의 크기를 2^k으로 표현합니다
• 큰 타일부터 배치하기 위해 내림차순 정렬합니다.
• 하나의 큰 정사각형(M×M)을 처음으로 넣어줍니다.

for (int i = 0; i < N; i++) {
    Tile tile = pq.poll(); // 현재 가장 적절한 빈 공간
    int len = (1 << length[i]); // 실제 타일 길이 (2^k)

    if (tile.min >= len) {
        // 현재 타일이 현재 빈 공간에 들어갈 수 있으면
        pq.add(new Tile(tile.max - len, tile.min)); // 오른쪽 빈 공간
        pq.add(new Tile(tile.min - len, len));      // 아래쪽 빈 공간
    } else {
        // 현재 타일이 안 들어가면 새 정사각형 추가
        pq.add(tile); // 원래 꺼낸 공간 다시 넣기
        pq.add(new Tile(M - len, len)); // 새 공간에서 남은 오른쪽
        pq.add(new Tile(M, M - len));   // 새 공간에서 남은 아래쪽
        ans++;
    }
}

• 타일을 배치하고 남은 공간을 다시 Tile 객체로 분할하여 pq에 저장
• 만약 현재 가장 큰 빈 공간에도 타일이 안 들어가면, 새로운 정사각형이 필요하다는 것으로 
  • 이 때 ans++ 해서 필요한 정사각형 개수를 증가합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 3503 초보자를 위한 점프대 설치하기입니다.

포인트

해당 문제에서 구하라는 부분은 두 점프대의 높이차 중에서 가장 큰 값을 최소화하는 것입니다.

그래서 오름차순(내림차순)으로 정렬하면 차이가 적지 않나 라고 생각했지만, 점프대는 원형으로 설치하는 것이 문제입니다.

따라서 배열을 원형이라고 생각하여
배열의 0번의 왼쪽 인덱스는 N-1, 오른쪽 인덱스는 1로 생각하여 정렬된 기준으로 점프대의 높이를 설치합니다.

소스코드

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

public class Q3503 {
    private static int tc, N;
    private static Integer[] heights;

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

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            N = Integer.parseInt(br.readLine());
            heights = new Integer[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                heights[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(heights, Collections.reverseOrder());

            int idx = 0;
            int[] ans = new int[N];
            Arrays.fill(ans, -1);
            ans[idx] = heights[idx];
            idx++;
            for (int i = 1; i < N; i++) {
                int num = heights[i];
                if (ans[N - idx] == -1 && ans[idx] == -1) {
                    ans[N - idx] = num;
                } else if (ans[idx] == -1) {
                    ans[idx] = num;
                    idx++;
                }
            }

            int maxDiff = 0;
            for (int i = 0; i < N; i++) {
                int diff = Math.abs(ans[i] - ans[(i + 1) % N]);
                maxDiff = Math.max(maxDiff, diff);
            }
            sb.append("#").append(t).append(" ").append(maxDiff).append("\n");
        }
        System.out.println(sb);
    }
}

/*
3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6
 */

코드 설명

• Arrays.sort(heights, Collections.reverseOrder());
  프대 높이를 내림차순으로 정렬 (높은 점프대부터 배치하기 위해).

for (int i = 1; i < N; i++) {
    int num = heights[i];
    if (ans[N - idx] == -1 && ans[idx] == -1) {
        ans[N - idx] = num;
    } else if (ans[idx] == -1) {
        ans[idx] = num;
        idx++;
    }
}

• 두 번째 점프대부터는 idx를 기준으로 좌우 교차 배치합니다.(N-idx는 왼쪽 인덱스, idx는 오른쪽 인덱스)
• 이렇게 하면 큰 높이차가 발생할 수 있는 인접 점프대를 최대한 멀리 배치할 수 있습니다.

int maxDiff = 0;
for (int i = 0; i < N; i++) {
    int diff = Math.abs(ans[i] - ans[(i + 1) % N]);
    maxDiff = Math.max(maxDiff, diff);
}

• 원형 구조이므로 마지막과 첫 번째 점프대도 인접합니다.
• 인접한 점프대들 사이의 높이 차이를 모두 계산하고, 그 중 최댓값을 구합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 5521 상원이의 생일파티입니다.

포인트

이 문제는 그래프 탐색 문제입니다.

특정 인물(상원이, 번호 1번)을 기준으로 자신의 친구와 친구의 친구까지 초대할 수 있는 사람 수를 구하는 것이 목적입니다.
즉, 깊이 2까지 탐색하는 문제로, 단순한 BFS 또는 DFS가 아니라 범위를 제한한 탐색이 핵심입니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Q5521 {
    private static int tc, N, M;
    private static List<List<Integer>> friends;

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

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

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

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                friends.get(a).add(b);
                friends.get(b).add(a);
            }

            int sum = 0;
            boolean[] already = new boolean[N + 1];
            already[1] = true;
            for (int num : friends.get(1)) {
                if (!already[num]) {
                    sum++;
                    already[num] = true;
                }
                for (int next : friends.get(num)) {
                    if (!already[next]) {
                        sum++;
                        already[next] = true;
                    }
                }
            }

            sb.append("#").append(t).append(" ").append(sum).append("\n");
        }
        System.out.println(sb);
    }
}
/*
2
6 5
2 3
3 4
4 5
5 6
2 5
6 5
1 2
1 3
3 4
2 3
4 5
 */

코드 설명

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    friends.get(a).add(b);
    friends.get(b).add(a);
}

• 인접 리스트 방식으로 친구 관계를 저장할 friends 리스트를 초기화합니다.
• 사람 번호는 1번부터 시작하므로 0번은 사용하지 않습니다.
• 양방향 그래프 형태로 친구 관계를 저장합니다.

for (int num : friends.get(1)) {
    if (!already[num]) {
        sum++;
        already[num] = true;
    }
    for (int next : friends.get(num)) {
        if (!already[next]) {
            sum++;
            already[next] = true;
        }
    }
}

• 상원이(1번)의 친구(num)와 친구의 친구(next)를 순회하며 초대 가능한 사람을 탐색합니다.
• 이미 초대한 사람은 already 배열로 체크하여 중복을 방지합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 3421 수제 버거 장인입니다.

포인트

중·고등학교 때 배운 부분집합 개념을 떠올려 보면, 원소의 개수가 N개일 때 가능한 모든 부분집합의 수는 2ⁿ임을 알 수 있습니다.

이 문제에서도 모든 음식 조합(부분집합)을 고려하되, 서로 같이 먹으면 안 되는 음식 쌍(충돌 쌍)이 포함된 조합은 제외해야 합니다.

초기에는 DFS를 이용해 완전탐색을 시도했지만, 시간 초과가 발생하였고, 더 빠른 탐색 방식이 필요했습니다.

그 대안으로 선택한 것이 비트마스킹(bit masking)입니다.

비트마스킹은 집합의 포함 여부를 비트(0 또는 1)로 표현할 수 있기 때문에, 모든 조합을 효율적으로 순회할 수 있으며,
AND(&) 연산을 통해 충돌 여부도 매우 빠르게 판단할 수 있습니다.

이처럼 비트 연산은 속도가 빠르고, 메모리 효율도 뛰어나기 때문에,
이번 문제와 같이 부분집합을 다루는 경우에 매우 적합한 방법입니다.

소스코드

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

public class Solution {
    private static int tc, N, M;
    private static boolean[][] disabled;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            long[][] conflict = new long[M][2];

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                long a = 1 << (Integer.parseInt(st.nextToken()) - 1);
                long b = 1 << (Integer.parseInt(st.nextToken()) - 1);
                conflict[i][0] = a;
                conflict[i][1] = b;
            }

            long count = 0;
            for (int i = 0; i < (1 << N); i++) {
                boolean check = false;
                for (int j = 0; j < M; j++) {
                    long foodA = conflict[j][0];
                    long foodB = conflict[j][1];
                    if ((i & foodA) != 0 && (i & foodB) != 0) {
                        check = true;
                        break;
                    }
                }
                if (!check) {
                    count++;
                }
            }
            sb.append("#").append(t).append(" ").append(count).append("\n");
        }
        System.out.println(sb);
    }
}
/*
3
3 2
1 2
2 3
3 0
3 3
1 2
1 3
2 3
 */

코드 설명

• long[][] conflict
  서로 함께 먹을 수 없는 음식 쌍을 저장하는 배열
  • 1 << (번호 - 1) 형태로 비트 마스크로 변환하여 저장합니다.
    (예: 음식 1 → 0001, 음식 3 → 0100)

for (int i = 0; i < (1 << N); i++) {
    boolean check = false;
    for (int j = 0; j < M; j++) {
        long foodA = conflict[j][0];
        long foodB = conflict[j][1];
        if ((i & foodA) != 0 && (i & foodB) != 0) {
            check = true;
            break;
        }
    }
    if (!check) {
        count++;
    }
}

• i는 0부터 2^N - 1까지의 모든 정수를 나타내며, 각 숫자가 하나의 부분집합을 의미합니다.
  • 예: i = 5 (101₂) → 음식 1과 음식 3을 선택한 경우
• conflict에 저장된 음식 쌍이 동시에 부분집합에 존재하면 해당 조합은 제외
  • (i & foodA) != 0 && (i & foodB) != 0 → 두 음식 모두 포함되었는지 확인
• 조건을 만족하는 조합(check == false)만 count++

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 6782 현주가 좋아하는 제곱근 놀이입니다.

포인트

해당 문제의 가장 포인트는 Math.sqrt()의 반환값입니다.

먼저 자바의 Math.sqrt() 스펙을 살펴보겠습니다.

/**
 * Returns the correctly rounded positive square root of a
 * {@code double} value.
 * Special cases:
 * <ul><li>If the argument is NaN or less than zero, then the result
 * is NaN.
 * <li>If the argument is positive infinity, then the result is positive
 * infinity.
 * <li>If the argument is positive zero or negative zero, then the
 * result is the same as the argument.</ul>
 * Otherwise, the result is the {@code double} value closest to
 * the true mathematical square root of the argument value.
 *
 * @param   a   a value.
 * @return  the positive square root of {@code a}.
 */
@IntrinsicCandidate
public static native double sqrt(double a);

스펙을 살펴보면 반올림된 양의 제곱근을 반환한다고 되어 있습니다.

예를 들어서 Math.sqrt(9) = 3이지만, Math.sqrt(8) = 2.xx 값으로 나오는 것입니다.

이제 문제를 살펴보면

값이 2일때는 0번의 연산

연산을 한번만 하는 것은 4(루트 4)이므로 3은 4로 이동 후 연산을 진행하면 2번의 연산이 진행됩니다.(n+1, 루트 N)

다음 제곱수를 생각했을 때 9는 루트 처리 후 3의 값에 +1하면 됩니다.

즉 일반화를 진행하면

1. 현재 수가 완전제곱수라면: √N 연산 (연산 1회)
2. 그 외의 경우: +1 연산을 반복해서 완전제곱수로 만든 뒤, √ 연산

• 완전제곱수가 아니면, +1 연산을 통해 다음 완전제곱수로 이동한 뒤 √ 연산을 합니다.
• 이 과정을 반복하면서 N이 2가 될 때까지 연산 횟수를 누적합니다.
• 즉, N → 다음 제곱수 → √ → 반복, 이 과정을 통해 DP 없이도 최적의 연산 횟수를 구할 수 있습니다.

소스코드

public class Q6782 {
    private static int tc;
    private static Long N;

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

        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= tc; t++) {
            N = Long.parseLong(br.readLine());
            sb.append("#").append(t).append(" ").append(solve(N)).append("\n");
        }
        System.out.println(sb);
    }

    private static long solve(long n) {
        long count = 0;

        while (n != 2) {
            long sqrt = (long) Math.sqrt(n);
            if (sqrt * sqrt == n) {
                n = sqrt;
                count++; // 한 번의 연산
            } else {
                long nextSquare = (sqrt + 1) * (sqrt + 1);
                count += nextSquare - n;
                n = nextSquare;
            }
        }

        return count;
    }
}

코드 설명

• solve(long n)
  n의 2로 만드는 최소 연산 값을 구하는 함수
  • n이 2가 아닐동안
    • Math.sqrt(n)을 통해 sqrt 값을 구해줍니다.(여기서 기본 스펙이 double이기 때문에 long으로 타입 캐스팅을 진행해줍니다.)
    • n이 제곱수인지를 판단해주기 위해 sqrt * sqrt = n인지 파악합니다
      • 제곱수라면
        • n = sqrt로 치환 후 count를 1 증가합니다.
      • 제곱수가 아니라면
        • 다음 제곱수까지 count를 증가시키고
        • n을 다음 제곱수로 치환합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 7793 오! 나의 여신님입니다.

포인트

해당 문제에서는 악마의 손아귀가 먼저 진행되어야 합니다.

만약 악마의 손아귀를 통해서 전파된 곳에 수연이가 이미 있는 곳이라도 사실 크게 의미가 없습니다.

왜냐하면 이미 수연이가 있는 위치는 수연이가 도달한 공간이기 때문에 다음 시간에는 수연이가 이동하기에 부식된 공간과는 수연이의 위치와 무관합니다. 수연이가 고려할 것은 다음 위치에 악마의 손아귀가 있는지 없는지 입니다.

따라서 BFS 탐색을 통해서 문제를 진행합니다.

소스코드

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

public class Q7793 {
    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static int tc, N, M, ans;
    private static char[][] map;
    private static int[][] step;
    private static boolean[][] visited;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static Pair angle, su;
    private static List<Pair> demons;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            map = new char[N][M];
            step = new int[N][M];
            visited = new boolean[N][M];
            demons = new ArrayList<>();
            ans = Integer.MAX_VALUE;

            for (int i = 0; i < N; i++) {
                String line = br.readLine();
                for (int j = 0; j < M; j++) {
                    map[i][j] = line.charAt(j);
                    if (map[i][j] == 'D') {
                        angle = new Pair(i, j);
                    } else if (map[i][j] == 'S') {
                        su = new Pair(i, j);
                    } else if (map[i][j] == '*') {
                        demons.add(new Pair(i, j));
                    }
                }
            }

            int answer = bfs();

            sb.append("#").append(t).append(" ")
                    .append(answer == -1 ? "GAME OVER" : answer)
                    .append("\n");
        }
        System.out.println(sb);
    }

    static int bfs() {
        Queue<Pair> suyeonQ = new LinkedList<>();
        Queue<Pair> demonQ = new LinkedList<>();
        suyeonQ.add(su);
        demonQ.addAll(demons);

        while (!suyeonQ.isEmpty()) {
            // 1. 악마 먼저 퍼짐
            int demonSize = demonQ.size();
            for (int i = 0; i < demonSize; i++) {
                Pair d = demonQ.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = d.x + dx[dir];
                    int ny = d.y + dy[dir];
                    if (canGo(nx, ny) && map[nx][ny] != 'D') {
                        map[nx][ny] = '*';
                        demonQ.offer(new Pair(nx, ny));
                    }
                }
            }

            // 2. 수연이 이동
            int suSize = suyeonQ.size();
            for (int i = 0; i < suSize; i++) {
                Pair s = suyeonQ.poll();
                for (int dir = 0; dir < 4; dir++) {
                    int nx = s.x + dx[dir];
                    int ny = s.y + dy[dir];
                    if (canGo(nx, ny)) {
                        if (map[nx][ny] == '*') {
                            continue;
                        } else if (map[nx][ny] == 'D') {
                            return step[s.x][s.y] + 1;
                        }
                        visited[nx][ny] = true;
                        step[nx][ny] = step[s.x][s.y] + 1;
                        suyeonQ.offer(new Pair(nx, ny));
                    }
                }
            }
        }
        return -1;
    }

    private static boolean canGo(int x, int y) {
        if (!inRange(x, y)) return false;
        if (visited[x][y] || map[x][y] == 'X' || map[x][y] == '*') return false;

        return true;
    }

    private static boolean inRange(int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M;
    }
}

/*
2
5 3
D*S
.X.
.X.
.X.
...
5 3
D*S
...
.X.
.X.
...
 */

코드 설명

• inRange(int x, int y)
  x, y가 격자 내에 존재하는지 판단하는 함수
• canGo(int x, int y)
  x, y가 갈 수 있는 위치인지 판단하는 함수
  • 격자 내에 존재하거나
  • 방문하지 않았던 점이거나
  • 돌이나 악마의 손아귀가 아닌 점일 시에 true를 반환합니다.
• bfs()
  bfs 탐색을 하는 함수
  • suyeonQ, demonQ를 선언합니다.
    • suyeonQ: 수연이의 위치를 저장하는 Queue
    • demonQ: 악마의 손아귀의 위치를 저장하는 Queue
  • suyeonQ.isEmpty()가 아닐동안
    • 악마의 손아귀를 먼저 진행
      • 현재 시점의 큐 크기(demonSize)만큼만 반복하여, 같은 시간대의 악마의 손아귀만 처리하고 다음 단계는 다음 턴에 처리
      • 갈 수 있을 때(canGo(nx, ny) && map[nx][ny] != 여신)
        • demonQ에 저장
    • 수연이 이동
      • 현재 시점의 큐 크기(suSize)만큼만 반복하여, 같은 시간대의 수연이 이동만 처리하고 다음 단계는 다음 턴에 처리 
      • step[][] 배열을 통해 이전 위치 + 1을 저장
      • 만약 다음 canGo에 여신이면 step[s.x][s.y] + 1 반환.