코테 유형 별 기출 선정하기

📝DP

📌최장 증가 부분 수열(LIS)

11053번: 가장 긴 증가하는 부분 수열

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int dp[] = new int[a];
        int arr[] = new int[a];
        Arrays.fill(dp, 1);

        for(int i = 0; i < a; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int max = 0;
        for(int i = 0; i < a; i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1;
            }

            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

12015번: 가장 긴 증가하는 부분 수열 2 

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

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

        List<Integer> li = new ArrayList<>();
        for(int i = 0; i < a; i++){
            int cnt = Integer.parseInt(st.nextToken());

            int pos = Collections.binarySearch(li, cnt);

            if(pos < 0) pos = -(pos + 1);

            if(pos == li.size()){
                li.add(cnt);
            }else{
                li.set(pos, cnt);
            }
        }

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

 

14002번: 가장 긴 증가하는 부분 수열 4

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

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

        int arr[] = new int[a];

        for(int i = 0; i < a; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int dp[] = new int[a]; // dp 배열
        int prev[] = new int[a]; // 가장 긴 증가하는 부분 수열 출력용

        Arrays.fill(dp, 1); //기본 1
        Arrays.fill(prev, -1);

        int max = 0;
        int index = 0;
        for(int i = 0; i < a; i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j] && dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
            if(max < dp[i]){
                max = dp[i];
                index = i;
            }
        }
        StringBuilder sb = new StringBuilder();

        int cnt = index;
        while(cnt != -1){
            sb.insert(0, arr[cnt] + " ");
            cnt = prev[cnt];
        }
        System.out.println(max);
        System.out.println(sb);


    }
}

11054번: 가장 긴 바이토닉 부분 수열

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int up[] = new int[a];
        int down[] = new int[a];
        int arr[] = new int[a];
        Arrays.fill(up, 1);
        Arrays.fill(down, 1);

        for(int i = 0; i < a; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }


        for(int i = 1; i < a; i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j] && up[i] < up[j] + 1){
                    up[i] = up[j] + 1;
                }
            }
        }

        for(int i = a - 2; i >= 0; i--){
            for(int j = a - 1; j > i; j--){
                if(arr[i] > arr[j] && down[i] < down[j] + 1){
                    down[i] = down[j] + 1;
                }
            }
        }

        int max = 0;
        for(int i = 0; i < a; i++){
            max = Math.max(max, up[i] + down[i] - 1);
        }

        System.out.println(max);
    }
}

📌 다차원 DP

17069번: 파이프 옮기기2

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

public class Main {
    static final int HORIZONTAL = 0;
    static final int VERTICAL = 1;
    static final int DIAGONAL = 2;

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

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

        long[][][] dp = new long[n][n][3];
        dp[0][1][HORIZONTAL] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (map[i][j] == 1) continue;

                if (j - 1 >= 0) {
                    dp[i][j][HORIZONTAL] += dp[i][j - 1][HORIZONTAL] + dp[i][j - 1][DIAGONAL];
                }
                if (i - 1 >= 0) {
                    dp[i][j][VERTICAL] += dp[i - 1][j][VERTICAL] + dp[i - 1][j][DIAGONAL];
                }

                if (i - 1 >= 0 && j - 1 >= 0) {
                    if (map[i - 1][j] == 0 && map[i][j - 1] == 0) {
                        dp[i][j][DIAGONAL] += dp[i - 1][j - 1][HORIZONTAL] +
                                              dp[i - 1][j - 1][VERTICAL] +
                                              dp[i - 1][j - 1][DIAGONAL];
                    }
                }
            }
        }

        long result = dp[n - 1][n - 1][HORIZONTAL] +
                      dp[n - 1][n - 1][VERTICAL] +
                      dp[n - 1][n - 1][DIAGONAL];

        System.out.println(result);
    }
}

10942번: 팰린드롬?

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

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 arr[] = new int[n + 1];

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

        int dp[][] = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++){
            dp[i][i] = 1;
        }

        for(int i = 1; i < n; i++){
            if(arr[i] == arr[i + 1])
                dp[i][i + 1] = 1;
        }

        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= n - i; j++){
                int x = j + i;
                if(arr[j] == arr[x] && dp[j + 1][x - 1] == 1)
                    dp[j][x] = 1;
            }
        }

        StringBuilder sb = new StringBuilder();
        int m = Integer.parseInt(br.readLine());
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            sb.append(dp[a][b]).append("\n");
        }

        System.out.println(sb);        
    }
}

17404번: RGB 거리2

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

public class Main {
    static final int INF = 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());

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

        int[][][] dp = new int[n + 1][3][3]; 
        int result = INF;

        for (int start = 0; start < 3; start++) {
            for (int c = 0; c < 3; c++) {
                if (c == start) dp[1][c][start] = cost[1][c];
                else dp[1][c][start] = INF;
            }

            for (int i = 2; i <= n; i++) {
                dp[i][0][start] = Math.min(dp[i - 1][1][start], dp[i - 1][2][start]) + cost[i][0];
                dp[i][1][start] = Math.min(dp[i - 1][0][start], dp[i - 1][2][start]) + cost[i][1];
                dp[i][2][start] = Math.min(dp[i - 1][0][start], dp[i - 1][1][start]) + cost[i][2];
            }

            for (int end = 0; end < 3; end++) {
                if (end == start) continue;
                result = Math.min(result, dp[n][end][start]);
            }
        }

        System.out.println(result);
    }
}

 

📝BFS/DFS

📌BFS + 다익스트라

13549번: 숨바꼭질 3

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

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] dp = new int[100001];
        Arrays.fill(dp, Integer.MAX_VALUE);

        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[1] - b[1]);

        q.add(new int[]{n, 0});
        dp[n] = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int pos = now[0];
            int time = now[1];

            if (pos == m) {
                System.out.println(time);
                return;
            }

            // 순간이동 (0초)
            if (pos * 2 < 100001 && dp[pos * 2] > time) {
                dp[pos * 2] = time;
                q.add(new int[]{pos * 2, time});
            }

            // 뒤로 걷기 (1초)
            if (pos - 1 >= 0 && dp[pos - 1] > time + 1) {
                dp[pos - 1] = time + 1;
                q.add(new int[]{pos - 1, time + 1});
            }

            // 앞으로 걷기 (1초)
            if (pos + 1 < 100001 && dp[pos + 1] > time + 1) {
                dp[pos + 1] = time + 1;
                q.add(new int[]{pos + 1, time + 1});
            }
        }
    }
}

13913번: 숨바꼭질4

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

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] dp = new int[100001];
        int[] prev = new int[100001];
        Arrays.fill(dp, Integer.MAX_VALUE);
        Arrays.fill(prev, -1);
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[1] - b[1]);

        q.add(new int[]{n, 0});
        dp[n] = 0;

        while (!q.isEmpty()) {
            int[] now = q.poll();
            int pos = now[0];
            int time = now[1];

            if(dp[pos] < time) continue;

            if(pos == m) break;
            
            // 순간이동 (1초)
            if (pos * 2 < 100001 && dp[pos * 2] > time + 1) {
                dp[pos * 2] = time + 1;
                prev[pos * 2] = pos;
                q.add(new int[]{pos * 2, time + 1});
            }

            // 앞으로 걷기 (1초)
            if (pos + 1 < 100001 && dp[pos + 1] > time + 1) {
                dp[pos + 1] = time + 1;
                prev[pos + 1] = pos;
                q.add(new int[]{pos + 1, time + 1});
            }
            // 뒤로 걷기 (1초)
            if (pos - 1 >= 0 && dp[pos - 1] > time + 1) {
                dp[pos - 1] = time + 1;
                prev[pos - 1] = pos;
                q.add(new int[]{pos - 1, time + 1});
            }
        }

        System.out.println(dp[m]);
        StringBuilder sb = new StringBuilder();
        sb.append(m);
        int cnt = m;
        while(prev[cnt] != -1){
            sb.insert(0, prev[cnt] + " ");
            cnt = prev[cnt];
        }

        System.out.println(sb);
    }
}

📌DFS + 백트래킹

15649번: N과 M 1

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int n,m;
    static int arr[];
    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());
        arr = new int[m];
        boolean visited[] = new boolean[n + 1];
        dfs(0, visited);
        System.out.println(sb);
    }

    public static void dfs(int depth, boolean visited[]){
        if(depth == m){
            for(int i = 0; i < m; i++){
                sb.append(arr[i]).append(" ");
            }

            sb.append("\n");
            return;
        }

        for(int i = 1; i <= n; i++){
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = i;
                dfs(depth + 1, visited);
                visited[i] = false;
            }
        }
    }
}

15650번 : N과 M 2

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int n,m;
    static int arr[];
    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());
        arr = new int[m];
        dfs(0, 1);
        System.out.println(sb);
    }

    public static void dfs(int depth, int start){
        if(depth == m){
            for(int i = 0; i < m; i++){
                sb.append(arr[i]).append(" ");
            }

            sb.append("\n");
            return;
        }

        for(int i = start; i <= n; i++){
            arr[depth] = i;
            dfs(depth + 1, i + 1);
        }
    }
}

15651번 : N과 M 3

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int n,m;
    static int arr[];
    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());
        arr = new int[m];
        dfs(0);
        System.out.println(sb);
    }

    public static void dfs(int depth){
        if(depth == m){
            for(int i = 0; i < m; i++){
                sb.append(arr[i]).append(" ");
            }

            sb.append("\n");
            return;
        }

        for(int i = 1; i <= n; i++){
            arr[depth] = i;
            dfs(depth + 1);
        }
    }
}

14888번 : 연산자 끼워넣기

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

public class Main {
    static int n;
    static int arr[];
    static int m[];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;

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

        arr = new int[n];
        m = new int[4];

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

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) m[i] = Integer.parseInt(st.nextToken());

        dfs(1, arr[0]);

        System.out.println(max);
        System.out.println(min);
    }

    public static void dfs(int depth, int num) {
        if (depth == n) {
            max = Math.max(max, num);
            min = Math.min(min, num);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if (m[i] > 0) {
                m[i]--;
                if (i == 0) dfs(depth + 1, num + arr[depth]);
                else if (i == 1) dfs(depth + 1, num - arr[depth]);
                else if (i == 2) dfs(depth + 1, num * arr[depth]);
                else {
                    int result;
                    if (num < 0)
                        result = -(-num / arr[depth]);
                    else
                        result = num / arr[depth];
                    dfs(depth + 1, result);
                }
                m[i]++;
            }
        }
    }
}

 

📝해시

📌해시 조합

9375번: 패션왕 신해빈

import java.io.*;
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());

        while(t-- > 0){
            Map<String, HashSet<String>> m = new HashMap<>();
            int n = Integer.parseInt(br.readLine());

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

                m.computeIfAbsent(b, k -> new HashSet<>()).add(a);
            }
            int result = 1;
            for(HashSet<String> h : m.values()){
                result *= (h.size() + 1);
            }
            result -= 1;
            System.out.println(result);
        }

    }
}

7785번: 회사에 있는 사람

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

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());
        Map<String, Integer> m = new HashMap<>();

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

            if(b.equals("enter")){
                m.put(a, 0);
            }else{
                m.remove(a);
            }
        }

        List<String> names = new ArrayList<>(m.keySet());
        Collections.sort(names, Collections.reverseOrder());
        

        for (String name : names) {
            System.out.println(name);
        }
    }
}

5052번: 전화번호 목록

import java.io.*;
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());

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            Map<String, Boolean> map = new HashMap<>();
            String[] arr = new String[n];

            for (int i = 0; i < n; i++) {
                arr[i] = br.readLine();
            }

            for (String phone : arr) {
                map.put(phone, false);
            }

            boolean flag = false;

            for (String phone : arr) {
                for (int len = 1; len < phone.length(); len++) {
                    String prefix = phone.substring(0, len);
                    if (map.containsKey(prefix) && map.get(prefix) == false) {
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }

            System.out.println(flag ? "NO" : "YES");
        }
    }
}

 

📝자료구조

📌스택

1918번 : 후위표기식

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

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

        String target = br.readLine();
        Stack<Character> s = new Stack<>();

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < target.length(); i++){
            char cnt = target.charAt(i);
            

            if(cnt == '('){
                s.push(cnt);
            }else if(cnt == ')'){
                while(!s.isEmpty() && s.peek() != '('){
                    sb.append(s.pop());
                }

                s.pop();
            }else if(cnt == '+' || cnt == '-'){
                if(!s.isEmpty() && (s.peek() == '*' || s.peek() == '/')){
                    sb.append(s.pop());
                }
                if(!s.isEmpty() && s.peek() != '('){
                    sb.append(s.pop());
                }
                s.push(cnt);
            }else if(cnt == '*' || cnt == '/'){
                if(!s.isEmpty() && (s.peek() == '*' || s.peek() == '/')){
                    sb.append(s.pop());
                }
                s.push(cnt);
            }else{
                sb.append(cnt);
            }
        }

        while(!s.isEmpty()){
            sb.append(s.pop());
        }
        System.out.println(sb);
    }

}

// 스택에 계산식을 넣는다.
// 만약 계산식이 x / 가 나온 후 - +가 나오면 x를 먼저 출력한다. 만약 가로가 나오면 가로 먼저 출력
// 만약 ( 가 나오면 다음 것은 일단 스택에 넣지 않고 출력을 한다.

계속 추가 예정