GOSE_KOSE

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드문제 여행 가자 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1976

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n; // n 개의 도시
    static int m; // 들려야 하는 m개 도시
    static int[] parent; // union find
    static List<Integer> nodes = new ArrayList<>(); // 도시 번호 저장
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = parseInt(br.readLine());
        m = parseInt(br.readLine());
        
        parent = new int[n + 1]; // 초기화
        for (int i = 0; i <= n; i++) parent[i] = i; // 루트 노드 설정하기
        
        for (int row = 1; row <= n; row++) {
            // 유니온 파인드를 위해 중복되는 경로를 제거하기 위해 대각선 기준 오른쪽 탐색
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int col = 1; col <= n; col++) {
                int link = parseInt(st.nextToken());
            
                if (col > row) { // 링크가 연결되어 있다면 row의 도시 번호를 기준으로 합치기
                    if (link == 1) union(find(row), find(col));
                }
            }      
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) nodes.add(parseInt(st.nextToken()));
       
        boolean result = isSameRoot(); // 도시가 같은 루트를 공유하는지 판단
        System.out.println(result ? "YES" : "NO");
    }
    
    static boolean isSameRoot() {
        
        if (m == 0) return true; // 만약 들려야 하는 도시가 0이라면 종료
        boolean check = true; // 루트가 같은지 판단
        
        int root = find(nodes.get(0));
        for (Integer node : nodes) {
            if (!(root == find(node))) { // 루트가 다르다면 간선이 존재하지 않음
                check = false;
                break;
            }
        }
        
        return check;
    }
   
    
    static int find(int x) { // find 경로 압축
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
    
    static void union(int v1, int v2) {
        parent[v1] = v2;
    } // v1을 루트로 v2 합치기
}

2, 풀이 중점 사항

각 도시로 연결되는 간선은 양방향 이동 경로 입니다. 이는 곧 주어지는 n개의 줄은 대칭 형태로 주어지고 있습니다.

저는 대각선을 기준으로 오른쪽에 위치한 값으로 parent 와 child를 설정하였습니다.

col > row 인 조건에서 link == 1 이라면, row가 부모가 되어, child를 연결할 수 있도록 구성하였습니다.

if (col > row) { // 링크가 연결되어 있다면 row의 도시 번호를 기준으로 합치기
    if (link == 1) union(find(row), find(col));
}

이 코드의 효과로, 1 -> 2가 연결되어 있다면 root 노드가 1이 되고, 2는 루트가 1인 집합의 원소가 됩니다.

이어지는 값에서 2 -> 3으로 연결된다면, 2는 root가 1이므로 3은 root 1을 그대로 따르게 됩니다.

static boolean isSameRoot() {
    
    if (m == 0) return true; // 만약 들려야 하는 도시가 0이라면 종료
    boolean check = true; // 루트가 같은지 판단
    
    int root = find(nodes.get(0));
    for (Integer node : nodes) {
        if (!(root == find(node))) { // 루트가 다르다면 간선이 존재하지 않음
            check = false;
            break;
        }
    }
    
    return check;
}

해당 소스에서 nodes.get(0)으로 꺼낸 root의 값이 거쳐야 하는 도시들의 root와 다르다면, 이는 다른 도시들을 경유하여 갈 수 없는 경로임을 의미하므로 false를 리턴하였습니다. 만약 거쳐야 하는 도시가 모두 root를 따른다면, 양방향 간선으로 인해, 서로 도시 간 이동이 가능합니다.

이상으로 유니온 파인드 문제 여행 가자 자바 풀이를 마치도록 하겠습니다.!

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 유니온 파인드문제 - 집합의 표현 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1717

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int[] parent;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        
        parent = new int[n + 1];
        for (int i = 0; i <= n; i++) parent[i] = i;
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int cal = parseInt(st.nextToken());
            int a = parseInt(st.nextToken());
            int b = parseInt(st.nextToken());
            
            if (cal == 0) {
                int p1 = find(a); // p1 루트 노드 찾기
                int p2 = find(b); // p2 루트 노드 찾기 
                
                union(p1, p2); // 합치기
            } else {
                boolean same = find(a) == find(b);
                sb.append(same ? "YES" : "NO").append("\n");
            }
        }
        
        System.out.print(sb);
    }
    
    static int find(int child) {

        if (child == parent[child]) return child; // 자신이 루트 노드라면
        return parent[child] = find(parent[child]); // 만약 루트 노드가 아니라면 루트 노드 찾기, 경로압축
    }
    
    static void union(int p1, int p2) {
        parent[p2] = p1; // p2의 부모를 p1으로 바꾸기
    }
}

2. 풀이 중점 사항

해당 문제는 유니온 파인드를 활용하여 집합을 표현할 수 있습니다.

static int find(int child) {

    if (child == parent[child]) return child; // 자신이 루트 노드라면
    return parent[child] = find(parent[child]); // 만약 루트 노드가 아니라면 루트 노드 찾기, 경로압축
}

child의 부모 노드가 자신이라면 이는 곧 루트 노드임을 의미합니다. 따라서, 자기 자신을 그대로 리턴합니다.

하지만, 만약 parent[child]가 자신이 아니라면, 루트 노드가 존재함을 의미합니다.

따라서, 경로 압축을 활용하여 find(parent[child]) 한 값을 찾아서 parent[child]에 대입하고 그 값을 리턴합니다.

예를 들어

child = 5;

parent[child] = 3;

parent[3] = 7;

parent[7] = 7 인 상황이 있습니다.

이를 경로 압축을 통해 parent를 찾으면 다음과 같습니다.

parent[5] = find(parent[5])  = find(parent[3]) = parent[7]; 이 성립되어 모두 경로를 압축할 수 있습니다.

이를 토대로 시간 복잡도를 효율적으로 개선할 수 있습니다.

이상으로 집합의 표현 자바 풀이를 마치도록 하겠습니다. 감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리 문제 - 트리의 지름 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/1167

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = parseInt(br.readLine());
        Graph graph = new Graph(n); // 그래프 생성
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v1 = parseInt(st.nextToken()); // 첫 번째 문자 정점
            while (true) {
                int v2 = parseInt(st.nextToken()); // 연결할 정점 -1이면 종료
                if (v2 != -1) {
                    graph.addEdge(v1, v2, parseInt(st.nextToken())); // 간선 길이
                } else break;                 
            }            
        }
        
        graph.run(1,  0); // 임의의 정점에서 가장 긴 정점 구하기
        graph.run(graph.getNext(), 0); // 다음 정점에서 가장 긴 정점 구하기
        
        System.out.println(graph.getMax());
    }
}

class Graph {
    int n;
    int max; // 정점 최장 거리
    int next; // 다음에 dfs를 계산할 next 노드
    Node[] nodes; // 노드 배열
    boolean[] visited; // 방문 설정
    
    Graph(int n) {
        this.n = n;
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i); // 초기화
    }
    
    class Node {
        int x;
        List<Edge> edges = new ArrayList<>(); // 노드에 연결될 간선 설정
        
        Node (int x) {
            this.x = x;
        }
    }
    
    class Edge { // edge
        int y; // x 노드와 연결되는 간선 y
        int dist; // x 노드와 y 노드의 간선 길이
        
        Edge (int y, int dist) {
            this.y = y;
            this.dist = dist;
        }
    }
    
    void addEdge(int x, int y, int dist) {
        Node n1 = nodes[x];      // 단방향 간선
        n1.edges.add(new Edge(y, dist));
    }

    void run(int x, int dist) {
        visited = new boolean[n + 1]; // visited 초기화
        dfs(x, dist); // dfs 실행
    }

    void dfs(int x, int dist) {
        Node n1 = nodes[x];
        visited[n1.x] = true;

        for (Edge e : n1.edges) { // 간선 탐색
            if (!visited[e.y]) { // 간선에 연결된 노드에 방문하지 않은 경우
                dfs(e.y, dist + e.dist); // 다음 노드, 현재 거리에 간선 길이 더하기
            }
        }

        if (max < dist) { // 길이가 더 크면
            max = dist; // 길이 업데이트
            next = x; // 다음 노드 업데이트 
        }
    }
    
    int getMax() {
        return max;
    }
    int getNext() {return next;}
    
}

2. 풀이 중점 사항

트리의 지름을 구하는 알고리즘은 DFS 혹은 BFS를 두 번 탐색하여 구할 수 있습니다.

트리는 사이클이 없는 그래프이므로, 트리의 지름은 트리 상에서 가장 멀리 떨어진 두 정점의 거리입니다.

이런 특성으로 인해 한 정점에서 가장 먼 정점을 찾고 나서, 다시 그 정점에서 다시 가장 먼 정점을 찾는다면 트리의 지름을 얻을 수 있습니다.!

따라서, 두 번의 dfs를 통해 가장 긴 거리를 유지하는 정점을 찾고 다시 그 정점에서 가장 긴 정점을 찾는다면 문제를 해결할 수 있습니다.

ex)

3  - ------- - - - 1

|     \            d: 10

|      \  

|        \ d: 500

|          4

|  d: 20

2

1의 노드 입장에서 가장 먼 노드는 4번입니다. 하지만 4번 노드에서 가장 긴 정점은 2번 노드입니다.

즉 임의의 노드에서 가장 먼 노드를 찾고 그 노드에서 다시 한번 가장 먼 노드를 찾으면 트리의 지름을 구할 수 있습니다.

이상으로 트리의 지름 자바 풀이를 마치겠습니다. 감사합니다!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 트리문제 - 트리의 부모 찾기 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/11725

1. 풀이 소스

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        Graph graph = new Graph(n); // 그래프 생성
        
        for (int i = 1; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            graph.addEdge(parseInt(st.nextToken()), parseInt(st.nextToken())); // 간선 설정
        }
        graph.getParent();
    }
}

class Graph {
    int n; // n개 노드
    Node[] nodes; // 노드를 담을 배열
    
    Graph(int n) {
        this.n = n;
        nodes = new Node[n + 1];
        for (int i = 1; i <= n; i++) nodes[i] = new Node(i); // 노드 초기화
    }
    
    class Node {
        int x;
        List<Node> adjacent = new ArrayList<>(); // 인접한 노드
        
        Node (int x) {
            this.x = x;
        }
    }
    
    void addEdge(int x, int y) {
        Node n1 = nodes[x];
        Node n2 = nodes[y];
        
        n1.adjacent.add(n2); // 연결된 간선
        n2.adjacent.add(n1); // 양방향 연결
    }
    
    void getParent() {
        int[] parent = new int[n + 1]; // 부모의 노드 번호 저장
        boolean[] visited = new boolean[n + 1]; // 방문
        
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(nodes[1]);
        
        while(!queue.isEmpty()) {
            Node n1 = queue.poll();
            
            visited[n1.x] = true;
            
            for (Node ad : n1.adjacent) {
                if (!visited[ad.x]) { // 아직 방문하지 않았다면 큐의 성질로 부모의 자식 노드 반환
                    queue.add(ad); // 큐에 추가 
                    parent[ad.x] = n1.x; // 자식 노드 번호에 부모 노드 번호 저장
                }
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 2; i <= n; i++) sb.append(parent[i]).append("\n");
        
        System.out.print(sb);
    }
}

2. 풀이 중점 사항

부모 노드의 인접한 노드는 자식 노드입니다. 큐의 성질을 활용하여 루트 노드를 큐에 넣고, 큐에 있는 인접한 노드 (자식 노드)를 큐에 넣습니다. 각 노드를 방문할 때마다 방문 처리하여, 다른 인접한 노드의 호출로 노드가 두 번 이상 큐에 들어가지 않도록 설정합니다. 이러한 방법으로 자식 노드의 부모 노드 번호를 출력할 수 있습니다. 자세한 풀이는 주석화 하였습니다.

이상으로 백준 트리 문제 트리의 부모 찾기 풀이를 마치도록 하겠습니다. 

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 벽장문의 이동 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2666

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main{
    static int n, m;
    static int[] arr;
    static int[][][] dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int left = parseInt(st.nextToken()); // 왼쪽에 있는 포인터
        int right = parseInt(st.nextToken()); // 오른쪽에 있는 포인터
        
        m = parseInt(br.readLine());
        // dp[m][n][n] => m번째 움직어야 하는 방을 움직일 때, left와 right의 움직임 최소 값
        dp = new int[m][n + 1][n + 1]; // m은 이동 해야하는 개수, n + 1 : left 이동, n + 1: right 이동
        arr = new int[m]; // 움직어야 하는 방 저장
        for (int i = 0; i < m; i++) arr[i] = parseInt(br.readLine());
        
        for (int i = 0; i < m; i++) {
            for (int j = 1; j <= n; j++) // (n은 1부터)
                Arrays.fill(dp[i][j], -1); // 초기 값은 -1로 초기화
        }
        
        System.out.println(dfs(0, left, right));
    }
    
    static int dfs(int idx, int left, int right) {
        if (idx == m) return 0; // 움직여야 하는 모든 움직임을 마친 경우
        
        if (dp[idx][left][right] == -1) { // 아직 dp가 업데이트 되지 않았음
            dp[idx][left][right] = Math.min(
                Math.abs(left - arr[idx]) + dfs(idx + 1, arr[idx], right), // left가 움직인 값 + 재귀로 다음 항, left가 움직여진 위치, right
                Math.abs(right - arr[idx]) + dfs(idx + 1, left, arr[idx])
            );
        }
        return dp[idx][left][right];
    }
}

2. 풀이 중점 사항

점화식 세우기

dp[m][left][right] 는 m번째 자리에 있는 방의 번호를 옮기는데 left방이 총 이동한 거리와 right 방이 총 이동한 거리를 더한 값의 최소를 DP로 정의하였습니다.

즉, 만약 m = 2, left = 3, right = 4라면, 현재 m의 방에서 left가 3에 위치해 있고 right가 4에 위치해 있는 상태까지 총거리의 최소를 의미하게 됩니다.

dp[idx][left][right] = Math.min(
	Math.abs(left - arr[idx]) + dfs(idx + 1, arr[idx], right),
    Math.abs(right - arr[idx]) + dfs(idx + 1, left, arr[idx])
)

이 점화식은 left - arr[idx] 즉 idx 번째에 옮겨야 하는 방의 위치에서 left를 뺀 후 절댓값을 취한 것이므로 이동 거리를 의미합니다.

그리고 arr[idx]는 현재 left를 움직였으므로 그 위치의 값을 넣어준 것입니다.

시나리오 

방 6개

m = 2

arr = {1, 4} 

left = 2, right  = 5 가 주어져 있다고 생각하겠습니다.

dp[0][2][5] = Math.min(

    Math.abs(left - arr[0]) + dfs(1, 1, 5)

    = Math.abs(2 - 1) + dfs(1, 1, 5)  = 1 +  dfs(1, 1, 5)

    = 1 + 

              dp[1][1][5] = Math.min(

                  Math.abs(1 - arr[1]) + dfs(2, arr[1], 5) 

                  = Math.abs(1 - 4) + dfs(2, arr[1], 5) 

                  = 3 + dfs(2, 4, 5)

                  = 3 

                 , 

                 Math.abs(5 - arr[5]) + dfs(2, 1, arr[5])

                 = 1 + dfs(2, 1, 4)              

                 = 1 

                )

            =  1

            (dp[1][1][5] = 1 저장)

  = 1 + 1 = 2  

   , Math.abs(right - arr[0]) + dfs (1, 2, 1)

     = Math.abs(5 - 1) + dfs(1, 2, 1)

     =   4 + dfs(1, 2,  1) ~ 

이와 같은 재귀 형태로 반복이 진행됩니다.

따라서, 최솟값을 DFS 형태와 dp를 활용하여 구할 수 있습니다.

이상으로 벽장문의 이동 자바 풀이를 마치도록 하겠습니다. 감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다. 

이번 포스팅은 백준 DP 계단 수 자바 풀이를 진행하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/1562

1. 풀이 소스

import java.io.*;

public class Main {
    static final int MOD = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        long[][][] dp = new long[n + 1][10][1 << 10]; // i 자리에서, k라는 숫자가 오는데, 0 ~ 9까지의 방문 여부를 담은 3차원 배열 ex) dp[10][6][10] 10번째 자리에서, 6이 올 수 있는 경우에 방문 상태는 0000000110
        for (int i = 1; i <= 9; i++) 
            dp[1][i][1 << i] = 1; // 1자리에서 k라는 수가 오는 경우 (0은 첫번째 자리에 올 수 없음)
        
        for (int t = 2; t <= n; t++) {
            for (int k = 0; k <= 9; k++) { // 2자리부터는 0 가능
                for (int visited = 0; visited < (1 << 10); visited++) { // 비트마스크에 의해 0 ~ 1024까지
                    
                    int nextVisited = visited | (1 << k); // 비트마스크로 방문 처리 (이진수 | 은 or 연산)
                    
                    if (k == 0) dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD; // k == 0 인 경우 올라가는 연산만 존재
                    else if (k == 9) dp[t][k][nextVisited] += dp[t - 1][k - 1][visited] % MOD; // k == 9인경우 내려가는 연산만 존재
                    else dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD + dp[t - 1][k - 1][visited] % MOD; // 둘 다 가능
                
                    dp[t][k][nextVisited] %= MOD; // 모든 경우를 구한 후 + 연산을 했으므로 한번 더 MOD 연산 진행
                }
            }
        }
        
        long sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum += dp[n][i][(1 << 10) - 1] % MOD; // 비트마스크의 마지막인덱스 1 111 111 111 (모든 숫자 방문)
            sum %= MOD;
        }
        
        System.out.println(sum);
    }
}

2. 풀이 중점 사항

계단 수

계단 수의 DP 점화식은 다음과 같습니다.

dp[n][k] = dp[n - 1][k - 1] + dp[n - 1][k + 1] // n은 자리수, k는 n의 자리에 있는 숫자

예를 들어 xx7이 있다고 가정하겠습니다.

xx7은 두번째 자리 수(3 - 1)가 6(k - 1) 이거나 8(k + 1) 인 값이어야 합니다.   

x67은 첫번째 자리수가 (2 - 1)가 5(k - 1) 이거나 7(k + 1)인 값이어야 합니다.

즉, 현재 n 번째 자리에서 k라는 숫자가 오기 위해서는 n - 1 자리에서 k - 1 숫자가 있는 dp와 n - 1 자리에서 k + 1 숫자가 있는 dp를 더해야 합니다.

하지만, 0 과 9의 경우는 0은 올라가는 계단 수만, 9는 내려가는 계단 수만 존재하므로  하단의 점화식을 세울 수 있습니다.

if (k == 0) dp[t][k] += dp[t - 1][k + 1]; // k == 0 인 경우 올라가는 연산만 존재
else if (k == 9) dp[t][k] += dp[t - 1][k - 1]; // k == 9인경우 내려가는 연산만 존재
else dp[t][k] += dp[t - 1][k + 1] + dp[t - 1][k - 1]; // 둘 다 가능

비트 마스킹 

다음은 0 ~ 9 까지 모든 숫자가 등장하는 계단 수를 구해야 합니다.

이를 위해 비트마스킹을 활용할 수 있습니다.

비트마스킹은 이전 풀이에서 활용한 방법으로 1 ~ n까지 숫자가 있을 때 방문 처리를 비트형태로 표현하는 방법입니다.

1 << 3 을 쉬프트 하게되면  1000 이 나오는데, 0은 방문 X, 1은 방문 O을 의미하도록 할 수 있습니다.

가령 111은 1, 2, 3번을 모두 방문 했다는 의미로 해석할 수 있습니다.

long[][][] dp = new long[n + 1][10][1 << 10]; // i 자리에서, k라는 숫자가 오는데, 0 ~ 9까지의 방문 여부를 담은 3차원 배열 ex) dp[10][6][10] 10번째 자리에서, 6이 올 수 있는 경우에 방문 상태는 0000000110

따라서, 기존의 점화식에 비트마스킹으로 방문 처리를 하는 기능을 추가하였습니다.

for (int visited = 0; visited < (1 << 10); visited++) { // 비트마스크에 의해 0 ~ 1024까지
                    
    int nextVisited = visited | (1 << k); // 비트마스크로 방문 처리 (이진수 | 은 or 연산)

    if (k == 0) dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD; // k == 0 인 경우 올라가는 연산만 존재
    else if (k == 9) dp[t][k][nextVisited] += dp[t - 1][k - 1][visited] % MOD; // k == 9인경우 내려가는 연산만 존재
    else dp[t][k][nextVisited] += dp[t - 1][k + 1][visited] % MOD + dp[t - 1][k - 1][visited] % MOD; // 둘 다 가능

    dp[t][k][nextVisited] %= MOD; // 모든 경우를 구한 후 + 연산을 했으므로 한번 더 MOD 연산 진행
}

이후, nextVisited  = visited | (1 << k)의 비트 or 연산으로 방문 처리가 될 수 있도록 하였습니다.

1000  | 0100   => 1100 이므로 (1, 2 번 방문)

만약 visited = 111 111 111 이었고, k == 9여서

nextVisited = 111 111 111 | 1 000 000 000 => 1 111 111 111이 된다면,
이는 곧  모든 위치를 방문한 경우를 의미하게 됩니다.

이상으로 계단 수 자바 풀이를 마치도록 하겠습니다. !

감사합니다.!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP 문제 공통 부분 문자열 자바 풀이를 진행하고자 합니다.

문제 출처 https://www.acmicpc.net/problem/5582

1. 풀이 소스 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String str1 = br.readLine(); // 입력 받을 문자열
        String str2 = br.readLine(); // 입력 받을 문자열
        int[][] dp = new int[str1.length() + 1][str2.length() + 1]; // 길이 + 1 길이 + 1 로 선언
        
        int max = 0;
        
        // row, col 을 1부터 시작하는 이유는 인덱스 에러 방지 
        for (int row = 1; row <= str1.length(); row++) {
            for (int col = 1; col <= str2.length(); col++) {
                if (str1.charAt(row - 1) == str2.charAt(col - 1)) { // 문자열은 0부터 시작하므로 실제 row = 1에 해당하는 문자는 0 
                    dp[row][col] = dp[row - 1][col - 1] + 1; // 만약 두 문자가 같다면 row - 1, col - 1 인덱스의 dp + 1 (연속된 문자열)
                    max = Math.max(max, dp[row][col]);
                }
            }
        }
        System.out.println(max);
    }
}

2. 풀이 중점 사항

해당 문제는 연속된 부분 문자열의 가장 큰 크기를 구해야 하는 것이 목표였습니다.

str1: ACABACD 

str2: ABABC

라는 문자열이 주어졌을 때, 두 문자열의 가장 긴 부분 문자열을 구하는 것은 다음의 표와 같습니다.

행의 첫번째 열은 str1의 문자 인덱스 번호이고, 열의 첫 번째 행은 str2의 인덱스 번호입니다.

(2, 0), (3, 1), (4, 2)의 문자열은 

str1의 ABA,  str2의 ABA입니다. 

이는 곧, 만약 B = B라면, 앞에 row - 1, col - 1의 값에 + 1을 하는 것과 동일하게 됩니다.

왜냐하면, B = B라면 앞에 같은 연속된 문자열이 있을 수도 있는데, 그 값을 DP가 저장하고 있기 때문입니다.

따라서, DP는 현재 주어진 문자열 A의 인덱스와 비교하고자 하는 문자열 B의 인덱스에 있는 문자가 같다면 
이전 연속된 값이 있는지 DP에서 확인하여 +1을 하는 로직을 구할 수 있습니다.

dp[row][col] = dp[row - 1][col - 1] + 1; // 만약 두 문자가 같다면 row - 1, col - 1 인덱스의 dp + 1 (연속된 문자열)

따라서, 이와 같은 로직을 구할 수 있게 되는 것 입니다.

이상으로 백준 DP 공통 부분 문자열 풀이를 마치도록 하겠습니다.

감사합니다!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 극장 좌석 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/2302

1. 풀이 소스

import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    static final int LEN = 41;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        int m = parseInt(br.readLine());

        int[] vip = new int[m]; // 고정석 저장
        int[] dp = new int[LEN]; // dp 초기화 41개 좌석
        
        for (int i = 0; i < m; i++) vip[i] = parseInt(br.readLine()); // vip 입력 받기
        
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        
        for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2]; // n번까지 설정
        
        int answer = 1; // n == 1일 때 answer는 1
        
        int preIdx = 0; // 곱셉을 위한 이전 위치
        for (int idx : vip) {
            answer *= dp[idx - preIdx - 1]; // 인덱스 - 이전 인덱스 - 1을 함으로써 연속된 좌석을 길이 구하기
            preIdx = idx; // 인덱스를 업데이트하여 dp 길이
        }
        
        answer *= dp[n - preIdx]; // 마지막 고정석으로부터 연속된 좌석 dp
        System.out.println(answer);
    }
}

2. 풀이 중점 사항

점화식 도출

앉을 수 있는 좌석은 다음의 규칙이 있습니다.

1번 좌석 : 1 (1)

2번 좌석까지: 1, 2   /   2, 1 (2)

3번 좌석까지: 1, 2, 3   /   1, 3, 2   /   2, 1, 3  (3)

4번 좌석까지: 1, 2, 3, 4  / 1, 3, 2, 4  / 2, 1, 3, 4 /  1, 2, 4, 3 / 2, 1, 4, 3 (5개)

이러한 규칙성은 피보나치수열과 같은 점화식을 도출할 수 있습니다.

dp [n] = dp[n - 1] + dp[n - 2]

이를 바탕으로 n개까지의 dp를 구해야 했습니다.

고정석 설정하기

고정석을 설정하고나면, 고정석 이전 혹은 사이, 이후에 있는 좌석들은 각각 새로운 길이의 좌석이라고 볼 수 있습니다.

즉, 인접한 3개, 인접한 1개, 인접한 3개의 좌석의 dp를 구한 후 세 개는 모두 동시에 발생하므로 곱하여 값을 구할 수 있습니다.

이러한 원리를 구현한 코드가  아래의 코드입니다.

int answer = 1; // n == 1일 때 answer는 1

int preIdx = 0; // 곱셉을 위한 이전 위치
for (int idx : vip) {
    answer *= dp[idx - preIdx - 1]; // 인덱스 - 이전 인덱스 - 1을 함으로써 연속된 좌석을 길이 구하기
    preIdx = idx; // 인덱스를 업데이트하여 dp 길이
}

answer *= dp[n - preIdx]; // 마지막 고정석으로부터 연속된 좌석 dp

이상으로 극장 좌석 자바 풀이를 마치도록 하겠습니다.

감사합니다.!!!

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 외판원 순회 자바 풀이를 진행하고자 합니다.

문제 출처: https://www.acmicpc.net/problem/2098

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    static int n;
    static int answer;
    static int[][] fromTo;
    static int [][] dp;
    static int INF = 987654321;

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

        n = parseInt(br.readLine());
        fromTo = new int[n][n];
        dp = new int[1 << n][n]; // 디피 설정

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

        answer = tsp(1, 0); // 방문, 위치
        System.out.println(answer);
    }

    static int tsp(int visited, int loc) {
        if (visited == (1 << n) - 1) {
            if (fromTo[loc][0] > 0) return fromTo[loc][0]; // 값이 유효함
            return INF; // 간선이 없어서 최대값으로 설정
        }

        if (dp[visited][loc] > 0) return dp[visited][loc]; // 현재 방문한 상태가 최신 상태로 업데이트 된 경우

        dp[visited][loc] = INF; // 아직 방문하지 않았음을 의미함

        for (int dest = 0; dest < n; dest++) {
            if (isValid(visited, loc, dest))
                dp[visited][loc] = Math.min(dp[visited][loc],
                        tsp(visited | (1 << dest), dest) + fromTo[loc][dest]);
        }

        return dp[visited][loc];
    }

	// 비트마스크의 & 연산으로 아직 방문하지 않은 경우 == 같은 위치에 1이 존재하지 않는 경우 == 0 && 방문 하려는 곳의 간선이 존재
    static boolean isValid(int visited, int loc, int dest) {
        return (visited & (1 << dest)) == 0 && fromTo[loc][dest] > 0;
    }
}

2. TSP (Traveling Salesman Problem)

TSP는 외판원 문제로 외판원이 각 독시를 정확히 한 번씩 방문하고, 처음 출발한 도시로 돌아오는 가장 짧은 경로는 무엇인지 구하는 문제입니다. 이 문제는 NP-완전 문재로 모든 가능한 경우를 탐색하여 최적 해를 구할 수 있습니다. 

3. DP와 비트마스킹

DP와 비트마스킹으로 TSP 문제를 해결할 수 있습니다. DP를 사용할 경우 시간 복잡도는 O(N^2 * 2^N)으로 해결할 수 있습니다.

• N^2: 모든 도시 간의 거리를 계산하는데 필요한 시간을 나타냅니다. 각 도시에서 다른 모든 도시로 이동하는 비용을 확인하는 단계입니다.
• 2^N: 각 도시의 방문 상태를 고려해야 합니다. 비트마스킹을 사용하므로 2^N으로 (ex 010100) 형태로 각 방문 상태를 설정할 수 있습니다. 

이러한 방법을 토대로 브루트 포스 방법으로 탐색할 경우 가지는 N! 보다 빠른 속도로 탐색을 수행할 수 있습니다.

N개의 노드가 있을 때, 방문 상태를 1 << N의 비트로 관리하면 방문 상태를 유지할 수 있습니다.

0010의 경우 2번 인덱스 노드는 방문한 상태를 의미하고, 0011은 2, 3번 노드를 방문한 상태를 의미합니다.

visited | (1 << n); // n을 방문 처리
visited & (1 << n); // n이 방문을 했는지 안했다면 0

자바에서 비트의 OR은 '|' 로 계산할 수 있습니다.

0010 | 0100 = 0110 을 구할 수 있습니다.

AND 연산은 '&'로 구할 수 있습니다. 같은 위치에 1이 있어야 1이 인정됩니다.

0010 & 0100 = 0000 

이를 토대로 visited | (1 << n)을 해석하면,

현재 방문한 상태의 visited 값과 or 연산을 진행하는데, 대상은 1 << n입니다.

1 << n은 1에서 n개까지를 오른쪽으로 시프트 시키는 것을 의미합니다. 즉,

1 << 3 = 1000(2)를 의미하는 것입니다. 

만약 visited = 10000(2) 였다면, visited | (1 << n)은 11000(2)의 값을 가질 수 있습니다.

AND연산은 방문을 이미 했는지를 판단해야 하므로 같은 위치에 1이 있는지를 판단하게 됩니다. 만약 0이라면
같은 자리에 1이 없다는 것을 의미하므로 방문하지 않았음을 의미합니다. 

한 가지 의문점은 왜 굳이 비트마스킹으로 visited를 설정하는가입니다

이는 비트열로 visited를 수정하고 바꾸는 과정을 수행하므로 따로 boolean 배열을 설정하지 않더라도 문제를 해결할 수 있습니다. 

또한 비트는 다른 연산보다 더 빠르게 연산이 가능하므로 효율적으로 계산을 수행할 수 있습니다.

4. 풀이 중점 사항

이를 토대로 코드를 살펴보면 다음과 같습니다.

TSP 문제를 해결하기 위해 DP와 비트마스킹을 활용합니다. 0, 0의 정점에서 시작하여 각 정점까지 이동이 가능한지 파악하고 방문하지 않았다면 방문합니다. 방문한 노드에서 현재 모두 방문해서 마지막 다시 시작점으로 이동해야 하는지, 혹은 이전에 이미 값을 업데이트했는지 등을 파악합니다. 이러한 재귀를 마치게 되면, 최종적으로 가장 짧은 순회 길이를 구할 수 있습니다.

          1열       2열      3열

1행     0           1          2

2행     1           0          1

3행     0           0          0

이 상태에서 예를 들어 (0, 0)으로 시작을 하면, (0,1)을 거치게 됩니다.

(1, 3) 열을 거치게 되고 (3, 1) 열을 거쳐서 값을 리턴하는 방식으로 재귀형태로 진행이 됩니다.

static int tsp(int visited, int loc) {
        if (visited == (1 << n) - 1) {
            if (fromTo[loc][0] > 0) return fromTo[loc][0]; // 값이 유효함
            return INF; // 간선이 없어서 최대값으로 설정
        }

        if (dp[visited][loc] > 0) return dp[visited][loc]; // 현재 방문한 상태가 최신 상태로 업데이트 된 경우

        dp[visited][loc] = INF; // 아직 방문하지 않았음을 의미함

        for (int dest = 0; dest < n; dest++) {
            if (isValid(visited, loc, dest))
                dp[visited][loc] = Math.min(dp[visited][loc],
                        tsp(visited | (1 << dest), dest) + fromTo[loc][dest]);
        }

        return dp[visited][loc];
    }

// 비트마스크의 & 연산으로 아직 방문하지 않은 경우 == 같은 위치에 1이 존재하지 않는 경우 == 0 && 방문 하려는 곳의 간선이 존재
static boolean isValid(int visited, int loc, int dest) {
    return (visited & (1 << dest)) == 0 && fromTo[loc][dest] > 0;
}

저는 55%에서 에러가 발생하여 참고한 블로그를 토대로 코드를 작성했었습니다.

중요한 포인트는 저는 시작할 때, 모두 INF값으로 설정하여, 간선이 없는 경우에도 INF 처리가 되어 에러가 발생했습니다.

참고했던 블로그 소스들에서는 시작을 모두 0으로 초기화하고, 간선이 존재하지 않으면 INF를 리턴합니다.

이렇게 되면, 자연스럽게 Math.min()의 우선순위에서 밀려서 선택이 되지 않고, 방문하지 않았고 간선이 존재하는 경우
INF로 초기화하고 loc위치에서 이동하려는 dest로 다시 tsp 재귀를 진행하면 간선이 존재하는 경우는 INF보다 작으므로 선택될 수 있는 환경이 되었습니다.

answer = tsp(1, 0); // 방문, 위치

처음 문제를 해결할 때, 왜 0번 인덱스로 순회를 시작하면 되는가에 대한 의문이 있었습니다.

순회라는 개념은 사이클이 된다는 것을 의미합니다.

만약, 최단 거리를 유지할 수 있는 순회 경로가

0 -> 1 -> 2 -> 3 -> 0이라면,

1-> 2 -> 3 -> 0 -> 1과 동일합니다.

즉 어디서 시작하던 0 -> 1을 가야 하고, 1 -> 2를 가야하고 , 2 -> 3, 3 -> 0을 가는 것은 동일합니다.

만약 최단 거리를 유지할 수 있는 순회 경로가

1 -> 2 -> 0 -> 3 -> 1 이더라도

0 -> 3 -> 1 -> 2 -> 0 은 순서만 다를 뿐 실제 사이클은 동일합니다.

따라서, 이 원리를 토대로 0번 인덱스에서 시작하면 최적의 값을 구할 수 있습니다.

외판원 문제와 같은 비트마스크 연산은 항상 헷갈리는데 나올 때마다 정리해 놓으면 도움이 되는 것 같습니다. 이상으로 

외판원 순회 자바 풀이를 마치도록 하겠습니다.

참고 블로그: https://velog.io/@zeesouth/%EB%B0%B1%EC%A4%80-2098.-%EC%99%B8%ED%8C%90%EC%9B%90-%EC%88%9C%ED%9A%8C-Java

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 줄세우기 자바 풀이를 작성하도록 하겠습니다.

문제 출처: https://www.acmicpc.net/problem/2631

1. 풀이 소스

import java.io.*;
import java.util.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(br.readLine());
        
        int[] map = new int[n];
        for (int row = 0; row < n; row++) map[row] = parseInt(br.readLine());
        int lis = getLISByBinarySearch(map); // 이진 탐색으로 LIS 길이 찾기
        
        System.out.println(n - lis); // 총 길이에서 LIS 개수를 빼면 이동가능한 길이가 나옴
    }
    
    static int getLISByBinarySearch(int[] arr) { // 이진 탐색
        List<Integer> dp = new ArrayList<>(); // dp 저장
        
        for (int num : arr) {
            if (dp.isEmpty() || num > dp.get(dp.size() - 1)) dp.add(num); // 처음이거나 마지막 숫자보다 크면 업데이트
            else {
                int left = 0, right = dp.size() - 1;
                while (left < right) { // 이진 탐색
                    int mid = left + (right - left) / 2;
                    if (dp.get(mid) < num) left = mid + 1;
                    else right = mid;
                }
                dp.set(right, num); // 위치에 값 업데이트 
            }
        }
        
        return dp.size();
    }
}

2. 풀이 중점 사항

이 문제는 정렬되지 않은 숫자가 있을 때, 각 위치를 이동하여 최소 숫자로 정렬하는 문제입니다.

순열 1, 5, 2, 9 가 주어져 있다고 예를 들겠습니다.

이 경우 2를 5 앞에 놓게 되면 1 2 5 9로 정렬을 할 수 있습니다.

1, 5, 2, 3, 7, 6이 주어졌다고 가정하겠습니다.

3의 뒤에 5을 이동시키고, 7을 6 뒤에 이동시키면 2번 안에 이동을 마칠 수 있습니다.

이는 최장 증가 부분 수열을 찾은 후, 최장 증가 부분 수열 내부로 각각 원소들을 이동시키면 되는 것입니다.

1      2        3         6          이 최장 증가 부분 수열이므로 

                      5          7     을 위치시키면 문제를 해결할 수 있습니다.

즉 정답은 총 개수 - 최장증가 부분 수열 개수를 빼면 해결 할 수 있습니다.

3. LIS 이진탐색으로 해결하기

이진 탐색은 O(logN)으로 LIS를 구할 수 있습니다. 이러한 기능이 가능한 이유는 만약 주어진 숫자가 마지막 인덱스보다 크다면 바로 추가하고, 만약 아니라면 최대로 큰 값을 찾아서 계속 업데이트하되, 그 찾는 과정을 이진 탐색으로 수행하기 때문입니다.

이 과정에서 중요한 점이, 이진 탐색으로 수행할 때, 그 값을 add 하는 것이 아니라 set으로 업데이트하는 것입니다.

즉 최장 증가 부분 수열이 5개라면 6개로 만드는 것이 아니라 중간에 값만 바꾸는 것이기 때문에 최장 증가 부분수열의 크기는 변하지 않고, 탐색한 위치의 값만 수정되게 되는 것입니다. 

static int getLISByBinarySearch(int[] arr) { // 이진 탐색
    List<Integer> dp = new ArrayList<>(); // dp 저장

    for (int num : arr) {
        if (dp.isEmpty() || num > dp.get(dp.size() - 1)) dp.add(num); // 처음이거나 마지막 숫자보다 크면 업데이트
        else {
            int left = 0, right = dp.size() - 1;
            while (left < right) { // 이진 탐색
                int mid = left + (right - left) / 2;
                if (dp.get(mid) < num) left = mid + 1;
                else right = mid;
            }
            dp.set(right, num); // 위치에 값 업데이트
        }
    }

    return dp.size();
}

먼저 DP를 리스트로 설정합니다. 

• 2, 5, 3, 7 숫자가 주어졌다면 하나씩 배열에 담긴 숫자를 탐색합니다.
• 2는 dp가 비어있으므로 dp에 추가합니다.
• 5는 dp의 마지막 값인 2보다 크므로 dp에 추가합니다.
• 3은 5의 마지막 값보다 작으므로 이진 탐색을 수행합니다.
• left = 0, right = 1이고 mid = 0 + 1 / 2 = 0 이므로, left = mid + 1입니다.
• left < right의 조건을 위배하므로 right를 업데이트하는데 right가 1이므로 5의 값을 대체합니다.
• 7은 dp의 마지막 값인 3보다 크므로 7을 추가로 넣습니다.
• 즉, 이진 탐색을 수행하며, 최장 부분 수열을 만족하며 값을 바꿔 끼는 것을 확인할 수 있습니다.

이를 통해 최장 증가 부분 수열의 크기를 구할 수 있습니다.

4. 최장 증가 부분 수열 전체를 이진 탐색으로 구하기

최장 증가 부분 수열을 위의 코드로 구하고 출력하게 된다면, 개수는 동일하지만 올바른 값이 출력되지 않습니다.

왜냐하면 이진 탐색으로 중간에 값을 set 하기 때문에 마지막 값이 변경되지 않는다면 중간의 값을 바꾸는 것이기 때문입니다.

따라서, 온전한 최장 증가 부분 수열을 구하려면 하단의 코드를 작성해야 합니다.

static List<Integer> lisOfBinarySearchList(int[] nums) {
    List<Integer> dp = new ArrayList<>();

    int[] idxs = new int[nums.length]; // 인덱스 저장할 배열
    int[] preIdxs = new int[nums.length]; // 이전 인덱스를 저장할 tmp 배열

    for (int i = 0; i < nums.length; i++) {
        if (dp.isEmpty() || nums[i] > dp.get(dp.size() - 1)) { // 리스트가 비어있거나 현재 리스트의 마지막 값보다 더 큰 경우
            if (!dp.isEmpty()) preIdxs[i] = idxs[dp.size() - 1]; // dp의 마지막 값을 임시 배열에 저장
            dp.add(nums[i]); // 값 추가하기
            idxs[dp.size() - 1] = i; // 인덱스를 저장할 색인 배열에 인덱스 업데이트
        } else { // 이진 검색 시작
            int left = 0, right = dp.size() - 1; // 초기화 양 끝
            while (left < right) {
                int mid = left + (right - left) / 2; // 중앙을 설정할 mid
                if (dp.get(mid) < nums[i]) { // 중간에 위치한 값보다 큰 경우 오른쪽 이진 검색
                    left = mid + 1; // left를 증가시켜서 위치를 옮김
                } else {
                    right = mid; // right를 미드로 설정하여 왼쪽 이진 탐색
                }
            }
            dp.set(right, nums[i]); // 중앙에 값을 대체함
            idxs[right] = i; // 대체한 인덱스 설정
            if (right > 0) preIdxs[i] = idxs[right - 1];
        }
    }

    List<Integer> lis = new ArrayList<>();
    int idx = idxs[dp.size() - 1];
    while (lis.size() < dp.size()) {
        lis.add(nums[idx]);
        idx = preIdxs[idx];
    }
    Collections.reverse(lis);
    return lis;
}

아래의 예시와 함께 설명하면 다음과 같습니다.

수열 2, 5, 3, 7이 주어져 있습니다.

arr은 배열 2, 5, 3, 7

dp는 이진 탐색으로 업데이트한 최장 증가수열을 저장할 dp

preIdxs는 Idx의 이전 인덱스 저장

Idxs는 최장 증가 부분 수열의 실제 값을 저장하기 위한 인덱스 

먼저 인덱스 0을 순회하면, dp가 비어있으므로 2를 저장합니다.

preIdxs[0] = idxs[0]      (0)

idxs[0] = 0

인덱스 1인 경우 arr[1] = 5가 2보다 크므로 5를 저장합니다.

preIdxs[1] = 0

idxs[1] = 1     

이것이 의미하는 바는, 가장 큰 최장 증가 부분 수열의 길이는 2입니다.

idx[dp.size() - 1]이 의미하는 바는 이 가장 긴 수열의 실제 값 (arr의 위치)를 저장한 인덱스입니다.

즉 arr[1]을 찾을 수 있습니다.

preIdx의 인덱스 1에 저장된 0은 다음 최장 증가 부분 수열에서 큰 값의 인덱스를 가리키고 있습니다.

인덱스가 2로 이동한다면, 

dp의 값은 업데이트가 되는데 5보다 3이 작지만 이진 탐색으로 right가 마지막 인덱스를 가리켜서 업데이트 됩니다.

이렇게 값이 더 커서 업데이트가 되는 경우가 아니라 이진 탐색으로 바뀌게 되는 경우는 idx를 먼저 업데이트합니다.

(개수가 증가하는 것이 아니라 내부의 값을 변경하므로)

따라서 idx가 가리키는 인덱스는 2로 수정됩니다.  preIdxs[2] = 0을 가리킵니다.

마지막 인덱스 3에 도달하면 7을 DP에 넣습니다.

preIdxs[3] = 2 (dp 사이즈 - 1)

idxs[2] = 3 (인덱스는 실제 arr의 위치를 가리킴)

총 나온 결과로 시뮬레이션을 확인하면 다음과 같습니다.

List<Integer> lis = new ArrayList<>();
    int idx = idxs[dp.size() - 1];
    while (lis.size() < dp.size()) {
        lis.add(nums[idx]);
        idx = preIdxs[idx];
}

• 최종 최장 증가 부분 수열을 찾기 위한 list를 선언합니다.
• dp.size() - 1의 값인 2를 인덱스로 하여 idxs 배열에서 찾습니다
• 값 3을 가지고 arr[3]의 값을 list에 추가합니다.
• 값 3으로 preIdxs[3] -> 다음 idx에서 찾을 인덱스 2를 가져와 idx로 업데이트 합니다.
• 인덱스 2로 arr[2]인 3을 찾습니다.
• 인덱스 2 preIdxs[2] = 0 을 다음 인덱스로 하여 값을 찾습니다.
• arr[0] = 2 

LIS 를 이진탐색으로 구현할 때, 임시 배열이 여러 개 생성되므로 많이 헷갈렸습니다.

실제 PPT로 그려가며 그 상황을 시뮬레이션하니, 이해할 수 있었습니다.

이상으로 줄세우기 자바 풀이를 마치도록 하겠습니다. 감사합니다.