데일리썽

문제 제목 : DFS와 BFS

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.*;

public class Main {
    public static Integer n, m, v;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[1001];

    public static void addEdge(int n, int m) {
        adjList.get(n).add(m);
    }

    public static void dfs(int node) {
        if (visited[node]) return;

        visited[node] = true;
        System.out.print(node + " ");

        for (int i = 0; i < adjList.get(node).size(); i++) {
            dfs(adjList.get(node).get(i));
        }
    }

    public static void bfs(int node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(node);
        visited[node] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");
            for (int i = 0; i < adjList.get(now).size(); i++) {
                int adjNode = adjList.get(now).get(i);
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();

        for (int i = 0; i < n + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            addEdge(x, y);
            addEdge(y, x);
        }

        for (int i = 1; i < n + 1; i++) {
            Collections.sort(adjList.get(i));
        }

        dfs(v);
        System.out.println();
        visited = new boolean[1001];
        bfs(v);
    }
}

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

2. DFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main3 {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();
    public static Boolean visited[] = new Boolean[node];

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void dfs (Integer node) {
        if (visited[node]) return;

        visited[node] = true;
        System.out.println(node + " ");

        for (int i = 0; i < adj.get(node).size(); i++) {
            int adjNode = adj.get(node).get(i);
            dfs(adjNode);
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

3. 시간 복잡도

노드수 : V

간선수 : E

시간 복잡도 : O(V + E)

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

2. BFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void bfs (Integer newNode) {
        Boolean visited[] = new Boolean[node];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[newNode] = true;
        queue.add(newNode);

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.println(now + " ");
            for (int i = 0; i < adj.get(now).size(); i++) {
                int adjNode = adj.get(now).get(i);
                if (!visited[adjNode]) {
                    visited[adjNode] = true;
                    queue.add(adjNode);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

3. 시간 복잡도

노드수 : V

간선수 : E

시간 복잡도 : O(V + E)

1. 그래프(Graph) 란?

그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용

2. 그래프(Graph) 관련 용어

• 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함
• 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch라고도 함)
• 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드)
• 참고 용어
  • 정점의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
  • 진입 차수(In-Degree) : 방향 그래프에서 외부에서 오는 간선의 수
  • 진출 차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수
  • 경로 길이(Path Length) : 경로를 구성하기 위해 사용된 간선의 수
  • 단순 경로(Simple Path) : 처음 정점과 끝 정점을 제외하고 중복된 정점이 없느 경로
  • 사이클(Cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

3. 그래프(Graph) 종류

무방향 그래프

방향이 없는 그래프

간선을 통해 노드는 양방향으로 갈 수 있음

보통 노드 A, B가 연결되어 있을 경우 (A, B) 또는 (B, A)로 표기

방향 그래프

간선에 방향이 있는 그래프

보통 노드 A, B가 A -> B로 가는 간선으로 연결되어 있을 경우 <A, B>롤 표기

가중치 그래프 또는 네트워크

간선에 비용 또는 가중치가 할당된 그래프

연결 그래프

무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재하는 경우

비연결 그래프

무방향 그래프에서 특정 노드에 대해 경로가 존재하지 않는 경우

사이클

단순 경로의 시작 노드와 종료 노드가 동일한 경우

비순환 그래프

사이클이 없는 그래프

완전 그래프

그래프와 모든 노드가 서로 연결되어 있는 그래프

4. 그래프와 트리의 차이

트리는 그래프 속에 속한 특별한 종류하고 볼 수 있음

문제 제목 : 가장 높은 탑 쌓기

난이도 : 상

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 50분 (못하면 2배 100분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static class Brick {
        public Integer index;
        public Integer area;
        public Integer height;
        public Integer weight;

        public Brick(Integer index, Integer area, Integer height, Integer weight) {
            this.index = index;
            this.area = area;
            this.height = height;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        ArrayList<Brick> brickList = new ArrayList<Brick>();

        brickList.add(new Brick(0, 0, 0, 0));
        for (int i = 1; i < n + 1; i++) {
            brickList.add(new Brick(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(brickList, (s1, s2) -> s1.weight - s2.weight);

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

        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (brickList.get(i).area > brickList.get(j).area) {
                    dp[i] = Math.max(dp[i], dp[j] + brickList.get(i).height);
                }
            }

        }

        Integer maxHeight = Arrays.stream(dp).max().getAsInt();

        int index = n;
        ArrayList<Integer> resultList = new ArrayList<>();
        while (index != 0) {
            if (maxHeight == dp[index]) {
                resultList.add(brickList.get(index).index);
                maxHeight -= brickList.get(index).height;
            }
            index -= 1;
        }

        System.out.println(resultList.size());
        for (int i = resultList.size() - 1; i >= 0; i--) {
            System.out.println(resultList.get(i));
        }
    }
}

문제 제목 : 기타리스트

난이도 : 중

문제 유형 : 동적 프로그래밍(DP

추천 풀이 시간 : 40분 (못하면 2배 80분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        Integer s = sc.nextInt();
        Integer m = sc.nextInt();
        ArrayList<Integer> diffList = new ArrayList<Integer>();
        int[][] dp = new int[51][1001];
        
        for (int i = 0; i < n; i++) {
            diffList.add(sc.nextInt());
        }
        
        dp[0][s] = 1;
        
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < m + 1; j++) {
                if (dp[i - 1][j] == 0) continue;
                if (j - diffList.get(i - 1) >= 0) {
                    dp[i][j - diffList.get(i - 1)] = 1;
                }
                if (j + diffList.get(i - 1) <= m) {
                    dp[i][j + diffList.get(i - 1)] = 1;
                }
            }
        }
        
        int result = -1;
        for (int i = m; i >= 0; i--) {
            if (dp[n][i] == 1) {
                result = i;
                break;
            }
        }
        
        System.out.println(result);
    }
}

문제 제목 : LCS

난이도 : 하

문제 유형 : 동적 프로그래밍(DP), LCS

추천 풀이 시간 : 30분 (못하면 2배 60분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        int[][] dp = new int[1001][1001];
        
        for (int i = 1; i < str1.length() + 1; i++) {
            for (int j = 1; j < str2.length() + 1; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        
        System.out.println(dp[str1.length()][str2.length()]);
    }
}

문제 제목 : 가장 긴 증가하는 부분 수열

난이도 : 하

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 30분 (못하면 2배 60분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int result = 0;
        ArrayList<Integer> a = new ArrayList<Integer>();
        int[] dp = new int[1000];
        
        for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (a.get(i) > a.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }  

        System.out.println(result);
    }
}