문제

n개의 알바 정보가 주어졌을때, 시작일과 종료일이 겹치지 않는 경우에만 이어서 할 수 있다. 이때 최대로 벌 수 있는 알바비는?

문제 풀이 과정

dp의 전형적인 문제, 시작일, 종료일, 알바비가 순서대로 주어지기 때문에 종료일을 기준으로 정렬해야 알바를 가장 많이 할 수 있다. (시간적으로)

문제 풀이 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] s = new int[n][3];

        for (int i = 0; i < n; i++) {
            s[i][0] = sc.nextInt();
            s[i][1] = sc.nextInt();
            s[i][2] = sc.nextInt();
        }
        Arrays.sort(s, Comparator.comparingInt(a -> a[1]));
         // DP 배열 초기화
        int[] dp = new int[n];
        dp[0] = s[0][2]; // 첫 번째 아르바이트의 급여

        for (int i = 1; i < n; i++) {
            int[] current = s[i];
            int maxPay = current[2];

            // 현재 아르바이트와 겹치지 않는 이전 아르바이트를 찾아 최대 급여 합산
            for (int j = i - 1; j >= 0; j--) {
                if (s[j][1] < current[0]) { // 겹치지 않는 경우
                    maxPay = Math.max(maxPay, dp[j] + current[2]);
                }
            }

            // 현재 아르바이트를 선택하지 않을 경우와 선택할 경우의 최대값을 dp에 저장
            dp[i] = Math.max(dp[i - 1], maxPay);
        }

        // 마지막 값이 철수가 벌 수 있는 최대 금액
        System.out.print(dp[n - 1]);

    }
}

문제

n * m의 숫자가 적혀있는 사각형에서 1,1에서 조건을 만족하여 밟을 수 있는 칸의 수의 최대를 구하시오.

• 지금 밟은 칸보다 큰 수만 밟을 수 있다.
• 지금 칸의 위치에서 최소 한 칸 오른쪽, 아래를 밟을 수 있다. (x, y -> x + 1, y + 1)

문제 풀이 과정

• int[][] dp를 만들어서 0,0에서부터 조건에 만족하는 경우에 값을 갱신

문제 풀이 코드

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        grid = new int[n][m];
        dp = new int[n][m];

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                grid[i][j] = sc.nextInt();
                dp[i][j] = -1;
            }
        }

        dp[0][0] = 1;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                for (int x = 0; x < i; x++){
                    for (int y = 0; y < j; y++){
                        if (dp[x][y] == -1)
                            continue;

                        if (grid[i][j] > grid[x][y]) // 밟을 수 있는 경우
                            dp[i][j] = Math.max(dp[x][y] + 1, dp[i][j]);
                    }
                }
            }
        }

        max = 0;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++)
                max = Math.max(max, dp[i][j]);
        }

        System.out.print(max);

    }

문제

n이 주어지고 n * n 으로 이루어진 숫자들의 배열이 주어진다. 시작점에서 본인보다 큰 수로만 이동이 가능 할 때, 최대로 이동할 수 있는 거리를 구하여라.

문제 풀이 방법

• 처음에는 dp + bfs로 풀이하려다가 메모리 초과 발생
• dp를 찾는 함수를 구해서 풀이하려다가 원하는 답이 나오지 않음

오답 풀이

    public static int findDP(int x, int y){
        if (dp[x][y] > -1)
            return dp[x][y];

        dp[x][y] = 1;

        int origin = grid[x][y];

        for (int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (inRange(nx, ny)){
                int forCheck = grid[nx][ny];
                if (origin < forCheck)
                    dp[x][y] = Math.max(dp[x][y], dp[nx][ny] + 1);
            }
        }

        return dp[x][y];
    }

• 여기서는 dp의 값이 원하는 값이 나오지 않음

맞는 풀이

    public static int findDP(int x, int y){
        if (dp[x][y] > -1)
            return dp[x][y];

        dp[x][y] = 1;

        int origin = grid[x][y];

        for (int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (inRange(nx, ny)){
                int forCheck = grid[nx][ny];
                if (origin < forCheck)
                    dp[x][y] = Math.max(dp[x][y], findDP(nx, ny) + 1);
            }
        }

        return dp[x][y];
    }

• 차이는 dp[x][[y] = Math.max() 부분이다. max 값을 구할 때, findDP(nx, ny)로 함수를 통해 dp값을 찾는 것과 dp[nx][ny]로 입력된 dp값을 찾는 것이다.

🔥 차이점 요약

메모리제이션

계산 했던 값은 다시 계산하지 않도록 저장하는 것!

public static int findDP(int x, int y){
        if (dp[x][y] > -1) // 초기 설정 값이 아니면
            return dp[x][y]; // 계산 한 값을 리턴!

문제

n 이 주어지면 n개의 노드로 만들 수 있는 BST 개수 출력

문제 풀이

• dp로 문제를 푸는 것은 알겠음 -> 어떤 규칙이 있는지.
• 모든 경우의 총합을 구하기

  // node가 4인 경우에
  // root로 한개 있고
  // 왼쪽에 0개 오른쪽에 3개
  // 왼쪽에 1개 오른쪽에 2개 ... 의 모든 경우를 다 더하기
  dp[4] = dp[0] * dp[3] + dp[1] * dp[2] + dp[2] * dp[1] + dp[3] * dp[0];

풀이 코드

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];

        dp[0] = 1; // node가 0인 경우는 1가지 밖에 없음

        int sum = 0;
        for (int i = 1; i <= n; i++){
            sum = 0;
            for (int j = 0; j < i; j++)
                sum += dp[j] * dp[i - 1 - j];
            dp[i] = sum;
        }

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

문제

n이 주어지고 4가지 연산을 사용하여 1을 만들 수 있는 연산의 최소 수를 구하라

문제 풀이

• 4가지 방법을 모두 사용해봐야함 -> 4군데를 도는 bfs라고 생각
• 지나간 곳을 지나가지 않도록 하는 visited 필요 -> 범위 설정에 어려움

• boolean[] visited 대신에 Set<Integer> set를 사용하자

풀이 코드

import java.util.*;

public class Main {
    public static int n;
    public static Queue<int[]> q = new LinkedList<>();
    public static Set<Integer> set = new HashSet<>();

    public static int calculation(int idx, int n){
        if (idx == 0)
            return n - 1;
        else if (idx == 1)
            return n + 1;
        else if (idx == 2 && n % 2 == 0)
            return n / 2;
        else if (idx == 3 && n % 3 == 0)
            return n / 3;
        return n;
    }

    public static int bfs(){
        while (!q.isEmpty()){
            int[] tmp = q.poll();
            int x = tmp[0];
            int move = tmp[1];

            if (x == 1)
                return move;

            for (int i = 0; i < 4; i++){
                int nx = calculation(i, x);
                if (nx == n || set.contains(nx))
                    continue;
                set.add(nx);
                q.add(new int[]{nx, move + 1});
            }
        }

        return -1;
    }

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

        q.add(new int[]{n, 0});
        set.add(n);
        System.out.print(bfs());

    }
}

문제

n * n의 숫자로 되어 있는 격자에 k개의 나라를 방문하는데, 이 나라와 인접하고 차이가 u이상 d이하면 방문 할 수 있다. 이때 방문할 수 있는 최대 나라의 수는?

문제 풀이

• 나라와 인접한 나라를 찾음 -> BFS
• 최대 경우를 찾음 -> 백트래킹

문제 해결 코드

public static void find(boolean[][] visited, int cnt, int kCnt) {
    if (kCnt == k + 1) {
        max = Math.max(max, cnt);
        return;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                // 방문 상태 복사
                boolean[][] nextVisited = copyVisited(visited);
                Queue<int[]> q = new LinkedList<>();
                q.add(new int[]{i, j});
                nextVisited[i][j] = true;

                int localCnt = 1; // 현재 시작점 포함
                while (!q.isEmpty()) {
                    int[] tmp = q.poll();
                    int x = tmp[0];
                    int y = tmp[1];

                    for (int d = 0; d < 4; d++) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (inRange(nx, ny) && !nextVisited[nx][ny] && diff(x, y, nx, ny)) {
                            nextVisited[nx][ny] = true;
                            q.add(new int[]{nx, ny});
                            localCnt++;
                        }
                    }
                }

                find(nextVisited, cnt + localCnt, kCnt + 1); // 백트래킹 재귀
            }
        }
    }
}

• bfs의 백트래킹 해결이 문제 해결의 요점
• 방문할 수 있는 수 -> bfs를 위해 queue에 넣을 좌표의 수
• k가 2 이상인 경우, 방문하지 않은 곳에서 출발 -> 최대의 수를 구할 수 있음

문제

n * m 배열이 물(0)과 빙하(1)로 이루어져 있다. 시간이 지날 수록 물에 둘러쌓인 빙하는 외각부터 1칸씩 녹는데 녹는 시간과, 마지막에 녹은 빙하의 크기를 구하라

0 0 0 0 0 0 0   0 0 0 0 0 0 0
0 1 1 1 1 0 0   0 0 0 0 0 0 0
0 1 1 0 1 1 0   0 0 1 0 1 0 0
0 1 0 1 1 1 0   0 0 0 1 1 0 0
0 1 1 1 1 1 0   0 0 0 0 0 0 0
0 0 0 0 0 0 0   0 0 0 0 0 0 0

초기 빙하 -> 1초 후 빙하

문제 해결 방안

• bfs로 외부의 물을 구하고
• 외부의 물과 접해 있는 곳을 모두 녹임
• 위를 반복

문제 풀이

import java.util.*;

public class Main {
    public static int n, m;
    public static int[][] grid;
    public static boolean[][] visited;
    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {1, -1, 0, 0};

    // 격자 범위 확인
    public static boolean inRange(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m;
    }

    // 외부 물(0)을 BFS로 찾기
    public static void markOutsideWater() {
        visited = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        visited[0][0] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (inRange(nx, ny) && !visited[nx][ny] && grid[nx][ny] == 0) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }

    // 빙하를 녹일 수 있는 위치 찾기
    public static List<int[]> findMeltTargets() {
        List<int[]> meltList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int d = 0; d < 4; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        if (inRange(nx, ny) && grid[nx][ny] == 0 && visited[nx][ny]) {
                            meltList.add(new int[]{i, j});
                            break;
                        }
                    }
                }
            }
        }

        return meltList;
    }

    // 전체 빙하가 다 녹았는지 체크
    public static boolean allMelted() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (grid[i][j] == 1)
                    return false;
        return true;
    }

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

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                grid[i][j] = sc.nextInt();

        int time = 0;
        int lastMeltCount = 0;

        while (!allMelted()) {
            markOutsideWater();  // 외부 물 탐색
            List<int[]> meltList = findMeltTargets();  // 녹일 빙하 찾기

            lastMeltCount = meltList.size();

            for (int[] pos : meltList) {
                grid[pos[0]][pos[1]] = 0;  // 빙하 녹이기
            }

            time++;
        }

        System.out.println(time + " " + lastMeltCount);
    }
}

public static List<int[]> findMeltTargets() {
        List<int[]> meltList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int d = 0; d < 4; d++) {
                        int nx = i + dx[d];
                        int ny = j + dy[d];
                        if (inRange(nx, ny) && grid[nx][ny] == 0 && visited[nx][ny]) {
                            meltList.add(new int[]{i, j});
                            break;
                        }
                    }
                }
            }
        }

        return meltList;
    }

위 함수가 물과 맞닿아 있는 빙하인지 체크하는 함수

• 주변이 물이고(0) 방문한 적이 있는지 판단 (외부의 물)
• 그렇다면 녹아야 할 빙하로 판단

문제

n * n의 숫자 행렬이 있을때, 오른쪽, 아래로만 이동할 수 있는데 (1, 1)에서 (n, n)까지의 경로에서의 최소값의 최대값을 구하라

문제 풀이

• DP인 것은 알 것 같음.
• DP로 그냥 경로의 최소 값은 쉽게 구할 수 있음
• 최소값의 최대값은 어떻게 구하는가 -> 핵심

문제 해결 방법

        int[][] dp = new int[n][n];
        dp[0][0] = matrix[0][0];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) continue;

                int fromTop = (i > 0) ? Math.min(dp[i - 1][j], matrix[i][j]) : Integer.MIN_VALUE;
                int fromLeft = (j > 0) ? Math.min(dp[i][j - 1], matrix[i][j]) : Integer.MIN_VALUE;

                dp[i][j] = Math.max(fromTop, fromLeft);
            }
        }
        System.out.println(dp[n - 1][n - 1]);

• 아래, 오른쪽 두방향으로만 진행 가능하므로, 두가지 방법으로 진행 했을때, 그 길의 최소 값 중 최대를 구하면 최소값의 최대값을 구할 수 있다.

문제

야구게임과 비슷한거 같은데 1~9까지 겹치지 않는 수의 조합으로 3자리가 주어지고 자리와 숫자가 일치하는 개수와 숫자만 일치하는 개수가 주어진다 이때 결정될 수 있는 숫자의 개수를 구하여라

예시
4
123 1 1
356 1 0
327 2 0
489 0 1

위의 경우 정답은 324, 328중 하나이므로 2를 리턴하게 된다.

풀이

• 가능한 모든 수를 주어진 조건에 대입하기

import java.util.Scanner;
public class Main {
    public static int[] num;
    public static int[] count1;
    public static int[] count2;
    public static int n;

    public static boolean checkSame(int i, int a){
        String str = String.valueOf(num[i]);
        String tmp = String.valueOf(a);

        int cnt = 0;

        for (int x = 0; x < 3; x++){
            if (str.charAt(x) == tmp.charAt(x))
                cnt++;
        }

        return cnt == count1[i];
    }

    public static boolean checkHave(int i, int a){
        String str = String.valueOf(num[i]);
        String tmp = String.valueOf(a);

        int cnt = 0;

        for (int x = 0; x < 3; x++){
            for (int y = 0; y < 3; y++){
                if (x != y && str.charAt(x) == tmp.charAt(y))
                    cnt++;
            }
        }

        return cnt == count2[i];
    }

    public static boolean isValid(int x){
        String str = String.valueOf(x);

        if (str.charAt(0) == str.charAt(1) || str.charAt(0) == str.charAt(2)
            || str.charAt(1) == str.charAt(2))
                return false;

        if (str.charAt(0) == '0' || str.charAt(1) == '0' || str.charAt(2) == '0')
            return false;

        for (int i = 0; i < n; i++){
            if (!checkSame(i, x) || !checkHave(i, x))
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        num = new int[n];
        count1 = new int[n];
        count2 = new int[n];
        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
            count1[i] = sc.nextInt();
            count2[i] = sc.nextInt();
        }

        int res = 0;
        for (int i = 123; i <= 987; i++){
            if (isValid(i))
                res++;
        }

        System.out.print(res);
    }
}

문제

n * m 배열에 q개의 쿼리가 주어지는데 x1 y1 x2 y2가 주어지고 이 주어진 범위 안에서 모서리 부분을 시계 방향으로 돌리고, 범위에 속하는 모든 값들을 본인 값 + 주변의 값의 평균으로 수정한다.

문제 풀이

• 구간을 정하고 값들을 밀어준다

코드

import java.util.Scanner;
public class Main {
    public static int[][] lst;
    public static int[][] queries;
    public static int n;
    public static int m;
    public static int q;

    public static void move(int x1, int y1, int x2, int y2) {  
        int temp = lst[x1][y1]; // 왼쪽 상단 값 저장 (시작점)

        // 1️⃣ 왼쪽 열 위로 이동
        for (int i = x1; i < x2; i++) {
            lst[i][y1] = lst[i + 1][y1];
        }

        // 2️⃣ 아래쪽 행 왼쪽으로 이동
        for (int j = y1; j < y2; j++) {
            lst[x2][j] = lst[x2][j + 1];
        }

        // 3️⃣ 오른쪽 열 아래로 이동
        for (int i = x2; i > x1; i--) {
            lst[i][y2] = lst[i - 1][y2];
        }

        // 4️⃣ 위쪽 행 오른쪽으로 이동
        for (int j = y2; j > y1 + 1; j--) {
            lst[x1][j] = lst[x1][j - 1];
        }

        lst[x1][y1 + 1] = temp; // 처음 저장했던 값 넣기

        update(x1, y1, x2, y2);
    }

    public static void update(int x1, int y1, int x2, int y2){ // 값 갱신
        int[][] tmp = new int[n][m];

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if(i >= x1 && i <= x2) {
                    if (j >= y1 && j <= y2){
                        int cnt = 1;
                        int sum = lst[i][j];
                        if (i - 1 >= 0){
                            cnt++;
                            sum += lst[i - 1][j];
                        }
                        if (i + 1 < n){
                            cnt++;
                            sum += lst[i + 1][j];
                        }
                        if (j - 1 >= 0){
                            cnt++;
                            sum += lst[i][j - 1];
                        }
                        if (j + 1 < m){
                            cnt++;
                            sum += lst[i][j + 1];
                        }
                        tmp[i][j] = sum / cnt;
                    }else
                        tmp[i][j] = lst[i][j];
                }else
                    tmp[i][j] = lst[i][j];
            }
        }
        lst = tmp;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        q = sc.nextInt();
        lst = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                lst[i][j] = sc.nextInt();
        queries = new int[q][4];
        for (int i = 0; i < q; i++)
            for (int j = 0; j < 4; j++)
                queries[i][j] = sc.nextInt() - 1;

        for (int i = 0; i < q; i++)
            move(queries[i][0], queries[i][1], queries[i][2], queries[i][3]);

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++)
                System.out.print(lst[i][j] + " ");
            System.out.println();
        }

    }
}

문제 설명

n * m 배열에 n * m개의 숫자가 주어진다. 이 숫자들을 겹치지 않는 두개의 직사각형 모양으로 감싸 그 속에 있는 숫자의 합을 더한다. 이 두 직사각형 속에 있는 수가 최대가 되는 경우를 구해라

풀이 과정

• 이전에 마름모 모양으로 숫자의 합을 더하는 것처럼 구할 수 있는 직사각형의 경우의 수를 생각 -> 한개의 직사각형의 최대값은 구할 수 있으나, 두개의 직사각형의 경우를 찾기 어려움
• 위의 경우에서 한개의 직사각형 값을 찾고, 나머지 부분에서 다른 직사각형을 찾으려 함 -> 기존의 직사각형과 겹치지 않아야하고, 경우의 수가 많아서 모든 부분을 구현하기 어렵다구 판단
• 특정한 위치에서의 모든 경우를 생각했었는데, 모든 점에서의 경우를 생각하는 것으로 변경 + 첫번째 직사각형과 두번째 직사각형이 겹치지 않는지 판단 -> 원하는 값을 찾을 수 있음 !

풀이 코드

마지막 점(모든 점에서의 경우 판단 + 겹치지 않는지 판단) 풀이 코드

    public static int find_max(){
        int ret = Integer.MIN_VALUE;

        for (int r1 = 0; r1 < n; r1++){
            for (int c1 = 0; c1 < m; c1++){
                for (int r2 = r1; r2 < n; r2++){
                    for (int c2 = c1; c2 < m; c2++){
                        int firSum = circulate(r1, c1, r2, c2);

                        for (int x1 = 0; x1 < n; x1++){
                            for (int y1 = 0; y1 < m; y1++){
                                for (int x2 = x1; x2 < n; x2++){
                                    for (int y2 = y1; y2 < m; y2++){
                                        if (right(r1, c1, r2, c2, x1, y1, x2, y2)){
                                            int secSum = circulate(x1, y1, x2, y2);
                                            ret = Math.max(ret, firSum + secSum);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }


        return ret;
    }

• 정말 모든 점에서 판단 r1, c1, r2, c2가 첫번째 직사각형, x1, y1, x2, y2가 두번째 직사각형의 점! -> 이 점에 속하는 값들을 더하고, 사각형이 겹치지 않는지 판단.

    public static boolean right(int r1, int c1, int r2, int c2,
                                int x1, int y1, int x2, int y2){
        if (x1 > r2 || x2 < r1 || y1 > c2 || y2 < c1)
            return true;
        return false;
    }

두 점이 겹치지 않는지 판단하는 코드

• x1 > r2 첫번째 사각형보다 두번째 사각형이 아래에 위치하는 경우
• x2 < r1 두번째 사각형이 첫번째 사각형 아래에 위치하는 경우
• y1 > c2 첫번째 사각형이 두번째 사각형의 왼쪽에 위치하는 경우
• y2 < c1 두번째 사각형이 첫번째 사각형의 왼쪽에 위치하는 경우

문제 해설 풀이와 차이점

해설에서는 겹치는 구간을 리스트로 처리하여방문한 부분을 +1 해준다. 만약 리스트 속 값이 2가 있는 경우는 겹치는 부분이 존재한다는 뜻이다.

문제 설명

n이 주어지고 n * n개의 숫자가 주어진다. 이 숫자들안에서 기울어진 직사각형으로 돌며 값을 더할 때, 최대가 되는 값을 구하라. 도는 방향은 ↗️↖️↙️↘️이다. ↙️↖️ ↘️↗️ 즉, 위 모양처럼 직사각형의 모양을 띌 수 있다.

문제 접근

• 모든 직사각형의 경우를 다 판단한다.
• 최대가 되는 값을 구하기 위해, 최대 크기의 직사각형을 구한다.

잘못된 생각

• ↖️ ↗️ 두가지 방향의 직사각형만 생각하여 구현 각각 짝수번째와 홀수번째의 길이가 1씩만 되도록 구현하여 원하는 최대 값이 나오지 않았다.

문제 풀이 코드 (사각형의 넓이를 구하는 부분)

    public static int find_sum(int i, int j){
        int ret = 0;

        for (int odd = 1; odd <= n; odd++){
            for (int even = 1; even <= n; even++){
                int sum = 0;
                boolean valid = true;

                int x = i;
                int y = j;

                // 1
                for (int k = 0; k < odd; k++){
                    x--;
                    y++;
                    if (x < 0 || y >= n){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }

                if (!valid)
                    continue;

                // 2
                for (int k = 0; k < even; k++){
                    x--;
                    y--;
                    if (x < 0 || y < 0){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }
                if (!valid)
                    continue;

                // 3
                for (int k = 0; k < odd; k++){
                    x++;
                    y--;
                    if (x >= n || y < 0){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }
                if (!valid)
                    continue;

                // 4
                for (int k = 0; k < even; k++){
                    x++;
                    y++;
                    if (x >= n || y >= n){
                        valid = false;
                        break;
                    }
                    sum += lst[x][y];
                }
                if (!valid)
                    continue;     

                ret = Math.max(sum, ret);           
            }
        }

        return ret;
    }

• for문으로 짝수번째 길이와 홀수번째 길이를 늘려가면 그때 그때의 최대 값을 갱신하였다.
• 주어진 숫자들 안에서 최대한으로 갈 수 있는 만큼 더하도록 구현하였다. (주어진 길이만큼)

문제 설명

n * n에 금이 있는데 금이 있는 부분은 1 없는 부분은 0으로 주어진다 금의 가격은 개당 m이고, 채굴 비용은 k^2 + (k + 1)^2이다. 마름모 모양으로 채굴할 수 있으며, 마름모 부분이 채굴장 밖을 벗어나도 채굴은 할 수 있으나 금은 없다.

문제 풀이 중 직면한 어려움

• 마름모를 어떻게 구현할 것인가

문제 풀이

• 좌표 내에서 기준 점에서 위치가 k만큼 떨어져 있는지 확인하여 마름모 부분을 확인

  public static int find(int i, int j, int K){
        int cnt = 0;
  
        for (int dx = -K; dx <= K; dx++) {
            for (int dy = -(K - Math.abs(dx)); dy <= (K - Math.abs(dx)); dy++) {
                int nx = i + dx;
                int ny = j + dy;
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 범위 체크
                // (nx, ny)는 K 크기의 마름모 내부에 포함됨
                if (lst[nx][ny] == 1)
                    cnt++;
            }
        }

전체 코드

import java.util.*;

public class Main {
    public static int n;
    public static int[][] lst;

    public static int find(int i, int j, int K){
        int cnt = 0;

        for (int dx = -K; dx <= K; dx++) {
            for (int dy = -(K - Math.abs(dx)); dy <= (K - Math.abs(dx)); dy++) {
                int nx = i + dx;
                int ny = j + dy;
                if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; // 범위 체크
                // (nx, ny)는 K 크기의 마름모 내부에 포함됨
                if (lst[nx][ny] == 1)
                    cnt++;
            }
        }

        return cnt;
    }

    public static int diff(int cnt, int k, int m){
        int dig = k * k + (k + 1) * (k + 1);
        int gold = cnt * m;

        if (gold - dig < 0)
            return 0;
        return gold - dig;
    }

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

        n = sc.nextInt();
        int m = sc.nextInt(); // 금 가격

        lst = new int[n][n];

        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++)
                lst[i][j] = sc.nextInt();
        }

        int max_charge = 0;
        //채굴 금액 : k^2 + (k+1)^2
        int k_max = (n + 1) / 2;

        for (int i = 0; i < n; i++) {         // 중심점 i
            for (int j = 0; j < n; j++) {     // 중심점 j
                for (int K = 0; K <= n; K++) { // 마름모 크기
                    int goldCount = find(i, j, K);
                    int cost = K*K + (K+1)*(K+1);

                    if (goldCount * m >= cost) { // 수익이 나는 경우
                        max_charge = Math.max(goldCount, max_charge);
                    }
                }
            }
        }

        System.out.print(max_charge);

    }
}

여러 개의 원소가 있고, 여러 개의 집합이 있다고 가정합시다. 특정 원소가 어떤 집합에 속해있는지 확인하고, 특정 집합을 합쳐야 할 일이 있다면 Union-Find 자료구조를 사용하면 좋습니다.

-> 트리가 있을 때, 노드에서 그 노드의 루트 노드(대표 노드)를 쉽게 알 수 있다.

문제링크

function init(size)
  set uf = [0] with size
  for i = 1 ... size
    uf[i] = i
  return uf

function find(x)
  if uf[x] == x
    return x
  return find(uf[x])

function union(x, y)
  set X = find(x), Y = find(y)
  uf[X] = Y

uf = init(6)

union(2, 3)
union(1, 4)
union(1, 5)
union(4, 2)
union(3, 1)

print(find(1))
print(find(2))
print(find(3))
print(find(4))
print(find(5))

여기서

union(2, 3)
union(1, 4)
union(1, 5)
union(4, 2)
union(3, 1)

이 부분을 해결하고 싶은 것인데

uf[] -> {1, 2, 3, 4, 5, 6} 이고

union(2, 3)
-> uf[2] = 3

union(1, 4)
-> uf[1] = 4

union(1, 5)
-> uf[4] = 5 // uf[1] = 4이기 때문에 X = 4가 된다

union(4, 2)
-> uf[5] = 3

union(3, 1)
-> uf[3] = 3 // uf[1] = 4, uf[4] = 5, uf[5] = 3

print(find(1))
-> uf[1] -> uf[4] -> uf[5] -> 3
print(find(2))
-> uf[2] -> 3
print(find(3))
-> uf[3] -> 3
print(find(4))
-> uf[4] -> uf[5] -> 3
print(find(5))
-> uf[5] -> 3

결론적으로 모든 출력이 3이 된다.

문제

1,2,3,4 를 가지고 입력된 숫자를 만드는 경우의 수 구하기 예를 들어 4의 경우 1 1 1 1 1 1 2 2 1 1 1 2 1 1 3 3 1 2 2 4

이렇게 8개를 만든다

문제풀이

package java_algo;

import java.util.*;

public class dp {

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

        int n = sc.nextInt();

        int[] dp = new int[n + 1]; // 합

        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;

        // {1, 2, 3, 4}
        for (int i = 3; i <= n; i++){
            if (i == 3)
                dp[3] = dp[2] + dp[1] + dp[0];
            else
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4];
        }
        System.out.println(dp[n]);
    }
}

설명

1,2,3,4로 암호를 만들어야하기 때문에 지금 수(i)의 총 합을 알기 위해서는 이전 i-1, i-2, i-3, i-4의 개수의 합이 필요하다. 각각에서 1,2,3,4씩 더해주면 i가 되기 때문에

완전 이진 트리의 일종으로 우선 순위 큐를 위해 만들어진 구조 최대 값, 최소 값을 쉽게 추출할 수 있다.

       7
     /  |
    5   6 
  / |  / |
 1  2  3  4

이런 모습 (완전 이진 트리)

• 최대 힙 트리나, 최소 힙 트리를 사용하여 정렬
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
• 과정 설명
  • 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다. 내림차순을 기준으로 정렬
  • 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
  • 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게 된다.

내림차순 정렬을 위한 최대 힙(max heap)의 구현

힙(heap)은 1차원 배열로 쉽게 구현될 수 있다. 정렬해야 할 n개의 요소들을 1차원 배열에 기억한 후 최대 힙 삽입을 통해 차례대로 삽입한다. 최대 힙으로 구성된 배열에서 최댓값부터 삭제한다.

최대 힙(max heap)의 삽입

힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

구현 (Java)

    public static void heapify(int[] lst, int n, int i) {
        int largest = i;         // 현재 노드
        int left = 2 * i + 1;    // 왼쪽 자식
        int right = 2 * i + 2;   // 오른쪽 자식

        // 왼쪽 자식이 더 크면 largest 갱신
        if (left < n && lst[left] > lst[largest]) {
            largest = left;
        }

        // 오른쪽 자식이 더 크면 largest 갱신
        if (right < n && lst[right] > lst[largest]) {
            largest = right;
        }

        // largest가 변경되었으면 교환 및 재귀적으로 힙화
        if (largest != i) {
            int temp = lst[i];
            lst[i] = lst[largest];
            lst[largest] = temp;

            // 재귀적으로 하위 트리를 힙화
            heapify(lst, n, largest);
        }
    }

    public static void heapSort(int[] lst) {
        int n = lst.length;

        // 힙 빌드: 최대 힙 생성
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(lst, n, i);
        }

        // 힙 정렬
        for (int i = n - 1; i > 0; i--) {
            // 루트(가장 큰 값)를 끝으로 보냄
            int temp = lst[0];
            lst[0] = lst[i];
            lst[i] = temp;

            // 나머지 힙화
            heapify(lst, i, 0);
        }
    }

주어진 수들에서 마지막 자리로 정렬하고 맨 앞자리까지 반복하여 정렬 시간 복잡도는 O(k * n) 이다.

예를들어 1 22 33 14 25 42 가 있으면 1 22 42 33 14 25로 정렬 (1의 자리) 그 뒤에 10의 자리로 정렬 1 14 22 25 33 42가 된다.

1의 자리로 정렬한 상태로 저장되기 때문에 그 다음 자리수를 기준으로 정렬될때 이미 한번 정렬된 상태(완전하지 않더라도)에서 정렬하게 된다.

구현

public static int[] radix(int[] lst, int k) {
        int n = lst.length;

        for (int i = 0; i < k; i++) {
            Queue<Integer>[] num = new LinkedList[10];
            for (int d = 0; d < 10; d++) {
                num[d] = new LinkedList<>();
            }

            // 자릿수별로 분배
            for (int j = 0; j < n; j++) {
                int digit = (lst[j] / (int) Math.pow(10, i)) % 10;
                num[digit].offer(lst[j]);
            }

            // 새로운 배열로 재구성
            int cnt = 0;
            for (int d = 0; d < 10; d++) {
                while (!num[d].isEmpty()) {
                    lst[cnt++] = num[d].poll();
                }
            }
        }

        return lst;
    }

Queue를 활용하여 구현하였다.

• 새로운 카드를 정렬되어 있는 카드 사이에 넣는 것과 비슷한 개념
• 두번째부터 시작해서 그 앞쪽 자료와 비교 했을때, 비교하려는 값이 더 작으면 그 자리에 넣고 원래 자리의 값은 뒤로 미는 것

예시

5 2 1 3 4 가 주어졌을때, 처음 비교할 값은 2

5 > 2이므로 2 5 1 3 4

그 다음 비교할 값은 1 5 > 1이므로 2 1 5 3 4 2 > 1 이므로 1 2 5 3 4

그 다음 비교할 값은 5 5 > 2 이므로 넘어감

그 다음은 3 5 > 3 1 2 3 5 4

그 다음은 4 5 > 4 1 2 3 4 5

구현

import java.util.*;

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

        int n = sc.nextInt();
        int[] lst = new int[n];

        for (int i = 0; i < n; i++)
            lst[i] = sc.nextInt();

        for (int i = 1; i < n; i++){
            int key = lst[i];
            int j = i - 1;
            while (j >= 0 && lst[j] > key){
                lst[j + 1] = lst[j];
                j--;
            }
            lst[j + 1] = key;
        }

        for (int i = 0; i < n; i++)
            System.out.print(lst[i] + " ");
    }
}

while문 속 내용이 조금 이해하기 어려웠는데 key값과 비교했을 때, key 값이 더 작으면 현재 비교 할 값을 뒤로 미뤄줘야 하니까 계속 뒤로 미뤄주는 거라고 생각,, 어차피 맨 처음의 lst[j + 1]는 key값으로 저장되어 있기 때문에 key값의 적절한 위치를 찾기 위해 key보다 작거나 같은 값이 나올때 까지 계속 그 큰 값들을 뒤로 미뤄주고 적절한 위치를 찾아 그 위치에 저장한다고 이해할 수 있다.

1. next()

• 기능
• 공백(스페이스, 탭, 줄바꿈)*을 기준으로 단어 하나를 읽습니다. 공백 이후의 입력은 남아있습니다. 사용 시점 단어 단위의 입력을 읽을 때 적합합니다.
• 특징 입력이 여러 단어로 이루어진 경우, 첫 번째 단어만 반환합니다. 입력 버퍼에 남아 있는 공백 또는 줄바꿈은 무시합니다.

  Scanner sc = new Scanner(System.in);
  System.out.println("Enter input:");
  String input = sc.next(); // "Hello World" 입력 시, input에는 "Hello"만 저장됨.
  System.out.println(input); // 출력: Hello

2. nextLine()

• 기능 한 줄 전체를 읽습니다. 줄바꿈(\n)을 기준으로 입력을 읽으며, 공백도 포함합니다.
• 사용 시점 여러 단어로 이루어진 한 줄의 입력을 읽을 때 적합합니다.
• 특징 줄바꿈 문자를 기준으로 입력을 가져오기 때문에, 이전에 남아있는 줄바꿈 문자도 읽을 수 있습니다. 입력 버퍼에 남아있는 줄바꿈을 명시적으로 처리해야 할 경우가 있습니다.

  Scanner sc = new Scanner(System.in);
  System.out.println("Enter input:");
  String input = sc.nextLine(); // "Hello World" 입력 시, input에는 "Hello World" 저장됨.
  System.out.println(input); // 출력: Hello World

차이점

1. 처리 범위의 차이

• next() 공백(스페이스, 탭, 줄바꿈)으로 구분된 단어 하나만 읽습니다. 따라서 처리 범위가 작고, 문자열 처리에 소요되는 시간이 적습니다.
• nextLine() 줄 전체를 읽으며, 공백이나 탭 등도 포함합니다. 읽어야 할 데이터의 양이 많아질 가능성이 높습니다.

2. 버퍼 처리

• next() 공백이나 줄바꿈을 기준으로 데이터를 잘라서 반환하기 때문에, 입력 버퍼에 남은 데이터는 이후 메서드에서 처리됩니다. 버퍼 관리가 간단하고 추가 작업이 적습니다.
• nextLine() 줄 전체를 읽으므로, 입력이 길어질수록 버퍼를 처리하는 시간이 더 많이 소요됩니다.

3. 사용 시 차이점

next()는 특정 단어만 처리해야 하는 간단한 작업에 적합하며, 입력 크기에 상관없이 빠르게 처리합니다. nextLine()는 줄 전체를 처리하므로, 문자열의 길이가 길거나 데이터 양이 많을수록 느려질 수 있습니다.