원래 서버에서 http를 사용하고 있다가 https로 배포한 프론트와의 통신을 위해 가비아 도메인을 ACM을 통해 인증서를 발급받아 새로 https를 적용하였다!

GET 요청으로 health_check를 보냈을 때는 응답이 잘 왔으나

✅ 문제

POST 요청을 보내니 connection timeout이 발생하는 것이다.

나는 서버에서 nginx를 활용한 무중단 배포 blue-green을 사용하고 있었다.

✅ 원인

• 검색해보니
• HTTPS 암호화로 인해 패킷이 무거워지거나, nginx의 기본 타임아웃 설정이 데이터가 포함된 POST 요청을 처리하기에 너무 짧은 것이었다.

✅ 해결

• Nginx 설정 파일 수정하기 (경로 /etc/nginx/conf.d/default.conf)

location / {
    proxy_connect_timeout 300;
    proxy_send_timeout 300;
    proxy_read_timeout 300;
    send_timeout 300;
    client_max_body_size 20M;
    ...
}

• 위 내용 작성 후

sudo systemctl daemon-reload (서비스 설정 변경 인식)

sudo systemctl reload nginx (Nginx 엔진에 설정 반영)

다시 postman으로 요청을 보내면 응답이 정상적으로 온다!!

초기에 개발에 입문 했을 때 사람들이 Docker Docker 하길래 도대체 무슨 기술인지 궁금했다. 백엔드 개발을 시작하면서 다양한 기술들을 배우고 싶었고 인프런 강의를 통해 원하는 기술들을 공부하는데 많은 도움이 되었다.

특히 박재성님 강의 도움을 정말 많이 받았다. 지금 포스팅은 Docker 강의 후기이지만 정말 많은 강의들을 들었다. 말그대로 전반적인 강의들은 필요한 액기스만 압축해놓은 거의 하루종일 시간만 투자하면 해당 기술을 배울 수 있다.

무엇보다 박재성님은 수업 자료를 항상 너무나도 꼼꼼하게 노션, pdf 형식으로 모두 제공해주시는게 정말 좋았다. 그만큼 수업에 더 깊이 집중할 수 있었다.

강의는 다음과 같았다.

• Docker 기본 개념
• 현업에서 자주 사용하는 Docker CLI 익히기
• 도커 볼륨을 활용해 데이터 유실 방지하기
• Dockerfile 활용해 이미지 직접 만들기
• Docker Compose를 활용해 컨테이너 관리하기
• Docker Compose를 활용해 2개 이상의 컨테이너 관리하기
• AWS EC2에 서버 배포해보기
• AWS EC2에서 Docker를 활용해 배포해보기

박재성님의 다른 강의들은 더 깊숙한 개념을 알고 싶다면 추가적인 학습이 필요한 것들도 있지만 Docker강의는 이 강의만으로도 Docker를 정복할 수 있을 정도로 강의 구성이 너무 좋았다.

그래서 Docker 강의 덕분에 서버 배포도 이제 수월하게 할 수 있게 되었다.

https://school.programmers.co.kr/learn/courses/30/lessons/42576

✔️관련 알고리즘 개념

해시

☑️ 문제 분석

• 해당 문제는 HashMap의 key와 value쌍을 이용하여 문제를 해결하는 것이다. 여기서 중요한 것은 예제 3과 같이

  "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

  동명이인이 있는 경우를 처리하는 것이다.

• 예제 3에 대해 분석해보자

  • completion 정보를 hashMap에 저장해둔다.
  • 이후 participant를 반복문으로 돌면서 hashMap에 저장된 참가자 정보가 없다면 해당 참가자가 완주하지 못한 것으로 판단하여 해당 참가자의 이름을 반환한다.
  1. completion 정보 저장
     1. stanko 삽입 (여기서 value값은 key에 해당하는 이름을 가진 사람수이다.)

        | key | value |
        | --- | --- |
        | stanko  | 1 |
    2. ana 삽입


        | key | value |
        | --- | --- |
        | stanko  | 1 |
        | ana  | 1 |
    3. mislav 삽입 .


        | key | value |
        | --- | --- |
        | stanko  | 1 |
        | ana  | 1 |
        | mislav  | 1 |
2. participant 정보다 hashMap에 포함된건지 확인


    | key | value |
    | --- | --- |
    | stanko  | 1 |
    | ana  | 1 |
    | mislav  | 1 |
    1. mislav 확인
        1. 현재 hashMap에는 mislav가 존재한다. 해당 참가자를 확인했으므로 hashMap에서 지워준다.


            | key | value |
            | --- | --- |
            | stanko  | 1 |
            | ana  | 1 |
    2. stanko확인
        1. 현재 hashMap에는 stanko가 존재한다. 해당 참가자를 확인했으므로 hashMap에서 지워준다.


            | key | value |
            | --- | --- |
            | ana  | 1 |
    3. mislav 확인
        1. 현재 hashMap에는 mislav이 존재하지 않는다. 즉 완주자 명단에 존재하지 않는 것이므로 해당 참가자의 이름을 반환한다. 

☑️ 코드

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String s : completion) {
            if(map.containsKey(s)) {
                Integer value = map.get(s);
                map.put(s, value+1);
            }else {
                map.put(s, 1);
            }
        }

        String answer = "";
        for (String s : participant) {
            if(map.containsKey(s)) {
                Integer value = map.get(s);
                if(value.equals(1)) map.remove(s);
                else map.put(s, value-1);
            } else {
                answer = s;
                break;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        String[] participant = {"mislav", "stanko", "mislav", "ana"};
        String[] completion = {"stanko", "ana", "mislav"};
        System.out.println(new Solution().solution(participant, completion));
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 동명이인을 처리하기 위한 로직이 어려웠다.

https://www.acmicpc.net/problem/10868

✔️관련 알고리즘 개념

세그먼트 트리

☑️ 문제 분석

• 이 문제는 구간에 해당하는 최솟값을 구하는 문제이다.

• M개의 구간에 대해 최솟값을 각각 구해야 하므로 빠르게 연산을 수행할 수 있는 세그먼트 자료구조를 이용하면 된다.

• 예제입력 1

10 4
75
30
100
38
50
51
52
20
81
5
1 10
3 5
6 9
8 10

• 1단계, 트리 초기화하기 - 리프노드에 원본 데이터 입력

  • 2*i ≥ 10 (N : 데이터 개수)를 만족하는 최솟값 I는 4이다.

  • 배열 size = 2*i *2 = 32이다.

  • 시작 리프노트 = 2*i = 16이므로 인덱스 16부터 N개의 데이터를 채운다.

    

• 2단계, 질의 값 구하기

  • 세그먼트 트리 index = 주어진 질의 index + 2ⁱ -1를 이용하여 세그먼트 트리용 index로 전환한다.

    ① start_index % 2 == 1(짝수)일 때 해당 노드를 선택한다.

    ② end_index % 2 == 0(홀수)일 때 해당 노드를 선택한다.

    ③ start_index depth 변경 → start_index = (start_index + 1) / 2 연산을 실행한다.

    ④ end_index depth 변경 → end_index = (end_index - 1) / 2 연산을 실행한다.

    ⑤ ①~④를 반복하다가 end_index < start_index가 되면 종료한다.

  • 예를 들어, 예시입력1에서 3 5는 3번째 데이터에서 5번째 데이터 중 최솟값을 구하는 것이다.

  • 위의 과정을 통해 범위에 속하는 최솟값을 구하면 아래와 같다.

  • 범위 시작 인덱스 = 3 + 2^4 - 1 = 18

  • 범위 끝 인덱스 = 5 + 2^4 - 1 = 20

    → 최종적으로 선택된 노드는 20번째 노드와 9번째 노드이다. 여기서 9번째 노드는 18번째와 19번째 노드의 최솟값을 지니고 있으므로 20번째와 9번째 노드를 선택한 것은 18~20번째 노드를 잘 선택한 것과 같다.

☑️ 코드

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

public class Main {
    static int[] tree;
    public static void main(String[] args) throws IOException {
        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 temp = N; // N 보존을 위해 복사
        int treeHeight = 0;
        while(temp != 0) {
            temp /= 2;
            treeHeight++;
        }

        int treeSize = (int) Math.pow(2, treeHeight+1);
        tree = new int[treeSize+1];

        int start_leaf_node_index = (int) Math.pow(2, treeHeight);
        for (int i = start_leaf_node_index; i < start_leaf_node_index + N; i++) {
            tree[i] = Integer.parseInt(br.readLine());
        }

        // 트리 초기화
        setTree(treeHeight);

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

            a += (int) Math.pow(2, treeHeight) -1;
            b += (int) Math.pow(2, treeHeight) -1;
            System.out.println(findMin(a, b));
        }

    }

    private static int findMin(int s, int e) {
        // a에서 b까지의 범위 중 최솟값 구하기
        int minValue = Integer.MAX_VALUE;

        while(s <= e) {
            if(s % 2 == 1) {
                minValue = Math.min(minValue, tree[s]);
                s++;
            }
            if(e % 2 == 0) {
                minValue = Math.min(minValue, tree[e]);
                e--;
            }
            s /= 2;
            e /= 2;
        }
        return minValue;
    }

    private static void setTree(int treeHeight) {
        int index = (int) Math.pow(2, treeHeight) - 1;
        for (int i = index; i > 0; i--) {
            tree[i] = Math.min(tree[2*i], tree[2*i+1]);
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음

https://www.acmicpc.net/problem/5052

✔️관련 알고리즘 개념

트라이

☑️ 문제 분석

• 해당 문제는 트라이 자료구조를 사용하면 된다.
• 우선 일관성이 깨지는 경우는 다음과 같이 두가지이다.

✍️ 첫 번째, 911의 prefix 91이 나중에 나오는 경우

1 // t
2 // n
911
91

• 트라이 자료구조에 911이 있는 상태에서 91을 삽입하는 경우

  • 91에서 1이 삽입되고 isEnd를 true라고 값을 표시한 후

  • 현재 노드에 대해 자식노드가 존재하는지 탐색한다. 만약 자식이 존재하면 일관성이 벗어나는 것이다.

  • 관련 코드

       if(k == phoneNumber.length()-1) {
                              now.isEnd = true;
                              // 자식이 있으면 일관성 위배
                              for (tNode child : now.next) {
                                  if (child != null) {
                                      consistency = false;
                                      break;
                                  }
                              }
                          }

✍️ 두 번째, prefix 911이 먼저 나오고 9112546이 나중에 나오는 경우

2 // t
3 // n
911
97625999
91125426

• 트라이 자료구조에서 911은 이미 삽입되어 있고 91125426을 삽입하고 있는 경우

  • 91125426에서 세번째 숫자인 1을 삽입했는데 해당 숫자를 다 삽입하지 않았는데도 isEnd가 true인 상태이다. 이 경우는 이미 다른 숫자 값이 존재하여 해당 숫자를 prefix로 갖는 경우이므로 일관성에 벗어나는 것이다.

  • 관련 코드

        if(now.isEnd) {
                              consistency = false;
                              break;
                          }

☑️ 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int i = 0; i < t; i++) {
            boolean consistency = true;
            int n = Integer.parseInt(br.readLine()); // 전화번호 수

            tNode root = new tNode(); // 루트노드는 공백으로
            for (int j = 0; j < n; j++) {
                String phoneNumber = br.readLine();
                tNode now = root;
                for (int k = 0; k < phoneNumber.length(); k++) {
                    char ch = phoneNumber.charAt(k);
                    if(now.next[ch - '0'] == null) {
                        now.next[ch - '0'] = new tNode();
                    }
                    if(now.isEnd) {
                        consistency = false;
                        break;
                    }
                    now = now.next[ch - '0'];

                    if(k == phoneNumber.length()-1) {
                        now.isEnd = true;
                        // 자식이 있으면 일관성 위배
                        for (tNode child : now.next) {
                            if (child != null) {
                                consistency = false;
                                break;
                            }
                        }
                    }
                }
            }
            System.out.println(consistency ? "YES" : "NO");
        }
    }

    static class tNode {
        tNode[] next = new tNode[10];
        boolean isEnd;
    }
}

☑️ 채점 결과 : 틀림 → 맞음

☑️ 어려웠던 점

• 아래의 경우를 생각하지 못함

1
2
911
91

https://www.acmicpc.net/problem/1012

✔️관련 알고리즘 개념

깊이 우선 탐색

너비 우선 탐색

☑️ 문제 분석

• 해당 문제는 BFS 혹은 DFS 탐색을 진행하면서 탐색이 진행되는 그룹수를 구하면 된다.

☑️ 코드

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

public class Main {
    static int[][] visited;
    static Queue<Cabbage> queue = new LinkedList<>();
    static int T, M, N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken()); // 가로 길이 (열)
            N = Integer.parseInt(st.nextToken()); // 세로 길이 (행)
            K = Integer.parseInt(st.nextToken()); // 배추 위치 개수

            visited = new int[N][M];

            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken()); // 가로
                int y = Integer.parseInt(st.nextToken()); // 세로
                visited[y][x] = 1; // 좌표 저장
            }

            queue.clear();
            int count = 0;
            for (int r = 0; r < N; r++) {
                for (int c = 0; c < M; c++) {
                    if (visited[r][c] == 1) {
                        BFS(r, c);
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }

    static void BFS(int r, int c) {
        visited[r][c] = 0;
        queue.add(new Cabbage(r, c));

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

            // 상
            if (cur.r - 1 >= 0 && visited[cur.r - 1][cur.c] == 1) {
                visited[cur.r - 1][cur.c] = 0;
                queue.add(new Cabbage(cur.r - 1, cur.c));
            }
            // 하
            if (cur.r + 1 < N && visited[cur.r + 1][cur.c] == 1) {
                visited[cur.r + 1][cur.c] = 0;
                queue.add(new Cabbage(cur.r + 1, cur.c));
            }
            // 좌
            if (cur.c - 1 >= 0 && visited[cur.r][cur.c - 1] == 1) {
                visited[cur.r][cur.c - 1] = 0;
                queue.add(new Cabbage(cur.r, cur.c - 1));
            }
            // 우
            if (cur.c + 1 < M && visited[cur.r][cur.c + 1] == 1) {
                visited[cur.r][cur.c + 1] = 0;
                queue.add(new Cabbage(cur.r, cur.c + 1));
            }
        }
    }

    static class Cabbage {
        int r, c;
        Cabbage(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 여기서 M은 가로(열), N은 세로(행)
• Java에서 배열은 arr[행][열] 구조라서 new int[N][M] 로 만들어야 한다
• 이전 코드에서는 x=가로, y=세로를 그대로 [x][y]에 넣고 있어서 index가 꼬인다.

👉 visited = new int[N][M];

https://www.acmicpc.net/problem/1647

✔️관련 알고리즘 개념

최소 신장 트리

☑️ 문제 분석

• 이 문제는 집(노드)를 길(에지)로 연결했을 때 비용(가중치)가 최소가 되도록 해야 하므로 최소 신장 트리의 개념을 이용하여 문제에 접근해야 한다.

• 문제에서는 모든 집을 연결하는 것이 아니라 집들을 길로 연결하여 두 개의 마을을 만들어야 한다. 만약 모든 집들을 연결하려면 N-1개의 에지를 사용하면 된다. 하지만 우리는 문제 요구 조건에 따라 두 개의 마을로 나눠야 하므로 N-2개의 에지만 사용하면 된다.

• 예시 입력 1을 분석해보자

  • 집의 개수는 7, 길의 개수는 12이고

  • 그 아래 12개의 줄에 집의 번호들과 비용이 작성되어 있다.

  • 최소 신장 트리를 사용하기 위해서는 우선순위 큐를 이용하여 비용이 낮은 순으로 정렬하고

  • 사이클 여부를 판단하기 위해 유니온 파인드를 수행해야 한다.

    7 12
    1 2 3
    1 3 2
    3 2 1
    2 5 2
    3 4 4
    7 3 6
    5 1 5
    1 6 2
    6 4 1
    6 5 3
    4 5 3
    6 7 4

☑️ 코드

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

public class Main {
    static int N, M; // 집의 개수, 길의 개수
    static int[] parent;
    static PriorityQueue<Edge> queue = new PriorityQueue<>();

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

        // 베열 초기화
        parent = new int[N+1];
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            queue.add(new Edge(A, B, C));
        }

        int used_Edge = 0;
        int result = 0;
        while (used_Edge < N-2) {
            Edge poll = queue.poll();
            if(find(poll.A) != find(poll.B)) {
                union(poll.A, poll.B);
                used_Edge++;
                result += poll.C;
            }
        }

        System.out.println(result);

    }

    static int find(int a) {
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a != b) parent[b] = a;
    }

    static class Edge implements Comparable<Edge>{
        int A;
        int B;
        int C;

        Edge(int A, int B, int C) {
            this.A = A;
            this.B = B;
            this.C = C;
        }

        @Override
        public int compareTo(Edge o) {
            return this.C - o.C;
        }
    }

}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음

https://www.acmicpc.net/problem/14938

✔️관련 알고리즘 개념

플로이드-워셜⭐

☑️ 문제 분석

• 해당 문제는 모든 노드간의 최단거리를 계산을 해야하는 문제이므로 플로이드-워션 개념을 사용하여 문제를 풀면된다.

• 예시입력1을 분석해보면

    5 5 4
    5 7 8 2 3
    1 4 5
    5 2 4
    3 2 3
    1 2 3

  • 첫 째줄에는 지역개수(n), 수색범위(m), 길의 개수(r)가 주어진다.
  • 둘째줄에는 1번에서 n번 지역까지 아이템 개수가 주어진다. 이는 별도의 items배열을 생성하여 지역별 아이템 개수를 저장해두고 최대 아이템 개수를 계산할 때 이용하면 된다.

    | 1 | 2 | 3 | 4 | 5 |
    | --- | --- | --- | --- | --- |
    | 5 | 7 | 8 | 2 | 3 |
- 이후 r개의 줄에는 길 정보가 주어져있으므로 인접행렬에 저장한다.
    - 단, 양방향으로 지역간 이동이 가능하므로 꼭 양방향으로 거리 정보를 저장한다.

• 최종 출력

  • 이제 최종 출력은 예은이가 1번~n번 지역에 떨어졌을 때 각각 경우에서 얻을 수 있는 아이템 개수를 계산하고 각 경우에서 얻을 수 있는 아이템 개수가 제일 큰 값을 출력하면 된다.

    int max_item = Integer.MIN_VALUE; // 최대 아이템 개수
          for (int i = 1; i <= n; i++) {
              int sum = 0;
              for (int j = 1; j <= n; j++) {
                  if(distance[i][j] <= m) {
                      sum += items[j];
                  }
              }
              if(max_item < sum) max_item = sum;
          }

☑️ 코드

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

public class Main {
    static int[][] distance; // 거리 배열
    static int[] items; // 지역별 아이템 개수

    public static void main(String[] args) throws IOException {
        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 r = Integer.parseInt(st.nextToken()); // 길의 개수

        // 지역별 아이템 개수 저장
        items = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            items[i] = Integer.parseInt(st.nextToken());
        }

        // 인접 행렬 초기화, i와 j의 값이 같은 곳은 0으로 초기화 나머지는 무한대
        distance = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(i == j) distance[i][j] = 0;
                else distance[i][j] = Integer.MAX_VALUE;
            }
        }

        // 길 정보 입력받기
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            if(distance[a][b] > l) {
                distance[a][b] = l;
                distance[b][a] = l;
            }
        }

        // 플로이드-워셜을 적용하여 노드간 최단거리 계산하기
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if(distance[i][k] != Integer.MAX_VALUE && distance[k][j] != Integer.MAX_VALUE && distance[i][j] > distance[i][k] + distance[k][j])
                        distance[i][j] = distance[i][k] + distance[k][j];
                }
            }
        }

        int max_item = Integer.MIN_VALUE; // 최대 아이템 개수
        for (int i = 1; i <= n; i++) {
            int sum = 0;
            for (int j = 1; j <= n; j++) {
                if(distance[i][j] <= m) {
                    sum += items[j];
                }
            }
            if(max_item < sum) max_item = sum;
        }

        System.out.println(max_item);
    }

}

☑️ 채점 결과 : 틀림 → 맞음

☑️ 어려웠던 점

• 양방향 그래프이므로 거리 정보를 양방향으로 저장했어야 했다.

// 처음엔 단방향 저장
if(distance[a][b] > l) {
    distance[a][b] = l;
}

-------->
// 양방향 거리 
if(distance[a][b] > l) {
    distance[a][b] = l;
    distance[b][a] = l;
}

https://www.acmicpc.net/problem/7040

✔️관련 알고리즘 개념

벨만-포드

☑️ 문제 분석

• 우선 문제 조건에서 1번부터 N번까지의 소들이 번호순대로 줄을 설 때 1번소와 N번 소의 최대 거리를 구해야 한다.
• 예시 입력 1을 분석해보자

4 2 1
1 3 10
2 4 20
2 3 3

• 소는 1번부터 4번까지 4마리가 있고 서로를 좋아하는 소의 쌍은 2쌍, 서로를 싫어하는 소의 쌍은 1쌍이 있다. 1번, 3번 소는 서로를 좋아하므로 최대 10까지만 떨어져 있을 수 있고 2번, 4번 소도 서로를 좋아하므로 최대 20까지만 떨어져 있을 수 있다. 그리고 2번, 3번 소는 서로를 싫어하므로 최소 3만큼 떨어져 있어야 한다.
• 최종적으로 1번과 4번의 최대 거리를 구해야 하므로 최대한 소들이 서로 떨어져 있게끔 한다.

• 위 그림을 보면 2와 4가 최대 20만큼 떨어져 있다. 이제 1과 2가 최대한 멀리 떨어져 있을 수록 1과 4사이의 거리가 최대일 것이다. 또한 1과 3이 최대 2만큼 떨어져 있다. 이제 3과 4가 최대한 멀리 떨어져 있을 수록 1과 4사이의 거리가 최대일 것이다. 예시 입력 1에서는 2와 3의 최소 거리가 나와 있으므로 전자를 이용하여 문제를 풀면된다.
• 따라서 1과 2사이 최대 거리는 7, 2와 4사이 최대 거리는 20이므로 1과 4사이의 최대거리는 27이다.

위의 과정을 벨만-포드를 적용하여 이해해보자

에지리스트 – (c1, c2, d)순

(1, 3, 10)

(2, 4, 20)

(2, 3, 3)

1번째 업데이트

(1)(1, 3, 10)

• 1번소의 distance[1] != ∞ => distance[3] = 10으로 업데이트

(2) (2, 4, 20)

• 2번 소의 distance[2] = ∞ => 업데이트 불가

(3) (2, 3, 3)은 최소 거리이고 우리는 3번 소의 distance[3] = 10 (!= ∞)

라는 것을 이용해서 distance[2] = distance[3] – 10 = 7로 업데이트

여기서

MD배열에서 distance[c2] != ∞이면 distance[c1] = distance[c2] – d로 계산할 수 있다.

ML배열은 일반적인 벨만포드와 같이 계산하면 된다.

2번째 업데이트

(1)(1, 3, 10)

• 업데이트 진행할 것 없음

(2) (2, 4, 20)

• distance[2] != ∞ => distance[4] = distance[2] +20 = 27로 업데이트

(3) (2, 3, 3)

• 업데이트 진행할 것 없음

최종적으로 한번 더 에지리스트를 순회하여

• 업데이트 되는 값이 있으면 음수사이클이 존재하는 것과 같으므로 줄을 서는 것이 불가 -> 1을 출력
• distance[N] = ∞ -> 2출력
• 줄서는것이 가능 & distance[N] != ∞ -> distance[N] 출력

☑️ 코드

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

public class Main {
    static int[] distance; // 거리 배열
    static List<Edge> edge = new ArrayList<>(); // 에지 리스트
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int ML = Integer.parseInt(st.nextToken());
        int MD = Integer.parseInt(st.nextToken());

        distance = new int[N+1];
        Arrays.fill(distance, Integer.MAX_VALUE);

        // ML 입력받기
        for (int i = 0; i < ML; i++) {
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            edge.add(new Edge("ML", c1, c2, d));
        }

        // MD 입력받기
        for (int i = 0; i < MD; i++) {
            st = new StringTokenizer(br.readLine());
            int c1 = Integer.parseInt(st.nextToken());
            int c2 = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            edge.add(new Edge("MD", c1, c2, d));
        }

         // 시작 노드의 거리 배열 값은 0이다.
        distance[1] = 0;
         // N-1번 벨만-포드를 반복한다.
        for (int i = 0; i < N - 1; i++) {
            for (Edge e : edge) {
                if(e.mode.equals("ML")) {
                    if(distance[e.c1] != Integer.MAX_VALUE && distance[e.c2] > distance[e.c1] + e.d) {
                        distance[e.c2] = distance[e.c1] + e.d;
                    }
                } else if(e.mode.equals("MD")) {
                    if(distance[e.c2] != Integer.MAX_VALUE && distance[e.c1] > distance[e.c2] - e.d) {
                        distance[e.c1] = distance[e.c2] - e.d;
                    }
                }
            }
        }

        boolean imPossible = false;
        for (Edge e : edge) {
            if(e.mode.equals("ML")) {
                if(distance[e.c1] != Integer.MAX_VALUE && distance[e.c2] > distance[e.c1] + e.d) {
                    imPossible = true;
                }
            } else if(e.mode.equals("MD")) {
                if(distance[e.c2] != Integer.MAX_VALUE && distance[e.c1] > distance[e.c2] - e.d) {
                    imPossible = true;
                }
            }
        }

        if(imPossible) System.out.println(-1);
        else if(distance[N] == Integer.MAX_VALUE) System.out.println(-2);
        else System.out.println(distance[N]);
    }

    static class Edge {
         String mode;
         int c1;
         int c2;
         int d;

         Edge(String mode, int c1, int c2, int d) {
             this.mode = mode;
             this.c1 = c1;
             this.c2 = c2;
             this.d = d;
         }
    }

}

☑️ 채점 결과 : 틀림 → 맞음

• 처음에는 벨만-포드는 최단거리 문제인데 여기는 최대 거리를 구하라고 해서 Integer.MAX_VALUE가 아닌 Integer,MIN_VALUE를 사용해서 틀렸다.

☑️ 어려웠던 점

• 처음에 문제를 이해하는 것이 어려웠다.

https://www.acmicpc.net/problem/1916

✔️관련 알고리즘 개념

다익스트라

☑️ 문제 분석

• 해당 문제는 최종적으로 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력해야 한다.
• 최소 비용을 구하기 위해서는 다익스트라를 활용하여 출발 도시에서 모든 노드까지 이르는 최소 거리를 구한 후 마지막 출력에서는 최소 거리 중 도착 도시에 이르는 최소 거리만을 출력하면 된다.

☑️ 코드

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

public class Main {
    public static int[] distance; // 최단 거리 저장 배열
    public static boolean[] visited; // 노드 방문 여부 표시
    public static ArrayList<Edge>[] list; // 인접리스트
    public static PriorityQueue<Edge> q = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 도시 개수
        int M = Integer.parseInt(br.readLine()); // 버스 개수

        distance = new int[N+1];
        visited = new boolean[N+1];
        list = new ArrayList[N+1];

        // 인접리스트 초기화
        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }

        Arrays.fill(distance, Integer.MAX_VALUE);

        StringTokenizer st;
        // 버스 노선 입력받기
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()); // 출발 도시
            int b = Integer.parseInt(st.nextToken()); // 도착 도시
            int cost = Integer.parseInt(st.nextToken());
            list[a].add(new Edge(b, cost));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        distance[start] = 0;
        q.add(new Edge(start, 0));

        while (!q.isEmpty()) {
            Edge current = q.poll();
            int c_v = current.vertex;

            if(visited[c_v]) continue; // 이미 방문한 노드라면 넘어감
            visited[c_v] = true;

            for (Edge edge : list[c_v]) {
                int vertex = edge.vertex;
                int weight = edge.weight;

                if(distance[vertex] > distance[c_v] + weight) {
                    distance[vertex] = distance[c_v] + weight;
                    q.add(new Edge(vertex, distance[vertex]));
                }
            }
        }

        System.out.println(distance[end]);
    }

    static class Edge implements Comparable<Edge> {
        int vertex;
        int weight;

        public Edge(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음

https://www.acmicpc.net/problem/3665

✔️관련 알고리즘 개념

위상 정렬

☑️ 문제 분석

• 그림을 이용하여 문제를 입력하면 다음과 같다.

• 만약 위상 정렬을 적용하여 노드간의 순서가 잘 출력 될 것 같으면 노드간의 순서를 출력한다.
  • 하지만, 진입차수가 0인 차수가 없는 경우에는 정렬이 불가하므로 ‘IMPOSSIBLE’을 출력하고
  • 반면, 진입차수가 0인 차수가 존재하지만 여러개 있는 경우 정확한 순위를 매길 수 없으므로 ‘?’를 출력한다.

☑️ 코드

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

public class Main {
    static int[] lastRank;
    static ArrayList<ArrayList<Integer>> arrayList; 
    static int[] D;                                 // 진입차수
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder out = new StringBuilder();
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int tc = 0; tc < t; tc++) {
            n = Integer.parseInt(br.readLine()); // 팀의 개수

            // 작년 순위
            lastRank = new int[n + 1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                lastRank[j] = Integer.parseInt(st.nextToken()); j 인덱스에 저장
            }


            arrayList = new ArrayList<>(n + 1);
            for (int j = 0; j <= n; j++) arrayList.add(new ArrayList<>());
            D = new int[n + 1];

            // 작년 순위를 인접리스트에 저장 
            for (int j = 1; j <= n; j++) {
                for (int k = j + 1; k <= n; k++) {
                    int u = lastRank[j]; 
                    int v = lastRank[k]; 
                    arrayList.get(u).add(v);
                    D[v]++;
                }
            }

            // 상대적인 등수가 바뀐 쌍의 수
            int m = Integer.parseInt(br.readLine());
            for (int j = 0; j < m; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                changeRank(a, b); 
            }

            // 최종 위상 정렬 적용하여 올해 순위 출력하기
            out.append(topologicalSort()).append('\n');
        }

        System.out.print(out.toString());
    }

    private static String topologicalSort() {
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) if (D[i] == 0) queue.offer(i);

        List<Integer> order = new ArrayList<>(n);
        boolean ambiguous = false;

        for (int step = 0; step < n; step++) {
            if (queue.isEmpty()) return "IMPOSSIBLE";  

            if (queue.size() > 1) ambiguous = true;     // 같은 시점의 후보가 2개 이상 → 모호

            int now = queue.poll();
            order.add(now);

            for (int next : arrayList.get(now)) {
                D[next]--;
                if (D[next] == 0) queue.offer(next);
            }
        }

        if (ambiguous) return "?";

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(order.get(i));
        }
        return sb.toString();
    }

    // a와 b팀의 상대적 순위 바꾸기 
    private static void changeRank(int a, int b) {
        // a -> b 가 있으면 b -> a 로 뒤집기
        if (arrayList.get(a).contains(b)) {
            arrayList.get(a).remove((Integer) b);
            D[b]--;
            arrayList.get(b).add(a);
            D[a]++;
        }
        // 없으면 b -> a가 있다고 보고 a -> b로 뒤집기
        else if (arrayList.get(b).contains(a)) {
            arrayList.get(b).remove((Integer) a);
            D[a]--;
            arrayList.get(a).add(b);
            D[b]++;
        }
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 다양한 예외 상황을 고려하여 코드를 작성하는 것이 어려웠다.

https://www.acmicpc.net/problem/16562

✔️관련 알고리즘 개념

유니온 파인드

☑️ 문제 분석

• 우선 예시입력 1, 2를 직접 확인해보면서 풀이를 파악한다.

• 그런데 위의 과정을 구현하고 나면 우리는 parent배열을 통해 집합 관계를 확인할 수 있다.

• 위 정보를 통해 최소 비용을 계산해야 한다.

• 즉, 배열을 돌면서 각 친구들의 친구비와 대표 노드의 최소 비용을 비교하면서 최소 비용을 업데이트해가면 된다.

☑️ 코드

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

public class Main {
    static int[] parent;
    static int[] friendCost;
    static int[] minCost;
    static  int k;
    public static void main(String[] args) throws IOException {
        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()); // 친구 관계수
        k = Integer.parseInt(st.nextToken()); // 가지고 있는 돈

        // 친구 비 저장 배열
        friendCost = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            friendCost[i] = Integer.parseInt(st.nextToken());
        }

        // 대표 노드 저장 배열
        parent = new int[N+1];
        minCost = new int[N+1];

        // 대표 노드 저장 배열 초기화
        for (int i = 1; i <= N; i++) {
            parent[i] = i;
        }

        // 친구 관계수를 입력받고 해당 친구 번호들에 대해 union 연산을 한다.
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int f1 = Integer.parseInt(st.nextToken());
            int f2 = Integer.parseInt(st.nextToken());

            if(f2 < f1) union(f2, f1);
            else union(f1, f2);
        }

        // 루트별 최소비 계산
        final int INF = 1_000_000_000;
        int[] minCost = new int[N + 1];
        Arrays.fill(minCost, INF);

        for (int i = 1; i <= N; i++) {
            int r = find(i); // 반드시 find로 루트 보정
            minCost[r] = Math.min(minCost[r], friendCost[i]);
        }

        int sum = 0;
        for (int i = 1; i <= N; i++) {
            if (i == find(i) && minCost[i] != INF) sum += minCost[i]; // 대표만 합산
        }

        if (sum <= k) System.out.println(sum);
        else System.out.println("Oh no");

    }

    public static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if(a != b) {
            parent[b] = a;
        }
    }

    public static int find(int a) {
        // 대표 노드 반환 함수
        if(parent[a] == a) return a;
        else return parent[a] = find(parent[a]);
    }
}

☑️ 채점 결과 : 틀림 → 맞음

• 집합 관계를 토대로 최소 비용을 계산하는 부분이 틀렸었다.

☑️ 어려웠던 점

• 최소 비용 계산이 어려웠다.

https://www.acmicpc.net/problem/2166

✔️관련 알고리즘 개념

Shoelace 공식(Shoelace formula)

• 2차원 평면에서 다각형의 면적을 구하는 공식으로, 점들이 순서대로(시계 혹은 반시계 방향) 주어졌을 때 사용할 수 있다.

🥾 Shoelace 공식 (신발끈 공식)

다각형의 꼭짓점이 다음과 같이 순서대로 주어졌다.

$(x1,y1), (x2,y2), (x3,y3), …, (xn,yn)$

이때, 면적 A는 다음과 같은 신발끈 공식으로 계산된다.

단, 여기에 끝 점의 다음 점으로 시작점을 다시 사용해야 하므로:

• $xn+1=x1$
• $yn+1=y1$이 된다.

☑️ 문제 분석

• 해당 문제는 N각형을 나타내는 N개의 좌표가 주어졌을 때 해당 다각형의 면적을 구하는 문제이다.

• 처음에는 N각형을 쪼개서 삼각형을 만든 다음 각 삼각형의 넓이를 |CCW|/2를 이용하여 구한 다음 다 더해서 N각형의 넓이를 구하려고 했는데 이는 좌표가 시계방향 혹은 반시계 순서대로 주어져야 사용할 수 있다.

• N각형의 넓이를 삼각형으로 쪼개지 않고 바로 구할 수 있는 방법은 신발끈 공식을 이용하여 문제를 푼다.

  

• 단 여기서 주의해야 할 것은 i값이 n일 때 i+1값은 존재하지 않으므로 x1, y1값으로 계산해야 한다는 점이다.

☑️ 코드

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

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

        Coordinates[] p = new Coordinates[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            p[i] = new Coordinates(a, b);
        }

        double result = 0;
        for (int i = 0; i < N; i++) {
            int j = (i + 1) % N; // 다음 점, 마지막 → 첫 점으로 순환
            result += (long)p[i].x * p[j].y - (long)p[j].x * p[i].y;
        }

        System.out.printf("%.1f\n", Math.abs(result) / 2.0);
    }

    public static class Coordinates {
        int x, y;
        Coordinates(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

☑️ 채점 결과 : 틀림 → 맞음

☑️ 어려웠던 점

• 신발끈 공식을 떠올리지 못했다.

https://www.acmicpc.net/problem/9095

✔️관련 알고리즘 개념

동적 계획법

☑️ 문제 분석

• 여기서 n의 값은 11보다 작은 양수이다.
• n에 대한 경우의 수는 앞의 세 개의 n값들의 합이다.
  • 왜 앞의 3개의 합이냐면 합을 1, 2, 3의 합으로만 나타낼 수 있기 때문이다.
• 아래 그림을 보면
  • 4를 1, 2, 3의 합으로 나타내는 경우의 수는 총 7가지이다.
    • 1을 나타내는 모든 식에 각각 3을 더해주면 4를 나타내는 식이 된다.
    • 2를 나타내는 모든 식에 각각 2를 더해주면 4를 나타내는 식이 된다.
    • 3을 나타내는 모든 식에 각각 1을 더해주면 4를 나타내는 식이 된다.
  • 따라서 여기서 점화식은 p[i] = p[i-1] + p[i-2] + p[i-3] (i > 3) 이 나온다.

☑️ 코드

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

public class Main {
    static int[] dp = new int[11]; // n은 11보다 작다고 했으니 0~10까지

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

        // DP 초기화
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= 10; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }

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

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음

https://www.acmicpc.net/problem/2839

✔️관련 알고리즘 개념

동적 계획법

☑️ 문제 분석

• 이문제는 Nkg으로 설탕의 무게가 주어졌을 때 3kg, 5kg 봉지를 최소 몇개로 만들 수 있느냐에 대한 문제이다.
• 봉지의 개수를 최소로 하려면 5kg이 최대한 많을 수록 좋다.
• 따라서 N이 5의 배수에 해당하는 값이라면 N/5의 값이 정답이 될 것이다.
• 하지만 5의 배수가 아닌 N의 값들이 문제인데
• 예시 입력 11은 3kg 2개, 5kg 1개, 18은 3kg 1개, 5kg 3개와 같이 3kg의 갯수도 고려해야 한다.
• 예시 입력 1: N=18
  • 18은 5의 배수아님 ⇒ 18 - 3 = 15 (count += 1)
    • N=18일 때는 5kg만으로 구성되지 않으므로 3kg으로도 채워준다.
    • 18 - 3 = 15, 3kg으로 옮긴 설탕을 제외한 값 15는 5의 배수이다.
    • 15 / 5 = 3이다. (count += 15/5)
    • 최종적으로 3kg 1개, 5kg 3개가 나오는 것이다.
• 예시 입력 5:N=11
  • 11은 5의 배수가 아님 ⇒ 11 - 3 = 8 (count += 1)
    • 11kg에서 일부를 3kg로 채웠는데 남은 값은 여전히 5의 배수가 아님
    • 8 - 3 = 5 (count += 1)
    • 남은 값 5는 5의 배수이므로 5kg 봉지로 채워준다.
    • 5/5 = 1 (count += 5/5)

⇒ 위의 과정을 재귀함수 형태로 구현한다.

☑️ 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(minNum(N, 0));
    }

    public static int minNum(int N, int count) {
        if (N < 0) return -1;              // 음수면 불가능
        if (N % 5 == 0) return count + N / 5;  // 5로 나눠지면 봉지 수 계산
        return minNum(N - 3, count + 1);   // 3을 빼고 계속 시도
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 재귀함수를 고려하여 알고리즘을 구성해내는게 어려웠다.

• AWS S3와 같은 클라우드 스토리지 서비스에서 제한된 시간 동안 접근 권한을 임시로 부여하는 URL
• 일반적으로 인증 없이도 파일 업로드/다운로드를 허용하고자 할 때 사용된다.

☑️Presigned URL의 필요성

• AWS S3는 기본적으로 인증된 사용자만 파일을 업로드하거나 다운로드할 수 있다. 하지만 다음과 같은 상황에서는 인증 없이도 접근을 허용해야 할 수 있다.

  ① 사용자가 웹 브라우저나 앱에서 직접 S3에 파일을 업로드하도록 하고 싶을 때

  ② 특정 사용자에게만 일시적으로 파일 다운로드 권한을 주고 싶을 때

• 이때 Presigned URL을 사용하면 서버에서 인증된 토큰이 포함된 URL을 생성해서, 클라이언트에게 전달하고, 이 URL을 통해 제한된 시간 동안 안전하게 접근할 수 있다.

☑️ 작동방식

• 서버가 S3와 통신해서 Presigned URL을 생성한다.

• 해당 URL에는 S3 버킷 정보, HTTP 메서드(GET/PUT 등), 유효기간, 서명(Signature) 이 포함됩니다.

• 클라이언트는 이 URL을 통해 S3에 직접 접근할 수 있습니다.

예시: https://your-bucket.s3.amazonaws.com/file.jpg?X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Credential=...

✅ AWS에서 S3 버킷 생성

☑️ S3 버킷 생성

☑️ IAM 사용자 생성

=> 위의 access-key와 secret-key를 꼭 저장해둔다.

✅ 코드 구현

✔️ build.gradle

dependencies {

    ...

    // jdk 의존성 추가 
    implementation 'com.amazonaws:aws-java-sdk-s3:1.12.676'

}

✔️ application.yml

cloud:
  aws:
    access-key: [access-key 값]
    secret-key: [secret-key 값]
    region: ap-northeast-2
    bucket: [bucket 이름]
    endpoint: s3.ap-northeast-2.amazonaws.com

✔️ S3Properties

=> AWS S3에 접근하기 위한 설정값들을 외부 설정 파일(application.yml 등)로부터 바인딩 받기 위한 역할을 한다.

package com.example.Premind_BE.infra.s3;

import lombok.Getter;
import lombok.Setter;
import org.springframework.boot.context.properties.ConfigurationProperties;

@ConfigurationProperties(prefix = "cloud.aws")
@Getter
@Setter
public class S3Properties {
    private String accessKey;
    private String secretKey;
    private String region;
    private String bucket;
    private String endpoint;
}

✔️ S3 Config

=> S3Config는 AmazonS3 객체를 생성하고, AWS 인증 정보 및 엔드포인트 설정을 읽어와 구성한 뒤, Spring Bean으로 등록하는 설정 클래스이다.

package com.example.Premind_BE.infra.s3;

import com.amazonaws.auth.AWSCredentials;
import com.amazonaws.auth.AWSStaticCredentialsProvider;
import com.amazonaws.auth.BasicAWSCredentials;
import com.amazonaws.client.builder.AwsClientBuilder;
import com.amazonaws.services.s3.AmazonS3;
import com.amazonaws.services.s3.AmazonS3ClientBuilder;
import lombok.RequiredArgsConstructor;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

@Configuration
@RequiredArgsConstructor
@EnableConfigurationProperties(S3Properties.class)
public class S3Config {

    private final S3Properties s3Properties;

    @Bean
    public AmazonS3 amazonS3() {
        AWSCredentials credentials = new BasicAWSCredentials(
                s3Properties.getAccessKey(), s3Properties.getSecretKey());

        AwsClientBuilder.EndpointConfiguration endpointConfig =
                new AwsClientBuilder.EndpointConfiguration(
                        s3Properties.getEndpoint(), s3Properties.getRegion());

        return AmazonS3ClientBuilder.standard()
                .withEndpointConfiguration(endpointConfig)
                .withCredentials(new AWSStaticCredentialsProvider(credentials))
                .build();
    }
}

• 나는 위 화면에서 파일 업로드 항목에 클라이언트가 파일을 놓는 순간 presigned url 발급 요청(클라이언트 역할)이 오면 presigned url을 발급(서버 역할)하고 클라이언트는 발급 받은 presigned url을 이용하여 PUT요청으로 S3에 파일을 업로드 한다.
• 위 서비스는 하나의 포트폴리오당 하나의 pdf파일만 업로드 가능하기 때문에 하나의 presigned url만 발급하도록 구현하였다.

☑️ 1단계: presigned url 발급하기

✔️ PortfolioController

public class PortfolioController {
    private final PortfolioService portfolioService;

    @Operation(summary = "presigned url 발급",description = "포트폴리오 업로드 페이지에서 파일을 pdf업로드 항목에 드래그하여 놓는 순간 presigned url을 발급 받고 해당 url로 파일 업로드 진행")
    @PostMapping(value = "/file-upload")
    public PresignedUrlResDto generatePresignedUrl() {
        return portfolioService.generatePresignedUrl();
    }
}

✔️ PortfolioService

=> 파일 이름(fileName)은 사용자의 고유 정보와 UUID 등을 기반으로 생성되며, S3에 저장될 경로 역할을 한다.

public class PortfolioService {
    private final PortfolioRepository portfolioRepository;
    private final UserRepository userRepository;
    private final JobCategoryRepository jobCategoryRepository;
    private final PortfolioQuestionRepository portfolioQuestionRepository;
    private final FileService fileService;
    private final S3Properties s3Properties;
    private final AmazonS3 amazonS3;
    private final JobService jobService;

    public PresignedUrlResDto generatePresignedUrl() {
        Long memberId = getCurrentMember().getId();
        String fileKey = fileService.generateUUID(); // UUID 기반 고유 파일 키 생성
        String fileName = fileService.createFileName(memberId, fileKey); // 사용자 ID와 UUID를 조합한 파일 이름 생성

        // Presigned URL 요청 객체 생성
        GeneratePresignedUrlRequest generatePresignedUrlRequest =
                fileService.createGeneratePresignedUrlRequest(s3Properties.getBucket(), fileName);

        // Presigned URL 생성
        String presignedUrl = amazonS3.generatePresignedUrl(generatePresignedUrlRequest).toString();
        return new PresignedUrlResDto(presignedUrl, fileKey);
    }
}

✔️ FileService

=> AWS S3 Presigned URL을 생성, 관리, 삭제하는 데 사용되는 유틸리티성 서비스이다.

@Slf4j
@Service
@Transactional
@RequiredArgsConstructor
public class FileService {
    private final AmazonS3 amazonS3;
    private final S3Properties s3Properties;

    //     파일 구분용 고유 UUID 생성
    public String generateUUID() {
        return UUID.randomUUID().toString();
    }

    // 사용자 ID + UUID 조합으로 S3에 저장할 파일 이름 생성
    public String createFileName(Long memberId, String imageKey) {
        return memberId
                + "/"
                + imageKey;
    }

    //     Presigned URL 생성을 위한 요청 객체 구성
    public GeneratePresignedUrlRequest createGeneratePresignedUrlRequest(String bucket, String fileName) {

        GeneratePresignedUrlRequest generatePresignedUrlRequest = new GeneratePresignedUrlRequest(bucket, fileName)
                .withKey(fileName)
                .withMethod(HttpMethod.PUT)
                .withExpiration(getPresignedUrlExpiration());

        generatePresignedUrlRequest.addRequestParameter(
                Headers.S3_CANNED_ACL, CannedAccessControlList.PublicRead.toString()
        );

        return generatePresignedUrlRequest;
    }

    // Presigned URL의 유효시간(5분) 설정
    public Date getPresignedUrlExpiration() {
        Date expiration = new Date();
        long expTime = expiration.getTime();
        expTime += TimeUnit.MINUTES.toMillis(5);
        expiration.setTime(expTime);

        return expiration;
    }

    // S3에서 해당 파일 삭제
    public void deleteFile(String fileUrl) {
        try {
            String bucket = s3Properties.getBucket();
            String fileKey = extractKeyFromUrl(fileUrl);
            amazonS3.deleteObject(bucket, fileKey);
            log.info("Deleted file from S3: {}", fileKey);
        } catch (Exception e) {
            log.error("Failed to delete file from S3: {}", fileUrl, e);
        }
    }

    //     전체 URL에서 S3 파일 키만 추출
    private String extractKeyFromUrl(String fileUrl) {
        // presigned URL의 실제 파일 경로만 추출
        URI uri = URI.create(fileUrl);
        return uri.getPath().substring(1); // e.g., "1/f829333c-2e4f-4a38-8eb9-2ee10ae2117e"
    }
}

✔️ 예시 응답

{
    "status": 200,
    "timestamp": "2025-07-28T12:35:31.4411101",
    "success": true,
    "data": {
        "presignedUrl": "[서버측에서 생성한 presigned url 값]"
    }
}

☑️ 2단계: 작성완료하여 fileUrl과 포트폴리오 작성 내용들을 저장

✔️ PortfolioController

@RestController
@RequestMapping("/portfolio")
@RequiredArgsConstructor
@Tag(name = "Portfolio API", description = "포트폴리오 관련 API입니다.")
public class PortfolioController {
    private final PortfolioService portfolioService;

    ...

    @Operation(summary = "포트폴리오 업로드",description = "PDF 포트폴리오 파일과 제목/직무/기업/질문답변 정보 등을 함께 업로드합니다.")
    @PostMapping(value = "/upload")
    public PortfolioUploadResDto uploadPortfolio(@RequestBody PortfolioUploadReqDto reqDto) {
        return portfolioService.uploadPortfolio(reqDto);
    }
}

✔️ PortfolioUploadReqDto (포트폴리오 업로드 요청 DTO)

=> 여기서 요청으로 받는 fileUrl값은 프론트측에서 presignedUrl.split('?')[0]을 통해 구한 후 요청으로 보내면 된다!!

package com.example.Premind_BE.domain.portfolio.dto.request;

import io.swagger.v3.oas.annotations.media.Schema;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.List;

@Data
@AllArgsConstructor
@NoArgsConstructor
@Schema(description = "포트폴리오 업로드를 위한 요청 DTO")
public class PortfolioUploadReqDto {
    @Schema(description = "선택한 직무의 대분류 ID값")
    private Long jobMajorId;
    @Schema(description = "선택한 직무의 중분류 ID값")
    private Long jobMiddleId;
    @Schema(description = "선택한 직무의 소분류 ID값")
    private Long jobMinorId;
    @Schema(description = "포트폴리오 제목")
    private String title;
    @Schema(description = "포트폴리오 지원 기업명")
    private String company;
    @Schema(description = "포트폴리오 질문-답변 항목 리스트")
    private List<PortfolioSectionReqDto> qaList;
    @Schema(description = "업로드된 S3 파일 경로, presignedUrl.split('?')[0] 값이다.")
    private String fileUrl;

}

✔️ PortfolioService

public PortfolioUploadResDto uploadPortfolio(PortfolioUploadReqDto reqDto) {
        List<JobCategory> jobCategories = jobService.findJobCategory(reqDto.getJobMajorId(), reqDto.getJobMiddleId(), reqDto.getJobMinorId());
        Portfolio portfolio = Portfolio.builder()
                .user(getCurrentMember())
                .jobMajor(jobCategories.get(0))
                .jobMiddle(jobCategories.get(1))
                .jobMinor(jobCategories.get(2))
                .title(reqDto.getTitle())
                .company(reqDto.getCompany())
                .filePath(reqDto.getFileUrl())
                .createdDate(LocalDateTime.now())
                .build();

        log.info("Portfolio created with title: {}", portfolio.getTitle());

        List<PortfolioSectionReqDto> sectionList = reqDto.getQaList();
        for (int i = 0; i < sectionList.size(); i++) {
            PortfolioSectionReqDto section = sectionList.get(i);
            PortfolioSection resumeSection = PortfolioSection.builder()
                    .sequence(i + 1)
                    .question(section.getQuestion())
                    .answer(section.getAnswer())
                    .build();
            portfolio.addSection(resumeSection);
        }

        portfolioRepository.save(portfolio);

        return new PortfolioUploadResDto(portfolio.getId());
    }

https://www.acmicpc.net/problem/1010

✔️관련 알고리즘 개념

조합

☑️ 문제 분석

• 문제 조건에 N ≤ M 조건에 따라 서쪽 사이트가 동쪽 사이트보다 작거나 같다는 것을 알 수 있다. 최대한 많은 다리를 지으려면 서쪽 사이트는 모두 다리로 연결될 수 밖에 없다. 그렇다면 서쪽 사이트의 개수만큼 동쪽에 있는 사이트를 선택해서 이어 주면 된다.
• 즉, 연산이 최종적으로 MCN이 되는 것이다.
  • 예시 입력1 2C2 = 1
  • 예시 입력2 5C1 = 5
  • 예시 입력3 29C15 = 67863915
• 조합 점화식
  • nCr = nCr-1 + n-1Cr-1 을 사용하여 코드를 작성한다.

☑️ 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 개수

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            System.out.println(combination(N, M));
        }
    }

    public static int combination(int N, int M) {
        int[][] p = new int[M+1][M+1];

        for (int i = 0; i <= M; i++) {
            for (int j = 0; j <= i; j++) {
                if(j == 0 || j == i)
                    p[i][j] = 1;
                else p[i][j] = p[i-1][j] + p[i-1][j-1];
            }
        }
        return p[M][N];
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음

https://www.acmicpc.net/problem/14565

✔️관련 알고리즘 개념

확장 유클리드 호제법 ⭐⭐⭐

☑️ 문제 분석

• 덧셈역을 구하는 것은 어렵지 않다.

  • 덧셈역은 (a + b) % n = 0을 만족하는 b의 값을 찾는 것이다.
  • 여기서 a, b의 값은 0 <= a, b < n 을 만족한다.
  • 따라서 덧셈역은 그냥 n - a로 계산하면 된다.
    • b = n - a (n > a이므로 n - a > 0일 것이다. 또한 n에서 0혹은 양수 값을 갖는 a값을 빼므로 b는 역시 n보다 작은 값을 가질 수 밖에 없으므로 0 <= b < n값을 갖는 다는 것은 자동으로 만족이 된다.)

  ---

• 곱셈역

  • 곱셈역은 확장 유클리드 호제법을 이용하여 문제를 푼다.
  • 여기서 확장 유클리는 호제법이란 ax+by=gcd(a, b)를 만족하는 정수 해 x, y 값을 찾는 알고리즘이다.
  • 하지만 (a*c)%n=1의 식을 어떻게 ax+by=c와 같은 식으로 해석해야 할지 어려웠다.

✅ (a * c) % n = 1 해석 여기서 (a * c)의 값은 n으로 나누었을 때 나머지 값이 1이 나와야 하므로 a x c = 1 x n + 1 ⇒ a x c - 1 x n = 1 a x c = 2 x n + 1 ⇒ a x c - 2 x n = 1 a x c = 3 x n + 1 ⇒ a x c - 3 x n = 1 a x c = 4 x n + 1 ⇒ a x c - 4 x n = 1 … 이런식들이 나온다. 근데 문제에서는 a, n의 값을 알고 있다. 예시 입력과 같이 n = 26, a = 11이라고 주어져 있다면 11c - 26d = 1을 만족시키는 정수해 c, d를 구하는 것 같다. 여기서 나오는 해 c가 곱셈역의 값이 된다. (단, c는 0~n-1사이의 정수여야 한다.) (여기서 d는 위의 식에서 1xn, 2xn, 3xn에서 변화하는 값이 1, 2, 3을 나타낸 것이다.)

• 그렇다면 예시입력 1: 26x’ - 11y’ = 1을 확장 유클리드 호제법을 통해 곱셈역을 구해보자

   ![](https://velog.velcdn.com/images/jina_ham/post/2fc2e453-8a59-41f3-825c-94d3a1199d6c/image.png)

  ⇒ 여기서 x값은 -7로 나오지만 곱셈역 c는 0~25 사이의 값을 가져야 한다.

** ✔️모듈러 연산** 이럴 땐 s값 (-7) 에 26 씩 더해가면서 양수가 되게 만들면 된다. 실제 식으로 보면 다음과 같습니다. 11 * (-7 + 26 - 26) + 26 * 3 = 1 로 바꿀 수 있고, 11 * (19 - 26) + 26 * 3 = 1 11 * 19 + 26 * (-11 + 3) = 1 11 * 19 + 26 * (-8) = 1 로 변형이 가능하기 때문이다.

※ 모듈러 연산은 결과 값에 N을 아무리 많이 더해도 결국 같은 값을 얻는다 연산이다.

• 따라서 예시 입력1의 최종 곱셈역은 -7에 26을 더한 -7 + 26 = 19이다.

☑️ 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Long.parseLong(st.nextToken());
        long A = Long.parseLong(st.nextToken());

        long addInverse = (N - A);

        if(gcd(A, N) != 1) System.out.println(addInverse + " " + -1);
        else {
            long result = multiplyInverse(A, N)[0];
            while(result < 0) { // 해가 음수가 나오면 양수로 보정하기 
                result += N;
            }
            System.out.println(addInverse + " " + result);
        }
    }

    // 곲셈역 구하기 (확장 유클리드 호제법 사용)
    private static long[] multiplyInverse(long A, long N) {
        long[] ret = new long[2]; // ret은 정수 해 x, y를 저장하는 배열
        if (N == 0) {
            ret[0] = 1;
            ret[1] = 0; // x = 1, y = 0
            return ret;
        }
        long q = A / N; // 몫
        long[] v = multiplyInverse(N, A % N);  // 재귀적으로 확장 유클리드, v는 이전 x', y'값을 저장하는 배열
        ret[0] = v[1]; // x = y'
        ret[1] = v[0] - v[1] * q; // y = x' - y' * q
        return ret;
    }

    private static long gcd(long a, long b) {
        if(b == 0) return a;
        else return gcd(b, a % b);
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 곱셈역을 구하는 과정을 확장 유클리드 호제법과 연관시켜 문제를 해결하는 것이 어려웠다.

https://www.acmicpc.net/problem/1735

✔️관련 알고리즘 개념

유클리드 호제법

☑️ 문제 분석

• 예시 입력이 2/7 + 3/5이면 두 분수를 7과 5의 곱으로 통분한다.
  • 해당 예시 입력은 35로 통분해준다.
  • 10/35 + 21/35 = 31/35이고 계산 결과가 기약분수가 아니라면
  • 분모, 분자의 최대 공약수로 나눠준다.
    • 최대 공약수를 구할 때는 유클리드 호제법에 따라 gcd함수를 구현하여 구한다.

☑️ 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());

        // 통분해서 분수 계산하기
        a *= d;
        c *= b;

        int numerator = a + c;
        int denominator = b * d;

        int gcd = gcd(numerator, denominator);
        System.out.println(numerator / gcd + " " + denominator / gcd);
    }

    static int gcd(int a, int b) {
        if(b == 0) return a;
        else return gcd(b, a%b);
    }
}

☑️ 채점 결과 : 맞음

☑️ 어려웠던 점

• 없음

https://www.acmicpc.net/problem/19577

✔️관련 알고리즘 개념 - 오일러피 함수

오일러피

☑️ 문제 분석

어떤 양의 정수 n이 있다고 할 때, xφ(x) = n을 만족하는 양의 정수 x가 존재하는가?

양의 정수 x가 존재하면 ⇒ 최소의 x를, 존재하지 않으면 ⇒ −1을 출력한다.

위 조건을 만족하도록 알고리즘을 구성해야 한다.

⇒ 여기서 x값은 n보다 작거나 같은 양의 정수에서 찾으면 된다.

⇒ 만약 x가 n보다 큰 양의 정수라면 x∅[x] > n이 될 것이기 때문에 문제의 조건을 만족할 수가 없기 때문이다.

• 예시 입력 1과 같이 n = 2라고 주어진다면

  

  x∅[x] = n을 만족하는 최소 x값은 2이다.

  2 x ∅[2] = 2 * 1 = 2값으로 2와 같으므로 양의 정수 x가 존재하고 그 최소값이 2이므로 2를 출력한다.

• 예시 입력 2와 같이 n = 3이라고 주어진다면

  

• x∅[x] = n을 만족하는 양의 정수 x가 존재하는지 확인해야 한다.

  • x = 2일 때, 2 * ∅[2] ≠ 3
  • x = 3일 때, 3 * ∅[3] ≠ 3 이므로 양의 정수 x가 존재하지 않으므로 -1을 출력한다.

• 예시 입력 3과 같이 n = 20이라고 주어진다면

  

- x를 2부터 반복했을 때, x = 2, 3, 4일 때는 조건을 만족하지 않는다.
- x = 5일 때, 5 * ∅[5] = 5 * 4 = 20 == 20이므로 이를 만족하는 최소 양의 정수값은 5이므로 5를 출력하고 반복문을 멈춘다.

위의 예시 입력을 토대로 문제 풀이 순서롤 써보면

1. n을 입력받은 다음 ∅[n]함수를 정의한다.
2. 1~n까지의 값을 갖는 ∅[n]함수를 정의한다.
3. ∅[n] 배열에서 인덱스를 앞에서 부터 반복하면서 x∅[x] == n를 만족하는 양의 정수 n이 존재하는지 찾는다.

⇒ 이 방법은 메모리 초과가 발생한다.

그래서 문제 풀이를 수정해보았다.

1. n을 입력받은 다음 n보다 작거나 같은수를 2부터 차례대로 반복하며
2. 문제 조건을 만족하는 x값을 찾는다. (위의 방법과 다른 점은 x에 대한 오일러 피 함수를 따로 정의하여 전체 오일러피 배열을 정의하는 것이 아니라 하나의 x값에 대한 오일러피 값을 그때 그때 계산하는 것이다.)
3. 만족하는 x값을 찾으면 결과 출력

⇒ 하지만 이 방식은 시간초과가 발생한다. 탐색시 불필요한 탐색을 제거하는 방향으로 가야 한다.

⚠️여기가 이 문제 해결의 핵심이다!!!

우리는 문제를 해결하기 위해 n보다 작은 모든 수에 대해 반복할 필요는 없다. x는 정수고, φ(x)도 정수고, n도 정수이다. 식을 φ(x) = n/x로 변형해서 생각해보면, φ(x)가 정수가 나오려면 n/x역시 정수가 나와야 한다. n/x가 정수가 나오려면 x가 n의 약수인 경우밖에 없다. 바꿔 말해서 이제 이 문제는 n의 약수인 x에 대해 φ(x)를 구하는 문제로 바뀌게 됩니다. ⇒ n에 대한 약수 배열을 구한 후 해당 배열을 순회하면서 문제를 푼다.

☑️ 코드

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

public class Main {
    static int n;

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

        int result = -1;

        // 약수만 순회하도록 개선
        for (int x : getDivisors(n)) {
            if (x * phi(x) == n) {
                result = x;
                break;
            }
        }

        System.out.println(result);
    }

    // 약수 리스트를 반환하는 함수
    private static ArrayList<Integer> getDivisors(int num) {
        ArrayList<Integer> list = new ArrayList<>(); // num의 약수를 저장하는 배열 초기화
        for (int i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                list.add(i);
                if (i != num / i) list.add(num / i);
            }
        }
        list.sort(Integer::compareTo); // 작은 수부터 탐색하게 정렬
        return list;
    }

    // 오일러 피 함수
    private static int phi(int x) {
        int value = x;
        int temp = x;

        for (int i = 2; i * i <= temp; i++) {
            if (temp % i == 0) {
                value = value - value / i;
                while (temp % i == 0) temp /= i;
            }
        }
        if (temp > 1) {
            value = value - value / temp;
        }
        return value;
    }
}

☑️ 채점 결과 : 메모리 초과 → 시간 초과 → 맞음

(n의 소수 배열을 별도로 생성하여 답을 구하는 과정은 gpt도움을 받음)

☑️ 어려웠던 점

• 탐색 조건을 추가하여 시간 초과 문제를 해결하는 것이 어려움