<stdio.han>

[문제 링크]

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

[난이도]

- Level 2

[알고리즘]

- 구현

- 배열

[코드]

import java.util.*;

class Solution {
    public String[] solution(int[][] line) {
        long maxX = Long.MIN_VALUE;
        long maxY = Long.MIN_VALUE;
        long minX = Long.MAX_VALUE;
        long minY = Long.MAX_VALUE;

        List<long[]> list = new ArrayList<>();

        for (int i = 0; i < line.length - 1; i++) {
            for (int j = i + 1; j < line.length; j++) {
                long A = line[i][0];
                long B = line[i][1];
                long E = line[i][2];
                long C = line[j][0];
                long D = line[j][1];
                long F = line[j][2];

                long denominator = A * D - B * C;

                if (denominator == 0) continue;  // 평행 또는 동일 직선

                long numeratorX = B * F - E * D;
                long numeratorY = E * C - A * F;

                // 정수 교차점인지 확인
                if (numeratorX % denominator != 0 || numeratorY % denominator != 0) continue;

                long x = numeratorX / denominator;
                long y = numeratorY / denominator;

                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);

                list.add(new long[]{x, y});
            }
        }

        int width = (int)(maxX - minX + 1);
        int height = (int)(maxY - minY + 1);

        char[][] graph = new char[height][width];
        for (char[] row : graph) {
            Arrays.fill(row, '.');
        }

        for (long[] point : list) {
            int x = (int)(point[0] - minX);
            int y = (int)(maxY - point[1]);  // y축 뒤집기

            graph[y][x] = '*';
        }

        String[] answer = new String[height];
        for (int i = 0; i < height; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < width; j++) {
                sb.append(graph[i][j]);
            }
            answer[i] = sb.toString();
        }

        return answer;
    }
}

[풀이]

단순 구현 문제이다. 중요한점은 int가 아닌 long타입으로 변환해서 풀어야한다는것이다. 그 이유는 int*int가 int의 범위를 벗어나는 경우가 있어 테스트케이스29번을 통과하지 못하기 때문이다.

[문제 링크]

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

[난이도]

- Gold 4

[알고리즘]

- BFS

- 백트래킹

[코드]

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

public class Main {
    static int N, M, result = 0;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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());

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        backTracking(0);
        System.out.println(result);
    }

    static void backTracking(int depth) {
        if (depth == 3) {
            result = Math.max(result, checkSafeArea(bfs()));
            return;
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1; // 벽을세움
                    backTracking(depth + 1);
                    map[i][j] = 0; // 벽을 되돌려놓음
                }
            }
        }
    }
    static int[][] bfs() {
        int[][] newMap = new int[N][M];
        for (int i = 0; i < N; i++) {
            System.arraycopy(map[i], 0, newMap[i], 0, M);
        }
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newMap[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (newMap[nx][ny] == 0) {
                        newMap[nx][ny] = 2;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
        return newMap;
    }
    static int checkSafeArea(int[][] newMap) {
        int safeArea = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (newMap[i][j] == 0) {
                    safeArea++;
                }
            }
        }
        return safeArea;
    }
}

[풀이]

4방탐색을하며 바이러스를 퍼트리는 부분은 일반적인 bfs알고리즘을 활용해 푼다. 더 생각해야할 부분은 벽을 3개 세우는데 반드시 3개를 세워야하기 때문에 백트래킹을 활용해 벽 3개를 세울 수 있는 가능한 모든 경우의 수를 생각해 세운 후 바이러스를 퍼트리고 다 퍼진후 안전한 공간의 개수를 세준다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- 그리디

[코드]

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[][] meetings = new int[N][2];

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

        // 끝나는 시간을 기준으로 정렬, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬
        Arrays.sort(meetings, (a, b) -> {
            if (a[1] == b[1]) {
                return Integer.compare(a[0], b[0]);
            }
            return Integer.compare(a[1], b[1]);
        });

        int count = 0;
        int lastEndTime = 0;

        for (int i = 0; i < N; i++) {
            if (meetings[i][0] >= lastEndTime) {
                lastEndTime = meetings[i][1];
                count++;
            }
        }

        System.out.println(count);
    }
}

[풀이]

정렬을 할 때 끝나는 시간을 기준으로 오름차순 정렬을 해준다.

그 후 현재시간이 0이라고 할 때 해당 배열의 시작 시간이 현재시간보다 크거나 같을 경우 현재시간을 해당 배열의 끝나는시간으로 변경해준다. 변경될 때 마다 count를 늘려준다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- DP

- 다익스트라

[코드]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt(); // 지름길의 개수
        int D = scanner.nextInt(); // 고속도로의 길이

        // graph를 생성하고 초기화
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= D; i++) {
            graph.add(new ArrayList<>()); // 노드의 개수만큼 생성
        }

        // 지름길 정보를 graph에 추가
        for (int i = 0; i < N; i++) {
            int u = scanner.nextInt(); // 시작 노드
            int v = scanner.nextInt(); // 도착 노드
            int w = scanner.nextInt(); // 가중치
            if (v <= D) { // 노드범위 이상일경우 추가하지 않는다.
                graph.get(u).add(new int[]{v, w}); //
            }
        }

        int[] dist = new int[D + 1]; // 가중치를 기록할 배열
        Arrays.fill(dist, Integer.MAX_VALUE); // 초기값은 모두 INF
        dist[0] = 0; // 시작 위치는 0

        // int[] a 중에서 두번째 요소인 a[1]을 기준으로 큐를 정렬, 즉 가중치(비용)을 기준으로 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{0, 0}); // {현재 위치, 현재 비용}

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int currentPos = current[0];
            int currentCost = current[1];

            // 만약 현재 비용이 기록된 비용보다 크다면, 이미 더 적은 비용으로 도달한 경로가 존재하므로 무시
            if (currentCost > dist[currentPos]) continue;

            // 다음 지점으로 이동 (일반 도로, 현재 위치에서 한 칸 앞으로 이동)
            // 현재위치에서 한 칸 앞으로 이동한 위치가 D(도로의 길이, 간선의 범위)를 넘지않는경우
            // 현재위치에서 한칸 앞으로 이동한 위치까지의 비용이 기존에 기록된 비용보다 작은 경우
            if (currentPos + 1 <= D && currentCost + 1 < dist[currentPos + 1]) {
                dist[currentPos + 1] = currentCost + 1; // 다음 위치까지의 비용 갱신
                pq.add(new int[]{currentPos + 1, currentCost + 1}); // 우선순위 큐에 추가
            }

            // 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
            for (int[] edge : graph.get(currentPos)) {
                int nextPos = edge[0]; // 지름길의 도착 위치
                int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
                // 지름길을 이용한 비용이 더 적다면 비용 갱신
                if (nextCost < dist[nextPos]) {
                    dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
                    pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
                }
            }
        }

        System.out.println(dist[D]);
    }
}

[풀이]

일반적인 다익스트라 알고리즘과 같다. 하지만 추가된 부분이 있다.

// 지름길로 이동 (현재 위치에서 연결된 모든 지름길을 탐색)
            for (int[] edge : graph.get(currentPos)) {
                int nextPos = edge[0]; // 지름길의 도착 위치
                int nextCost = currentCost + edge[1]; // 지름길을 이용한 다음 위치까지의 비용
                // 지름길을 이용한 비용이 더 적다면 비용 갱신
                if (nextCost < dist[nextPos]) {
                    dist[nextPos] = nextCost; // 다음 위치까지의 비용 갱신
                    pq.add(new int[]{nextPos, nextCost}); // 우선순위 큐에 추가
                }

지름길을 이용한 경우의 가중치를 한번 더 생각해주어야 한다는 것이다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- DP

[코드]

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

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[] wine = new int[n+1];
        for (int i = 1; i <= n; i++) {
            wine[i] = Integer.parseInt(br.readLine());
        }

        if (n == 1) {
            System.out.println(wine[1]);
            return;
        }

        // 초기값 설정
        int[] dp = new int[n+1];
        dp[1] = wine[1];
        if (n > 1) {
            dp[2] = wine[1] + wine[2];
        }

        // 점화식 도출
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i]));
        }
        /**
         * dp[i-1]  = i번째 잔을 안마시는경우
         * dp[i-2] + wine[i] = i-1번째잔을 마시지 않고 현재와인을 마시는 경우
         * dp[i-3] + wine[i-1] + wine[i] = i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우
         */

        System.out.println(dp[n]);
    }
}

[풀이]

1. DP 배열 정의: dp[i]는 i번째 포도주 잔까지 최대로 마실 수 있는 포도주의 양을 의미합니다.
2. 점화식 수립:
   • dp[i]는 세 가지 경우 중 최댓값이 됩니다:
     1. i번째 잔을 마시지 않는 경우: dp[i-1]
     2. i번째 잔을 마시고, i-1번째 잔을 마시지 않는 경우: dp[i-2] + wine[i]
     3. i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔을 마시지 않는 경우: dp[i-3] + wine[i-1] + wine[i]
3. 초기 조건 설정:
   • dp[0]은 첫 번째 잔을 마시는 경우입니다.
   • dp[1]은 첫 번째와 두 번째 잔을 마시는 경우입니다.
   • dp[2]은 세 번째 잔까지의 최댓값을 고려합니다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int k;
    static char[] operators;
    static boolean[] visited = new boolean[10];
    static List<String> results = new ArrayList<>();

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

        // 공백을 없애고 각 글자를 char array로 담는다
        operators = br.readLine().replace(" ", "").toCharArray();

        solve("", 0);

        results.sort(String::compareTo); // results 리스트를 사전순으로 정렬

        System.out.println(results.get(results.size() - 1)); // 최댓값
        System.out.println(results.get(0)); // 최솟값
    }

    /**
     *
     * @param num 현재까지 생성된 숫자
     * @param index 현재 처리중인 숫자자리
     */
    static void solve(String num, int index) {
        if (index == k + 1) {
            results.add(num);
            return;
        }

        for (int i = 0; i <= 9; i++) {
            if (visited[i]) continue; // 이미사용한 숫자라면 통과

            // index가 0일경우에는 비교할 숫자가 하나밖에 없기때문에 다음숫자로 넘어감
            // 혹은 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
            if (index == 0 || check(num.charAt(index - 1) - '0', i, operators[index - 1])) {
                visited[i] = true;
                solve(num + i, index + 1);
                visited[i] = false; // 완전탐색을 위해 복구
            }
        }
    }

    static boolean check(int a, int b, char operator) {
        if (operator == '<') return a < b;
        else return a > b;
    }
}

[풀이]

백트래킹 알고리즘을 활용할 때 넘겨주는 매개변수를 num : 현재까지 생성된 숫자, index 현재 처리중인 숫자 를 넘겨준다.

for문을 돌며 숫자 두개를 입력받은 부등호와 비교해 참일경우에만 다음숫자를 진행한다.

[문제 링크]

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

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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[] primeStarts = {2, 3, 5, 7};

        // 결과를 저장할 리스트
        List<Integer> results = new ArrayList<>();

        // 신기한 소수 찾기
        for (int start : primeStarts) { // 일의 자리가 2, 3, 5, 7 이여야함
            findAmazingPrimes(N, start, 1, results);
        }

        // 결과 정렬 및 출력
        Collections.sort(results); // 오름차순으로 정렬 후 출력
        for (int num : results) {
            System.out.println(num);
        }
    }

    // 재귀적으로 신기한 소수를 찾는 함수

    /**
     *
     * @param N N자리
     * @param current 현재 숫자
     * @param length 현재 숫자의 길이
     * @param results 현재 숫자의 길이가 N자리가 되면 results 리스트에 추가함
     */
    private static void findAmazingPrimes(int N, int current, int length, List<Integer> results) {
        if (length == N) { // N자리가 될 때까지 반복
            results.add(current);
            return;
        }

        // 다음 자리수로 확장
        for (int i = 1; i <= 9; i++) {
            int next = current * 10 + i;
            if (isPrime(next)) { // 소수면 true
                findAmazingPrimes(N, next, length + 1, results);
            }
        }
    }

    // 소수 판별 함수
    private static boolean isPrime(int num) {
        if (num < 2) return false; // 2보다 작으면 소수가 아님
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) return false; // num이 i로 나눠떨어지면 소수가 아님
        }
        return true;
    }
}

[풀이]

일의 자리가 소수인것은  2, 3, 5, 7 밖에 없으므로 2, 3, 5, 7을 기준으로 신기한 소수를 찾는다. 소수 판별함수는 숫자가 어떤 특정한 수로 나눠떨어지면 소수가 아닌 성질을 활용한다.

[문제 링크]

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

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int N, M;
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;
    static boolean found = false;

    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());

        adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(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());
            adj.get(a).add(b); // 양방향 간선
            adj.get(b).add(a); // 양방향 간선
        }

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (!found) { // ABCDE가 존재하면 true 발견하지 못했다면 false
                dfs(i, 0);
            }
        }

        System.out.println(found ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        if (depth == 4) { // depth가 4면 ABCDE가 서로 연결되어있다는 뜻
            found = true;
            return;
        }

        visited[node] = true;

        for (int next : adj.get(node)) {
            if (!visited[next]) { // 중복방문을 방지
                dfs(next, depth + 1);
                if (found) return;
            }
        }

        visited[node] = false; // 완전탐색을위해 다시 false로 변경
    }
}

[풀이]

이중 ArrayList로 인정리스트인 Adjacency list를 선언해준후.

각 정점을 기준으로 dfs를 반복해 depth가 4인경우를 찾아준다.

depth가 4일경우 ABCDE가 친구인 경우이다.

찾았다면 1을 못찾았다면 0을 출력한다.