두 원소 그룹의 대표노드끼리 연결하는 것은 상관 없지만, 그룹 내부의 모든 원소가 연결되어있는 것을 설정해줘야할 필요가 있을 때 신경을 써 줘야함.

find

    static int find(int n){
        if(n == rooted[n]){
            return n;
        }else{
            return rooted[n] = find(rooted[n]);
        }
    }

두 그룹의 대표 노드끼리 연결

    static void union(int a, int b){
        a = find(a);
        b = find(b);
        if(a != b){
            rooted[b] = a;
        }
    }

두 그룹간의 모든 노드가 대표노드를 똑같이 가지게함.

   static void union(int a, int b){
        int fa = find(a);
        int fb = find(b);
        if(a != b){
            for(int i = 0; i<n; i++){
                if(rooted[i] == fb){
                    rooted[i] = fa;
                }
            }
        }
    }

checkSame

모든 인덱스를 탐색해야하고, 해당 건수가 많다면 비효율적임.. 이를 통해서 같은 부모 노드를 가지는지 확인하기 위해 find를 한번 더 호출해서 최종 부모 노드까지 재귀탐색 할 수 있도록 확인

    static boolean checkSame(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b){
            return true;
        }
        else{
            return false;
        }
    }

현재 위치보다 큰 수를 어떻게 구할 수 있을까 고민한 문제였다. 최대 크기가 백만번이기 때문에, 이중 포문을 사용한다면 무조건 시간 초과 발생

제일 먼저 스택이 떠오름.

• 스택이 비어있다면, 그냥 삽입
• 비어있지 않다면
  • 스택 top이 현재 index의 값보다 크거나 같다면 그냥 삽입
  • 스택 top이 현재 index의 값보다 작다면,
    • 스택 top이 크거나 같을 때 까지 모두 pop하여 pop된 숫자들의 오큰수를 현재 index의 값으로 설정함.

이쁘게 코드화로 한다면?

Stack<Num> stack = new Stack<>();
int[] NGE = new int[n];
for(int i = 0; i<n; i++){
    while(!stack.isEmpty() && stack.peek().value < nums[i].value){
        Num top = stack.pop();
        NGE[top.index] = nums[i].value;
    }

        stack.push(nums[i]);
    }

while(!stack.isEmpty()){
    Num top = stack.pop();
    NGE[top.index] = -1;
}

• 스택이 비어있지 않고, 스택에 들어있는 탑 값이 현재 인덱스의 값보다 작다면

  • 스택 pop(), 그리고 pop된 숫자의 인덱스에 오큰수로 현재 인덱스의 값을 채워넣음.

• 그리고 나서 현재 수를 스택에 삽입

• 모두 순회한 후에, 아직 스택에 남아 있는 값은 오큰수가 존재하지 않는 수

시간 복잡도

전체 숫자의 개수 n과 내부에 스택 순회하는 수 (현재 값보다 이전에 작은 값이 존재할 때) 백만개의 오름차순이라고 가정한다면 : O(2n) 백만개의 내림차순이라고 가정한다면 : 스택에 n번 삽입 O(n) + 스택에서 오큰수가 없는 수 채워넣기 O(n)

최악의 경우의수 : O(n)

인줄 알았는데, 마지막 출력부에서 문제가 발생한듯하다. for문으로 출력출력출력을 하니까 시간초과가 나고, BufferedWriter를 사용하니 통과하였음..

//시간 초과 난 출력부
        for(int i = 0; i<n; i++){
            System.out.print(NGE[i] + " " );
        }

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

public class BackJoonMemo {

    static class Num{
        int value;
        int index;

        Num (int v, int i){
           this.value = v;
           this.index = i;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

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

        Stack<Num> stack = new Stack<>();
        int[] NGE = new int[n];
        for(int i = 0; i<n; i++){
            while(!stack.isEmpty() && stack.peek().value < nums[i].value){
                Num top = stack.pop();
                NGE[top.index] = nums[i].value;
            }

            stack.push(nums[i]);
        }

        while(!stack.isEmpty()){
            Num top = stack.pop();
            NGE[top.index] = -1;
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i = 0; i<n; i++){
            bw.write(NGE[i] + " " );
        }
        bw.write("\n");
        bw.flush();

        br.close();
        bw.close();

    }

}

결과

접근

Dijkstra 알고리즘을 써야하는 것을 미리 알고 접근하였음.

일반적인 다익스트라 알고리즘은 항상 탐색한 경로에서 갈 수 있는 최단 거리를 방문하고, 최단거리를 만들어 가면서 한번 방문한 노드는 재방문하지 않음.

하지만 여기서 요구하는 최단거리는 거리에 따른 k번째 경로를 요구한다.

그래서 기본적인 다익스트라에 요구되는 "재방문하지 않는다." 라는 조건을 없애고, 같은 노드에 여러 번 들어가면서 해당 노드로의 k번째 경로를 만들어주는 것을 목표로 하였음.

기본 조건

• 일반 Dijkstra
  • 처음 방문한 노드라면(이미 방문한 노드가 아니라면)
  • 또는, 재차 방문 했을 때, 지나온 거리가 현재 노드로의 최단 거리보다 작을 때

• k번째 최단거리를 구하기 위한 조건
  • 현재 구한 거리의 개수가 k 보다 작을 때, 해당 노드로의 거리 리스트에 추가함
  • k보다 크거나 같다면, k번째에 위치한 최단거리보다 작다면 해당 위치에 새로운 최단 거리를 삽입한다.

1) 여기서 m은 최대 200만개 이고, 구할 수 있는 최대 최단거리의 개수 k는 100개가 최대이므로, 최단거리를 나올때마다 다익스트라 순환큐에 집어 넣으면 당연히 시간초과가 날 것으로 생각하였다.

2) 그래서 노드 i의 k번째 최단거리 리스트에 삽입하기 위해서 조건을 충족하지 않거나, 이미 k번째가 완성되어서, 계속해서 k번째 최단거리보다 더 큰 거리의 값이 나온다면 큐에 더 이상 들어가지 않도록 제한을 걸 수 있도록 구현하기로 하였다.

3) 또한 값을 삽입하기 위한 k번쨰 위치 등을 찾기 위해서 200만이나 되는 간선에 대한 부담을 줄이기 위해 이진탐색을 통해서 삽입 위치를 빠르게 찾을 수 있었다.

코드

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

public class BackJoonMemo {

    // 1) 노드 리스트를 구하기 위한 커스텀 클래스 
    static class Node implements Comparable<Node>{
        int vertex;
        int time;
        // 1-1) k번째 최단 경로를 우선순위 큐로 판별하기 위한 변수
        int stackedTime; 

        public int compareTo(Node n){
            return this.stackedTime - n.stackedTime;
        }

        Node(int n, int t, int st){
            this.vertex = n;
            this.time = t;
            this.stackedTime = st;
        }
    }

    static ArrayList<Node>[] edges; // i번째 노드에 연결된 간선 목록
    static ArrayList<Integer>[] distance; // i번째 노드로의 최단 경로 목록
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // n = 노드의 수, m = 간선의 수, k = 구하고자 하는 최단 거리의 번째
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());;
        int k = Integer.parseInt(st.nextToken());;

        edges = new ArrayList[n+1];
        distance = new ArrayList[n+1];
        for(int i = 1; i<=n; i++){
            edges[i] = new ArrayList<>();
            distance[i] = 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());
            int c = Integer.parseInt(st.nextToken());

            // 처음에는 최단 경로 스택을 간선의 가중치부터 시작
            edges[a].add(new Node(b, c, c));
        }

        recursiveDijkstra(1, k);

        for(int i = 1; i<=n; i++){
            if(distance[i].size() < k){
                System.out.println(-1);
            }else{
                System.out.println(distance[i].get(k-1));
            }
        }

        for(int i = 1 ;i <=n ; i++){

        }

    }

    static void recursiveDijkstra(int start, int k){
        PriorityQueue<Node> queue = new PriorityQueue<>();

        queue.add(new Node(start, 0, 0));
        distance[start].add(0);

        // 2) 일반적인 다익스트라 알고리즘을 따르되, 재방문이 가능하다.
        while(!queue.isEmpty()){
            Node currNode = queue.poll();

            ArrayList<Node> edge = edges[currNode.vertex];
            for(Node node : edge){
                // 2-1) 현재 최단 거리에서 다음 노드까지 걸리는 새로운 최단거리
                int newDist = currNode.stackedTime + node.time;

                // 2-2) 만일 아직 해당 노드까지 최단거리 개수가 k가 미만이거나,
                // k번째 보다 크거나 같다면, k번째에 위치한 최단거리가 현재 구한 
                // 새로운 최단거리와 비교해서 더 작을 때 새로운 k번째 최단거리로 판별한다.
                int nextNodeDistSize = distance[node.vertex].size();
                if(nextNodeDistSize < k || distance[node.vertex].get(nextNodeDistSize - 1) > newDist){
                // 3) 또한, k의 크기와 간선이 최대 100과 200만개이기 때문에,
                //    간선의 개수에 따른 모든 경우의 수를 큐에 집어넣으면 
                //    너무 많고 탐색하는데도 오래걸리기 때문에 이진탐색을 통해서 삽입할 위치를 찾음.
                    binarySearchInsert(node.vertex, newDist);
                    queue.add(new Node(node.vertex, node.time, newDist));
                }
            }
        }
    }

    static void binarySearchInsert(int vertex, int value){
        ArrayList<Integer> currDistances = distance[vertex];

        int left = 0;
        int right = currDistances.size() - 1;

        // 찾으려는 위치의 값보다 현재 넣으려는 최단경로의 길이가 더 작다면, 해당위치의 오른쪽에 삽입
        // "" 더 크다면, 해당 위치의 왼쪽에 삽입
        // "" 크기가 같은 최단경로라면, 해당위치에 그대로 삽입.
        int mid;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(currDistances.get(mid) < value){
                left = mid + 1;
            }else if (currDistances.get(mid) > value){
                right = mid - 1;
            }else{
                left = mid;
                break;
            }
        }

        currDistances.add(left, value);

    }

}

실수한 부분

k번째 최단거리를 집어넣는 조건에서 아래 처럼, 현재 노드로의 최단거리에 마지막 값이랑 비교해서 시간초과가 났다. nextNodeDistSize - 1 -> k - 1로 변경하였음. 처음에 생각했는데 급하게 한다고 해당 부분에서 실수했고, 바로 고쳐서 정답으로 하였다.

if(nextNodeDistSize < k || distance[node.vertex].get(nextNodeDistSize - 1) > newDist){
                    binarySearchInsert(node.vertex, newDist);
                    queue.add(new Node(node.vertex, node.time, newDist));
                }

결과

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

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

public class BackJoonMemo {

    static class ElectricLine implements Comparable<ElectricLine>{
        int start;
        int end;

        ElectricLine(int start, int end){
            this.start = start;
            this.end = end;
        }

        public int compareTo(ElectricLine e){
            return this.start - e.start;
        }
    }


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

        int n = Integer.parseInt(st.nextToken());

        ElectricLine[] lines = new ElectricLine[n];
        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            lines[i] = new ElectricLine(start, end);
        }

        Arrays.sort(lines);

        int[] lis = new int[n];
        int max = 0;
        for(int line = 0; line< n; line++){
            lis[line] = 1;
            for(int j = 0; j<line; j++){
                if(lineUnCross(lines[line], lines[j])){
                    lis[line] = Math.max(lis[line], lis[j] + 1);
                }
            }

            max = Math.max(max, lis[line]);
        }

        /*for(int i = 0; i<n; i++){
            System.out.println(lines[i].start + ", " + lines[i].end + " : " + lis[i]);
        }*/

        System.out.println(n - max);
    }

    static boolean lineUnCross(ElectricLine e1, ElectricLine e2){
        if(e1.start < e2.start){
            if(e1.end < e2.end){ // (안 겹침)
                return true;
            }
            else{ // e1.end > e2.end (겹침)
                return false;
            }
        }

        else { // e1.start > e2.start (둘이 같은 경우는 X)
            if(e1.end < e2.end){ // (겹침)
                return false;
            }
            else{  // (안 겹침)
                return true;
            }
        }
    }
}

• 1) 현재 만드려는 금액이, 현재 선택하려는 코인의 금액보다 작을 때

  • 이전에 현재 금액을 만들 수 있었던 경우의 수를 선택 dp[i][j] = dp[i-1][j]

• 2) 현재 만드려는 금액이, 현재 선택하려는 코인의 금액보다 크거나 같을 때

  • 2-1) 현재 선택한 코인 1개로만 해당 금액을 만들 수 있을 때
    • dp[i][j] = 1
  • 2-2) 현재 만드려는 금액에서 선택한 코인을 뺀 값이 만들어져 있지 않을 때
    • dp[i][j] = dp[i-1][j]
  • 2-3) 1개로도 금액을 못 만들고, 현재 만드려는 금액에서 선택한 코인을 뺀 값이 존재할 때
    • dp[i][j] = Math.min(dp[i][gap] + 1, dp[i-1][j])

2-2) 조건에 2-1)번 조건을 같이 묶으려고 했었을 때, 만들 수 없는 금액에 동전 선택의 경우의 수가 할당 되버림 if(dp[i][gap] == 0 || gap != 0) 모두 0으로 만들어 져 버림.

그래서 gap != 0이 부분 빼버리고 그냥 진행하려고,

if(gap < 0){
     dp[i][j] = dp[i-1][j];
}
else{ // gap >= 0
    if(dp[i][gap] == 0){
        dp[i][j] = dp[i-1][j];
    }else{
        dp[i][j] = Math.min(dp[i][gap] + 1 , dp[i-1][j]);
    }
}

이런식으로 해버리니까 만들 수 없는 금액에 동전의 경우의 수가 할당 되어 버림 6에서 1개의 개수로 만들 수 있다고 나옴;;

public class BackJoonMemo {


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

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n+1][k+1];

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


        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= k; j++){
                int gap = j - coins[i-1];
                if(gap < 0){
                    dp[i][j] = dp[i-1][j];
                }else{ // gap >= 0
                    if(gap == 0){
                        dp[i][j] = 1;
                    }
                    else if(dp[i][gap] == 0){
                        dp[i][j] = dp[i-1][j];
                    }
                    else{
                        if(dp[i][gap] != 0){
                            dp[i][j] = dp[i][gap] + 1;
                            if(dp[i-1][j] != 0){
                                dp[i][j] = Math.min(dp[i][j], dp[i-1][j]);
                            }
                        }

                    }
                }
            }
        }


        /*for(int i = 1; i<=n; i++){
            System.out.print(coins[i-1] + " ");
            for(int j = 0; j<= k; j++){
                System.out.print(j + " : " + dp[i][j] + ", ");
            }
            System.out.println();
        }*/


        System.out.println(dp[n][k] == 0 ? -1 : dp[n][k]);
    }
}

상어가 이동할 수 있는 경우의 수는, 우선순위를 고려해야함. 만일, 3번 이동안에 물고기가 없다면? 이동 우선순위 숫자를 정해진데로 해야함.

이동 가능한 경우의 수 중에, 각 칸에서 가장 우선순위가 높은 경우의 수

또한, 한번 이동하고 원위치로도 다시 이동이 가능하다. 다만, 이미 물고기를 먹기 위해 이동을 한번이상 했다면, 물고기 수는 카운트 X

처음에 boolean으로 방문 기록을 체크했다가, dfs형태로 구현하면서 함수 리턴시 visited를 다시 false로 하는 과정에서 중복으로 방문하는 곳도 같이 초기화가 되어서 값이 한번 꼬임.

또한, 커스텀 클래스를 사용하여 내부 자료구조를 활용하려 했으나 깊은 복사/ 얕은 복사 이슈로 인스턴스를 구분하는데서 실수함.

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

public class BackJoonMemo2 {

    static class Fish{
        int x, y;
        Deque<Integer> fishes;

        Fish(int x, int y){
            this.x = x;
            this.y = y;
            this.fishes = new LinkedList<>();
        }
    }

    static int[][] visited;
    static int[][] shark;
    static int[][] smell;
    static Fish[][] fishState;
    static String sharksPath;
    static int sx, sy;

    static int pathMaxFishes;

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

        // 물고기 수
        int m = Integer.parseInt(st.nextToken());

        // 상어 마법 연습 횟수
        int s = Integer.parseInt(st.nextToken());


        fishState = new Fish[5][5];
        initFishFields(fishState);

        // 물고기 첫 위치
        for(int i = 0; i< m; i++){
            st = new StringTokenizer(br.readLine());
            int fx = Integer.parseInt(st.nextToken());
            int fy = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            fishState[fx][fy].fishes.add(d);
        }

        // 상어 첫 위치
        st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken());
        sy = Integer.parseInt(st.nextToken());
        shark = new int[5][5];
        shark[sx][sy] = 1;
        visited = new int[5][5];

        // 물고기 냄새
        smell = new int[5][5];

        // 물고기 복사 마법 실행(횟수 만큼)
        for(int i = 0; i< s; i++){
            System.out.print("Practice <" + (i +1) + "> \n" );
            // 1. 물고기 복사
            Fish[][] fishCopy = fishCopy();////

            // 2. 물고기 이동
            fishMove(i+1);////
            System.out.println("fish Moved");
            printFields(fishState);

            // 3. 상어 이동
            System.out.println("shark Moved : ");
            System.out.println("before -> sx : " + sx + ", sy : " + sy);
            sharkExceptsFish(i+1);////
            System.out.println("shark Path : " + sharksPath);
            System.out.println("after -> sx : " + sx + ", sy : " + sy);

            System.out.println("\nsmell gone");
            System.out.println("before");
            for(int x = 1; x<=4; x++){
                for(int y = 1; y<= 4; y++){
                    System.out.print(smell[x][y] + " ");
                }
                System.out.println();
            }

            // 4. 두번 전물고기 냄새 사라짐
            smellGone(i+1); ////
            System.out.println("after");
            for(int x = 1; x<=4; x++){
                for(int y = 1; y<= 4; y++){
                    System.out.print(smell[x][y] + " ");
                }
                System.out.println();
            }

            // 5. 물고기 복사 완료
            for(int x = 1; x <= 4; x++){
                for(int y = 1; y <= 4; y++){
                    fishState[x][y].fishes.addAll(fishCopy[x][y].fishes);
                }
            }

            System.out.println("\nfish Cloned");
            printFields(fishState);
        }

        // 마법 종료 후 남아있는 물고기 수 확인
        int result = 0;
        for(int x = 1; x <= 4; x++){
            for(int y = 1; y <= 4; y++){
                result += fishState[x][y].fishes.size();
            }
        }

        System.out.println("result : " + result);


    }
    static Fish[][] fishCopy(){ // 1) 물고기 복사
        Fish[][] copy = new Fish[5][5];
        initFishFields(copy);

        for(int i = 1; i<= 4; i++){
            for(int j =1; j<=4; j++){
                copy[i][j].fishes.addAll(fishState[i][j].fishes);
            }
        }

        return copy;
    }

    static void fishMove(int pracCount){ // 2) 물고기 한칸 이동
        Fish[][] movedFishFields = new Fish[5][5];
        initFishFields(movedFishFields);

        for(int i = 1; i<= 4; i++){
            for(int j = 1; j<=4; j++){
                Deque<Integer> fieldsFish = fishState[i][j].fishes;
                int remainFish = fieldsFish.size(); // 실수부분
                for(int f = 0; f<remainFish; f++){
                    int[] whereToMove = getFishDirection(i, j, fieldsFish.poll(), 1); // return moved R, C, Dir
                    int movedI = whereToMove[0];
                    int movedJ = whereToMove[1];
                    int movedD = whereToMove[2];
                    movedFishFields[movedI][movedJ].fishes.add(movedD);
                }
            }
        }

        fishState = movedFishFields;
    }

    static int[] getFishDirection(int i, int j, int dir, int spin){ // 2-1) 물고기 이동 방향 설정
        if(spin > 8){
            return new int[]{i, j, dir};
        }

        int movedR = i;
        int movedC = j;

        if(dir == 1){        // 왼쪽
            movedC--;
        }else if (dir == 2){ // 왼쪽 대각선 위
            movedR--;
            movedC--;
        }else if (dir == 3){ // 위
            movedR--;
        }else if (dir == 4){ // 오른쪽 대각선 위
            movedR--;
            movedC++;
        }else if (dir == 5){ // 오른쪽
            movedC++;
        }else if (dir == 6){ // 오른쪽 대각선 아래
            movedR++;
            movedC++;
        }else if (dir == 7){ // 아래
            movedR++;
        }else if (dir == 8){ // 왼쪽 대각선 아래
            movedR++;
            movedC--;
        }


        if(movedR < 1 || movedR > 4 || movedC < 1 || movedC > 4){
            return getFishDirection(i, j, dir - 1 == 0 ? 8 : dir -1, spin + 1);
        }
        else if(smell[movedR][movedC] != 0){
            return getFishDirection(i, j, dir - 1 == 0 ? 8 : dir -1, spin + 1);
        }
        else if(shark[movedR][movedC] != 0){
            return getFishDirection(i, j, dir - 1 == 0 ? 8 : dir -1, spin + 1);
        }

        return new int[]{movedR, movedC, dir};
    }

    // 3) 상어 이동
    static void sharkExceptsFish(int pracCount){
        sharksPath = "555";
        pathMaxFishes = 0;

        if(sx-1 >= 1 && sx <= 4){
            sharksMoving(sx-1, sy, "1", fishState[sx-1][sy].fishes.size()); // 상
        }
        if(sy - 1 >= 1 && sy <= 4){
            sharksMoving(sx, sy-1, "2", fishState[sx][sy-1].fishes.size()); // 좌
        }
        if(sx + 1 <= 4 && sx >= 1){
            sharksMoving(sx+1, sy, "3", fishState[sx+1][sy].fishes.size()); // 하
        }
        if(sy + 1 <= 4 && sy >= 1){
            sharksMoving(sx, sy+1, "4", fishState[sx][sy+1].fishes.size()); // 우
        }

        char[] pathSeq = sharksPath.toCharArray();

        // 물고기 냄새
        fishSmell(pracCount, pathSeq);
    }

    // 3-1) 상어 상/하/좌/우 이동
    static void sharksMoving(int i, int j, String path, int exceptFishes){
        int currPathFishes = exceptFishes;

        if(visited[i][j] >= 1) {
            currPathFishes = exceptFishes - fishState[i][j].fishes.size();
        }

        visited[i][j]++;

        /*for(int x= 1; x<=4 ;x++){
            for(int y = 1; y <= 4; y++){
                System.out.print(visited[x][y] + " ");
            }
            System.out.println();
        }*/

        System.out.println();
        if(path.length() == 3){
            if(pathMaxFishes < currPathFishes){
                pathMaxFishes = currPathFishes;
                sharksPath = path;
                System.out.println("1 " + path + " fishes : " + pathMaxFishes);
            }else if(pathMaxFishes == currPathFishes && path.compareTo(sharksPath) < 0){
                pathMaxFishes = currPathFishes;
                sharksPath = path;
                System.out.println("2 " + path + " fishes : " + pathMaxFishes);
            }
            else{
                System.out.println("0 " + path + " fishes : " + pathMaxFishes);
            }

            System.out.println("---------------");
            visited[i][j]--;
            return;
        }

        if(i - 1 >= 1 && i <= 4) {
            sharksMoving(i - 1, j, path + "1", currPathFishes + fishState[i - 1][j].fishes.size()); // 상
        }
        if(j - 1 >= 1 && j <= 4) {
            sharksMoving(i, j - 1, path + "2", currPathFishes + fishState[i][j - 1].fishes.size()); // 좌
        }
        if(i + 1 <= 4 && i >= 1){
            sharksMoving(i+1, j, path + "3", currPathFishes + fishState[i+1][j].fishes.size()); // 하
        }
        if(j + 1 <= 4 && j >= 1){
            sharksMoving(i, j+1, path + "4", currPathFishes + fishState[i][j+1].fishes.size()); // 우
        }

        visited[i][j]--;
    }

    // 3-2) 상어 지나간 자리 물고기 있으면 물고기 냄새
    static void fishSmell(int pracCount, char[] pathSeq){
        shark[sx][sy] = 0;
        for(char s : pathSeq){
            if(s == '1'){
                sx--;
            }else if(s == '2'){
                sy--;
            }else if(s == '3'){
                sx++;
            }else if(s == '4'){
                sy++;
            }
            if(fishState[sx][sy].fishes.size() >= 1){
                fishState[sx][sy].fishes = new LinkedList<>();
                smell[sx][sy] = pracCount;
            }
        }

        shark[sx][sy] = 1;
    }

    static void smellGone(int pracCount){ //
        for(int i = 1; i<=4 ; i++){
            for(int j = 1; j<= 4; j++){
                if(smell[i][j] <= pracCount - 2){
                    smell[i][j] = 0;
                }
            }
        }
    }

    static void printFields(Fish[][] fList){
        for(int i = 1; i<=4 ; i++){
            for(int j =1 ; j<=4; j++){
                System.out.print(fList[i][j].fishes);
            }
            System.out.println();
        }

        System.out.println();
    }

    static void printFieldsSize(Fish[][] fList){
        for(int i = 1; i<=4 ; i++){
            for(int j =1 ; j<=4; j++){
                System.out.print(fList[i][j].fishes.size()+ " ");
            }
            System.out.println();
        }

        System.out.println();
    }

    static void initFishFields(Fish[][] field){ // 물고기 필드 초기화
        for(int i = 1; i<= 4; i++){
            for(int j = 1; j<= 4; j++){
                field[i][j] = new Fish(i, j);
            }
        }
    }
}

회의시간을 모두 비교하면서 O(n)의 시간으로 진행할 수 있는 방법에 대해 고민함

• 회의의 최대 수는 10만이므로, 하나씩 다 비교한다면 O(n!)으로 시간 무조건 초과

과정

1. 입력 예제를 그려봤을 때, 나열하고 비교하는 순서를 시작 시간이 가장 빠른 순으로 해야겠다고 생각함.
2. 시작 시간이 같을 경우에는 더 빨리 끝나는 회의를 우선 순위로 둠.

-> 나열 후 하나씩 큐에 삽입하면서, 마지막 회의가 추가로 진행할 회의보다 빨리 끝나면 그대로 큐에 넣고, 추가로 진행할 회의가 마지막 회의보다 더 빨리 시작하고, 더 빨리 끝나면 마지막회의를 삭제한 후 회의를 추가하기.

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

public class Main {
    static class Meeting implements Comparable<Meeting>{
        int hour;
        int start;
        int end;

        @Override
        public int compareTo(Meeting m1){
            if(this.start < m1.start){
                return -1;
            }else if(this.start > m1.start){
                return 1;
            }else{
                return this.end - m1.end;
            }
        }

        Meeting (int start, int end){
            this.start = start;
            this.end = end;
            this.hour = end - start;
        }

    }

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

        // 배달할 설탕의 무게 (kg)
        int n = Integer.parseInt(st.nextToken());
        int start, end;

        Meeting[] meetings = new Meeting[n];

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            meetings[i] = new Meeting(start, end);
        }

        Arrays.sort(meetings);


        Deque<Meeting> meetingList = new LinkedList<>();
        for(int i = 0; i<n; i++){
            //System.out.println(meetings[i].start + ", " + meetings[i].end + ", " + meetings[i].hour);

            if(meetingList.isEmpty()){
                meetingList.add(meetings[i]);
            }

            else{
                Meeting currMeeting = meetingList.getLast();

                if (meetings[i].start < currMeeting.end) {
                    if(meetings[i].end < currMeeting.end){
                        meetingList.removeLast();
                        meetingList.addLast(meetings[i]);
                    }
                }else{
                    meetingList.addLast(meetings[i]);
                }
            }
        }

        System.out.println(meetingList.size());
    }
}

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

public class BackJoonMemo {
    static int[] cards;
    static boolean[] visited;
    static int n, m, result, check;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 배달할 설탕의 무게 (kg)
        n = Integer.parseInt(st.nextToken());
        int five = 0, three = 0;

        int[] sugarW = new int[5001];

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

        sugarW[0] = 0;
        sugarW[3] = 1;
        sugarW[5] = 1;

        for(int i = 6; i<n+1; i++){
            if(sugarW[i-5] != -1){ // 5의 배수일 때
                sugarW[i] = sugarW[i-5] + 1;
            }
            if(sugarW[i-3] != -1){ // 3의 배수일 떄
                if(sugarW[i] != -1){
                    sugarW[i] = Math.min(sugarW[i-3] + 1, sugarW[i]);
                    continue;
                }
                sugarW[i] = sugarW[i-3] + 1;
            }
        }

        //for(int i = 0; i<n+1; i++){
        //    System.out.println(i + ": " + sugarW[i]);
        //}

        System.out.println(sugarW[n]);


    }



}
/**
 * if(n % 5 == 0){ // 5의 배수일 경우
 *                 five += n / 5;
 *                 n %= 5;
 *             }
 *             else if(n % 3 == 0){ // 5의 배수가 아니고 3의 배수 일 경우
 *                 three += n / 3;
 *                 n %= 3;
 *             }
 *             else if(n >= 5){ // 5, 3 배수 어떤 것도 아닌 경우 (5kg 봉지로 가져가는게 제일 적게 들고가는 방법)
 *                 five += n / 5;
 *                 n %= 5;
 *             }
 *             else if(n < 5 && n >= 3){ // 3kg 봉지를 들고갈 수 있는 경우의 수
 *                 three += n / 4;
 *                 n %= 4;
 *             }
 *             else{
 *                 n -= 1;
 *                 validate = true;
 *             }
 */

모범 답안..(그리디)

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());
   int X = 0;

   while(true) {
       if(N%5 == 0) {
           System.out.println(N/5 + X);
           break;
       } else if (N<0) {
           System.out.println(-1);
           break;
       }
       N -= 3;
       X++;
   }
}

}

블랙잭을 룰로 m숫자에 가장 가까운 3개의 카드 조합을 만들어야함..

DP 문제인가 해서 한참 고민하다가 도저히 답이 안 나올거 같아서 문제 유형을 보니 브루트포스라는 힌트를 얻음.

브루트 포스이므로 전체 탐색을 진행 시키도록 함.

case 1

카드 3개를 중복없이 선택하는 경우의 수

• 5 6 7, 5 6 8, 5 6 9

• 6 7 8, 6 7 9, 6 8 9
• 7 8 9

첫 카드는 반드시 전체 카드의 수 n 중에서 n-3 번째 카드만선택 가능하도록 한다.

ex) n = 5 일경우, 인덱스 : 0, 1, 2, 3, 4 이므로 0, 1, 2 까지만 선택해야 Out of Index를 일으키지 않음.

여기에 추가로 카드 3개 선택 후 숫자 합이 m보다 작거나 같고, m과의 차이가 가장 낮은 기준을 지정해주었다.

if (count == 0){
    if(m - value >= 0 && check >= m - value){
        check = m - value;
        result = value;
    }
}

---
### 코드

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

public class BackJoonMemo { static int[] cards; static boolean[] visited; static int n, m, result, check; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine());

    // 카드의 개수 n
    n = Integer.parseInt(st.nextToken());

    // 만들어야할 숫자 m
    m = Integer.parseInt(st.nextToken());

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

    // 카드목록 cards
    cards = new int[n];

    // dfs 방문 기록
    visited = new boolean[n];

    check = Integer.MAX_VALUE;
    for(int i = 0; i<n; i++){
        cards[i] = Integer.parseInt(st.nextToken());
    }
    // 0 ~ n-3 까지의 숫자만 선택하여 길이를 넘지 않는 3개의 카드를 고르기 위한 범위
    for(int i = 0; i<n-2; i++){
        dfs(cards[i], i, 2);
    }
    System.out.println(result);

}

public static void dfs(int value, int index, int count){
    visited[index] = true;
    if (count == 0){
    // 카드를 3장 고르고, 외친 숫자 m에 가장 가까운 기준을 고르기 위함
        if(m - value >= 0 && check >= m - value){
            check = m - value;
            result = value;

            //System.out.println(value + ", " + index + ", " + count + ", " + Arrays.toString(visited));
        }

        visited[index] = false;
        return;
    }

    // 이미 고른 코드 다음 부터 지정하여 중복을 방지
    for(int i = index + 1; i< n; i++){
        if(!visited[i]){
            dfs(value + cards[i], i, count - 1);
        }
    }

    visited[index] = false;

}

}

```

문제를 보 갈피를 못 잡았지만, 문제 유형을 확인하고 정렬과 그리디라는 힌트를 얻은 후 쉽게 도출할 수 있었다.

처음과 마지막 통나무 또한 이어진다는 가정하에 순환구조를 어떻게 표현할지 고민해야했다.

• 우선 통나무 간의 최소 높이를 구할 수 있는 가장 쉬운 방법은 입력된 통나무를 나열하는 것

• 그 후 처음 통나무부터 높이차를 순서대로 양쪽에 삽입하면 뛰는 높이 난이도가 낮은데로 배치가 가능하다.

• 꼭 숫자가 낮은 순으로 올 필요가 없기 때문에, 데크를 사용하여 논리적 순환구조를 바라보면서 뛰었을때 가장 높은 난이도를 계산만해서 도출하였음.

case 1

여기서 왼쪽과 오른쪽에 놓는 기준이 필요하였다.

• 다음에 배치해야할 통나무의 높이(Logs Height)가 왼쪽, 오른쪽과의 차를 비교
• 만일, Logs Height가 왼쪽 통나무의 차와 오른쪽 통나무의 차 중에서
  • 오른쪽 통나무와의 차가 왼쪽 통나무와의 차보다 크거나 같다면 오른쪽에 삽입
  • 왼쪽 통나무와의 차가 오른쪽 통나무와의 차보다 작으면 왼쪽에 삽입

이렇게 조건을 만든 이유는, 만일 차가 더 작은쪽에만 편향적으로 통나무를 배치하다보면 반대쪽(왼쪽 <-> 오른쪽)에 놓이는 통나무는 그 차가 더 높아질 것이기 때문에,

왼쪽에 놓았다면 더 큰 편차를 만들지 않기 위해서 오른쪽에 놓으면서 밸런스를 유지하기 위함

-> 그래야 오른쪽에 놓은 후 왼쪽에도 놓을 준비가 되고, 그 반대의 경우도 안정적으로 문제를 해결할 수 있겠다고 생각하였다.

코드

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

public class BackJoonMemo {

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

        int n = Integer.parseInt(st.nextToken());

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

            st = new StringTokenizer(br.readLine());
            int[] logList = new int[logCount];

            for(int j = 0; j<logCount; j++){
                logList[j] = Integer.parseInt(st.nextToken());
            }
            // 정렬하여 높이가 최소인 순서를 우선 구하기
            Arrays.sort(logList);
            System.out.println(solution(logCount, logList));
        }

    }

    public static int solution(int logCount, int[] logList){
        Deque<Integer> logComb = new LinkedList<>();

        // 데크를 활용하여 양쪽에 높이가 최소인 값들을 넣을 준비
        logComb.add(logList[0]);
        logComb.addFirst(logList[1]);
        int leftDiff, rightDiff, difficulty = 0;
        for(int i = 2; i< logCount; i++){
            leftDiff = Math.abs(logList[i] - logComb.getFirst());
            rightDiff = Math.abs(logList[i] - logComb.getLast());

            // 양쪽끝의 차가 같거나 오른쪽이 더 클 경우에 오른쪽에 통나무 정렬
            if(leftDiff <= rightDiff){
                logComb.addLast(logList[i]);

                difficulty = Math.max(difficulty, rightDiff);
            }
            // 왼쪽 차가 더크면 왼쪽에 통나무 정렬
            else{
                logComb.addFirst(logList[i]);
                difficulty = Math.max(difficulty, leftDiff);
            }
        }

        //System.out.println(logComb);
        return difficulty;
    }

}

결과

아무래도 입력시 정수가 최대 10000개 까지 입력되는데, 여기서

• main에서 10000개를 담기 위한 배열
• solution 함수에 매개변수로 넘겨주는 배열
• 통나무 정렬을 위한 Deque 자료형
  까지 해서 메모리가 꽤 크게 잡혔다.

시간 복잡도는 : 정렬 (nlogn) + 배열 순차 탐색 (O(n))으로 계산 가능하다

DP 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

비용 1,000과 집의 수 1,000을 확인해 봤을 때 1,000 * 1,000 = 1,000,000 int 자료형으로 해결 가능함

case 1

필요한 경우의 수는 현재 집을 선택햇을 때의 최소값은 이전에 선택하지 않은 집에서의 최소값을 더하면 되겠다고 생각했다.

• DP : 점화식
• H : 집 색칠 비용

DP[R] = H[R] + DP[G-1] + DP[B-1] DP[G] = H[G] + DP[R-1] + DP[B-1] DP[B] = H[B] + DP[R-1] + DP[G-1]

이렇게 점화식을 세우면, 색이 겹칠 일 없이 비용의 최소값을 각 색마다 구할 수 있다.

코드

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

public class BackJoonMemo {

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

        int n = Integer.parseInt(st.nextToken());

        int[][] houses = new int[n+1][3];

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

        int[][] dp = new int[n+1][3];
        // 각 색 별 겹치지 않는 최소값 선택
        for(int i = 1; i <= n; i++){
            dp[i][0] = houses[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = houses[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = houses[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
        }

        int r = dp[n][0];
        int g = dp[n][1];
        int b = dp[n][2];

        System.out.println(Math.min(r, Math.min(g, b)));

    }

}

결과

시간복잡도 : O(n)

https://github.com/SUNGIN99/JavaCodingTest/tree/main/%EB%B0%B1%EC%A4%80/Silver/2156.%E2%80%85%ED%8F%AC%EB%8F%84%EC%A3%BC%E2%80%85%EC%8B%9C%EC%8B%9D

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

연속으로 놓여있는 3잔의 경우 마실 수 없다를 점화식에 적용하는 것을 중점으로 고민하였다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

1,000 * 10,000 = 10,000,000 -> int 형으로 해결 가능

n의 범위

1 ≤ n ≤ 10,000 이었기 때문에, n이 어떤 숫자이든 연속된 3잔이란 조건을 만족할 수 있는 방법이 필요하다고 생각함

case 1

n = 3 일때, [1, 2], [1, 3], [2, 3]을 선택하는 경우의 수가 필요하다.

6, 10, 13, 9, 8, 1 에서 3까지 최대로 마실 수 있는 경우의 수는 [2, 3]을 선택했을 때 !

여기서 DP[n-1], DP[n-2] + N[n]을 통해 [1, 2], [1, 3]에 대한 선택의 경우의 수는 고민할 수 있었지만, [2, 3]을 어떻게 구해야하나? 라는 고민이 있었음.

case 2

n = 4 일 때 DP[1], DP[2] 는 이미 쉽게 구할 수 있었다.

• DP[1] = N[1]
• DP[2] = DP[1] + N[2]

n = 4 일 때는 앞에 1을 선택했을 때와 안했을 때의 차이를 고민할 수 있었다.

• 현재 포도주를 선택 O : [1, 2, 4], [1, 3, 4]
• 현재 포도주를 선택 X : [1, 2], [1, 3], [2, 3]

점화식 도출

• 여기서, DP[n-1]의 값이 연속된 2자리일 경우 현재 N[n]을 선택할 수 없다.

• 만일 DP[n-1]이 DP[n-2] + N[n-1]일 경우(N[n-2]가 선택된), N[n]은 선택할 수 없다. 그러므로, DP[n-2] + N[n]의 형태를 만들 수 있음.

• ** 마지막으로, N[n-1]과 N[n]을 더하되, N[n-2]를 포함하지 않는 점화식 기준을 정할 수 있도록, N[n-1] + N[n] + DP[n-3]을 통해 N[n-2]가 포함되지 않은 값을 비교할 수 있다.**

따라서,

• DP[n-1] : 현재 포도주를 마신 양의 수의 합이, 앞의 연속된 포도주를 마셨을 때 보다 작은 경우
• DP[n-2] + N[n]: 현재 포도주를 마시고, N[n-1] 포도주를 마시지 않았을 때의 경우
• DP[n-3] + N[n-1] + N[n] : N[n-2] 포도주를 마시지 않고, 현재와 바로 앞 포도주를 마시는 경우

위 기준을 통해서 코드를 구현하여 정답을 도출할 수 있었다.

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

public class Main {

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

        int n = Integer.parseInt(st.nextToken());

        // 1 ~ n 기준의 index를 맞추기 위해 n+1
        int[] grapeDrinks = new int[n+1];

        for(int i = 1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            grapeDrinks[i]= Integer.parseInt(st.nextToken());

        }

        int[] dp = new int[n+1];
        dp[1] = grapeDrinks[1];

        // n == 1일 경우 N[1]만 도출하면 됨.
        if(n == 1){
            System.out.println(dp[1]);
            return;
        }

        // n >= 2 일 경우 N[1], N[0]을 통해서 비교 가능
        dp[2] = dp[1] + grapeDrinks[2];
        for(int i = 3; i<= n; i++){
            // a1: 현재 포도주를 선택하지 않고, 다음 포도주를 선택할 가능성을 둠.
            int a1 = dp[i-1]; 

            // a2: 현재 포도주를 선택하고, 바로 앞 포도주를 선택하지 않음.
            int a2 = dp[i-2] + grapeDrinks[i];

            // a3: 현재 포도주와 바로 앞 포도주를 선택하지않고, 앞앞 포도주를 선택하지 않음.
            int a3 = grapeDrinks[i] + grapeDrinks[i-1] + dp[i-3];

            dp[i] = Math.max(a1, a2);
            dp[i] = Math.max(dp[i], a3);
        }

        System.out.println(dp[n]);
        //System.out.println(Arrays.toString(grapeDrinks));
        //System.out.println(Arrays.toString(dp));
    }

}

결과

시간복잡도 : O(n)

https://elena90.tistory.com/entry/JAVA-%EB%AC%B4%ED%95%9C%EB%8C%80-%EC%A0%95%EC%88%98-BigInteger-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0

https://steady-coding.tistory.com/176

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

MemberDTO.Request newUser = new MemberDTO.Request("테스트 유저", "test@email.com", "password");

        // response
        Set<AuthorityDto> authorityDtos = new HashSet<>();
        authorityDtos.add(new AuthorityDto("ROLE_TEST"));
        MemberDTO.Response newUserRes = new MemberDTO.Response(newUser.getName(), newUser.getEmail(), authorityDtos);

        when(memberService.create(newUser)).thenReturn(newUserRes);

        ObjectMapper objectMapper = new ObjectMapper();
        String requestBody = objectMapper.writeValueAsString(newUser);

수동 매핑

// ObjectMapper를 직접 사용하여 JSON 문자열을 생성
    ObjectMapper objectMapper = new ObjectMapper();
    ObjectNode requestBodyNode = objectMapper.createObjectNode();
    requestBodyNode.put("name", newUser.getName());
    requestBodyNode.put("email", newUser.getEmail());
    requestBodyNode.put("password", newUser.getPassword());
    String requestBody = requestBodyNode.toString();

https://registry.terraform.io/providers/hashicorp/aws/2.34.0/docs/resources/lb_target_group_attachment

https://registry.terraform.io/providers/hashicorp/aws/latest/docs/resources/instance#attribute-reference

https://registry.terraform.io/providers/hashicorp/aws/latest/docs/resources/vpc

VPC 기본 라우터 테이블

https://registry.terraform.io/providers/hashicorp/aws/latest/docs/resources/default_route_table

VPC

참고블로그 https://blog.outsider.ne.kr/1301 https://gurumee92.tistory.com/240

brew install awscli source '/opt/homebrew/share/zsh/site-functions/_aws' >> ~/.zshrc

awscli IAM 연결

aws configure

AWS Access Key ID [None]: aws cli 액세스 iam key
AWS Secret Access Key [None]: aws cli 액세스 iam secret
Default region name [None]: ap-northeast-2
Default output format [None]: json

awscli 연결 정보 확인

cat ~/.aws/credentials

[default]
aws_access_key_id = aws cli 액세스 iam key
aws_secret_access_key = aws cli 액세스 iam secret

cat ~/.aws/config

[default]
region = ap-northeast-2
output = json