자료구조의 핵심은 데이터를 저장하고 꺼내기 위해 논리적으로 구조화하여 저장하는것

EX) 배열, 트리, 그래프, 큐, 스택, 리스트 자료구조를 왜 알아야 할까? 우리가 프로그래밍 하면서 발생하는 문제는 대부분 데이터에 관한 문제이다. 완벽한 자료구조는 없다. 각 자료구조의 장점과 단점을 알아야 상황에 따라 적절하게 사용할 수 있다.

📝 문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

• 0: x좌표가 증가하는 방향 (→)
• 1: y좌표가 감소하는 방향 (↑)
• 2: x좌표가 감소하는 방향 (←)
• 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

입력예제1

3 3 3 0 1 4 2 1 3 4 2 2 1

출력예제1

4

입력예제2

10 5 5 0 0 5 6 0 0 5 7 0 0 5 8 0 0 5 9 0 0 6 5 0 0 6 6 0 0 6 7 0 0 6 8 0 0 6 9 0 0

출력예제2

8

💡 Solution

1. 드래콘 커브마다 draqCurve 메소드를 통해 이동한 좌표를 알아낸다.
  1-1) 0세대 부터 g 세대 까지 좌표가 이동하는 방향을 list에 담는다.
  1-2) 처음 list에 0세대 정보는 넣어 둔다. 그 후에 1세대 부터 g세대까지 for문을 돌면서 방향을 담는다.
  1-3) 전 세대의 방향 정보를 뒤에서 부터 탐색한다. 그리고 기존 정보에 +1 을 한 값이 현재 세대의 방향 정보이다.
        방향이 4이상이 되면 안되니까 %4를 해준다.
  1-4) list에 있는 방향 정보를 바탕으로 이동된 좌표를 map에 표시한다.
2. map 을 완전탐색하여 4각형을 만들 수 있는지 확인한다.

🔑 code

import java.util.*;


public class Main {

    static boolean map[][] = new boolean[101][101];
    //우상좌하 (방향 0,1,2,3)
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,-1,0,1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0; i<n; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            int d = sc.nextInt(); // 시작 방향
            int g = sc.nextInt(); //세대
            //커브 그리기
            drawCurve(x,y,d,g);
        }
        //사각형인지 확인하기
        int answer = 0;
        for(int i=0; i<100; i++){
            for(int j=0; j<100; j++){
                if(map[i][j] && map[i][j+1] && map[i+1][j] && map[i+1][j+1]){
                    answer ++;
                }
            }
        }
        System.out.println(answer);
    }

    private static void drawCurve(int x, int y, int d, int g) {
        List<Integer> dir = new ArrayList<>();
        //첫번쨰 방향 추가하기
        dir.add(d);
        //시작점 map에 true로 바꾸기
        map[x][y] = true;
        //이미 0세대는 추가했기 때문에 1세대부터 g 세대 까지
        for(int i=1; i<=g; i++){
            for(int j = dir.size()-1; j>=0; j--){ //현재 세대 = 전세대대의 방향 + 전 세대의 방향을 뒤집은 후에 1을 더한값을 추가
                dir.add((dir.get(j)+1)%4);
            }
        }

        //커브 만들어진 좌표 map에 true로 만들기
        for(int i : dir){
            x+= dx[i];
            y+= dy[i];
            map[x][y] = true;
        }

    }



}

📝 문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

입력예제1

2 20 50 50 30 20 40

출력예제1

1

입력예제2

4 10 50 10 100 20 90 80 100 60 70 70 20 30 40 50 20 100 10

출력예제2

3

💡 Solution

• 순회하며 방문하지 않은 모든 노드를 이동할 수 없을 때까지 이동을 한다. 이동할 수 있는지 없는지는 bfs를 통해 확인한다.
• bfs로 이동가능한 구역을 찾는다. 다음으로 이동 할 노드와 현재 노드와 차이가 L이상 R이하여야 한다.
• 이동한 구역의 인구수 update를 위해 list에 이동가능한 구역을 넣어주고 그 구역의 인구 수를 total 변수에 따로 저장한다.
• 다음 이동가능한 구역을 찾기 위해 queue에 값을 넣는다.
• list에 저장된 수가 1보다 크면 이동이 가능하기 때문에 이동 가능한 지역에 사람수를 업데이트 해준 후 true를 리턴한다.
• 인구 이동이 더이상 일어날 수 없으면 몇번 이동이 발생했는지 리턴한다.

🔑 code

import java.util.*;

public class 인구이동_16234 {

    //방문한 국가인지 확인
    static boolean[][] visit;
    //땅 크기, 인구 제한 사항
    static int n,l,r;
    //인구이동하는 국가 정보
    static ArrayList<Pos> list;
    //인구수
    static int[][] population;

    public static void main(String[] args) {
        Scanner sc = new Scanner (System.in);
        n = sc.nextInt();
        l = sc.nextInt();
        r = sc.nextInt();
        //인구 수
        population = new int[n][n];

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                population[i][j] = sc.nextInt();
            }
        }
        int result = 0;
        //인구 이동이 없을 때까지 반복
        while(true){
            visit = new boolean[n][n];
            boolean move = false;
            for(int i=0; i<n ; i++){
                for( int j=0; j<n; j++){
                    if(!visit[i][j]) {

                        if(bfs(i,j)) move = true; //이동가능한 국경이 있는지 확인
                    }
                }
            }
           if(!move) break;
           result ++;
        }
        System.out.println(result);
    }

    static boolean bfs(int x, int y){
        //이동가능한 나라 리스트
        list = new ArrayList<Pos>();
        Queue<Pos> queue = new LinkedList<>();

        list.add(new Pos(x,y));
        queue.add(new Pos(x,y));
        visit[x][y] = true;

        int total = population[x][y];
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};

        while(!queue.isEmpty()){
            Pos pos = queue.poll();
            x = pos.x;
            y = pos.y;

            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<n && !visit[nx][ny]){

                    int populationDifference = Math.abs(population[nx][ny]- population[x][y]);
                    //이동할 국가의 인구 수 차이가 l보다 크고 r보다 작은지 확인
                    if(populationDifference >= l && populationDifference<=r){
                        total += population[nx][ny];
                        queue.add(new Pos(nx,ny));
                        list.add(new Pos(nx,ny));
                        visit[nx][ny] = true;
                    }
                }
            }
        }
        if(list.size() > 1) {
            int movingNum = total/list.size();
            //인구 수 변경
            for(Pos pos : list){
                int changeX = pos.x;
                int changeY = pos.y;
                population[changeX][changeY] = movingNum;
            }
            //인구이동이 가능
            return true;
        }
        //인구 인동 불가능
        return false;
    }
    static class Pos{
        int x;
        int y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

📚알고리즘 분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

📝 문제

수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다.

김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.

참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)

수강신청 대충한 게 찔리면, 선생님을 도와드리자!

입력형식

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)

이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109)

출력형식

강의실의 개수를 출력하라.

입력예제1

3 1 3 2 4 3 5

출력예제1

2

💡 Solution

하나의 수업이 끝나야 다음 수업이 들어 올 수가 있다. 아님 새로운 강의실을 추가해야한다. 수업들을 하나하나 비교하기 위해선 수업 시작 시간을 기준으로 오름차순 정렬을 한다.(시작시간이 같다면 끝나는 시간으로) 첫번째 수업 끝나는 시간을 큐에 넣은 후 두번째 수업 부터 시작시간과 큐에 있는 끝나는 시간을 비교를 한다. 두번째 수업시작이 첫번째 수업 끝나는 시간과 같거나 크면 큐에 있던 끝나는 시간을 제거한 후 두번째 수업 끝나는 시간을 넣는다. 즉 강의실을 새로 열지 않고 이어서 수업한다는 의미이다. 만약 작다면 새로운 강의실을 열어야 하기때문에 큐에 추가를 한다. 종료 시각이 가장 빠른 수업의 종료 시간과 비교해야하기때문에 우선순위 큐를 사용한다. 요약하면, 배정되지 않은 수업의 시작시간과 우선순위 큐안에서 종료 시각이 가장 빠른 수업의 종료 시간과 비교하는 것이다.

🔑 code

package 백준;

import java.util.*;

public class 강의실배정_11000 {

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

        for(int i=0; i<n; i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        //1. 수업 시작 시간을 기준으로 정렬을 한다.
        Arrays.sort(arr,new Comparator<int[]>(){
           public int compare(int[] o1, int[] o2){
               if(o1[0] == o2[0]) return o1[1] - o2[1];
               return o1[0] - o2[0];
           }
        });
        // 2. 우선순위 큐에 첫번째 수업의 끝나는 시간을 저장한다.
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(arr[0][1]);

        // 3. 두번째 수업시간부터 배열을 돌며 비교한다.
        for(int i=1; i<n; i++){
            //시작하는 시간이 우선순위 큐에 있는 끝나는 시간보다 같거나 크면 우선순위 큐에 있는 끝나는 시간을 제거한다.(새로운 강의실 열필요 없음)
            if(arr[i][0] >= queue.peek()) queue.poll();
            // 현재 수업의 끝나는 시간을 우선순위 큐에 넣는다.
            queue.add(arr[i][1]);
        }
        //우선순위 큐에 남아있는 수가 필요한 강의실 수다.
        System.out.println(queue.size());

    }
}

📚알고리즘 분류

그리디 알고리즘, 정렬, 우선순위 큐

📝 문제

대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.

현지도 이러한 머신 러닝용 클러스터를 관리하는 역할을 맡고 있다. 클러스터의 성능은 컴퓨터의 수가 많아질 수록, 각각의 성능이 올라갈 수록 향상된다. 그런데 어느 날 협업 중인 몇몇 연구실에서 클러스터의 성능을 업그레이드해 달라는 요청을 보내 왔다. 이들은 특히 클러스터를 이루는 각각의 컴퓨터 중 성능이 가장 낮은 컴퓨터의 성능이 병목이 된다고 알려 왔다.

이 클러스터에는 N대의 컴퓨터가 있으며, 각각의 성능은 a_i라는 정수로 평가할 수 있다. 현지는 각각의 컴퓨터에 비용을 들여 업그레이드를 진행할 수 있다. 성능을 d만큼 향상시키는 데에 드는 비용은 d²원이다. (단, d는 자연수이다.)

업그레이드를 하지 않는 컴퓨터가 있어도 되지만, 한 컴퓨터에 두 번 이상 업그레이드를 수행할 수는 없다.

업그레이드를 위한 예산이 B원 책정되어 있다. 현지의 목표는 B원 이하의 총 비용으로 업그레이드를 수행하여, 성능이 가장 낮은 컴퓨터의 성능을 최대화하는 것이 목표이다. 이 최선의 최저성능을 계산하는 프로그램을 작성하시오.

제약조건

1≤ N ≤ 10⁵인 정수

1≤ a_i ≤10¹⁰인 정수

1≤ B ≤10¹⁸인 정수

입력형식

첫째 줄에 컴퓨터의 수와 예산을 나타내는 정수 N과 B가 공백을 사이에 두고 주어진다. 둘째 줄에 각 컴퓨터의 성능을 나타내는 N개의 정수 a₁, a₂, ..., a_n이 공백을 사이에 두고 주어진다.

B의 범위가 매우 넓어, 사용하는 프로그래밍 언어에 따라 64비트 정수형을 사용해야 할 수 있음에 유의하시오.

출력형식

첫째 줄에 예산을 효율적으로 사용했을 때, 성능이 가장 낮은 컴퓨터의 성능으로 가능한 최댓값을 출력하시오.

입력예제1

4 10 5 5 6 1

출력예제1

4 네 번째 컴퓨터의 성능을 1에서 4로 업그레이드 하는 데 드는 비용은 32=9원이다. 이 경우, 가장 낮은 성능의 컴퓨터는 4의 성능을 가지게 되며, 가장 낮은 성능으로 가능한 최대값은 4가 됨을 알 수 있다.

입력예제2

10 10 5 3 9 8 4 3 1 8 6 3

출력예제2

3 일곱 번째 컴퓨터의 성능을 1에서 3으로 업그레이드 하는 데 드는 비용은 22=4원이다. 이 경우, 가장 낮은 성능의 컴퓨터는 3의 성능을 가지게 된다.

가장 낮은 성능이 4가 되기 위해서는 원래 3의 성능을 가지고 있었던 두 번째, 여섯 번째, 그리고 열 번째 컴퓨터를 향상시키는 데 드는 비용 12+12+12=3원과 일곱 번째 컴퓨터의 성능을 3이 아닌 4로 향상시키는 데 드는 비용 (4-1)2=9원, 총 12원이 들기 때문에 불가능하다.

입력예제3

10 10000000 10 2 2 9 6 1 8 3 1 9

출력예제3

1005

💡 Solution

입력이 커서 모든 경우의 수를 따져서 풀면 안되고 이진 탐색으로 접근해야 하는 문제.

1. 성능이 가장 낮은 컴퓨터의 가능한 성능 범위는 컴퓨터 성능들의 최솟값 ~ 컴퓨터 성능들의 최댓값 + 예산 B의 제곱근
2. 성능 범위를 이진 탐색으로 해서 가장 낮은 컴퓨터의 최대 성능을 찾자. <예산 내에서 업그레이드 할 수 있는지 확인> 2-1. 기준 값 ( 가장 낮은 컴퓨터 성능이라고 가정하는) - 원래 컴퓨터 성능 > 0 이면 두개 뺀 값 만큼 성능을 올려줘야 함 2-2. 그리고 cost(성능 증가 시켰을 때 드는 비용)에 두개 뺀 값의 제곱을 더해 준다. 2-3. cost가 예산 보다 커지면 false(right를 mid -1) 아니면 true (left를 mid+1) true 일땐 answer에 가장 낮은 성능 값 업데이트

✔ 참고자료

🔑 code

import java.util.Arrays;
import java.util.Scanner;

public class 슈퍼컴퓨터클러스터 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();  // 컴퓨터 수 1≤N≤10^5인 정수
        long b = sc.nextLong(); // 예산 1≤B≤10^18인 정수

        long[] computer = new long[n];

        for(int i=0; i<n; i++){
            computer[i] = sc.nextLong(); //컴퓨터 성능 ai 1≤N≤10^9인 정수
        }

        Arrays.sort(computer);
        // 제일 성능이 낮은 컴퓨터의 성능 최소, 최대값
        long min = computer[0];
        long max = computer[n-1] + (long)Math.sqrt(b);

        long answer = 0;

        //이분 탐색으로 제일 낮은 성능 컴퓨터 찾기
        while( min <= max){
            long mid = (min + max)/2;
            if(check(computer, mid, b)){ //예산을 더 키워도 된다
                min = mid +1;
                answer = mid;
            }else{
                max = mid -1 ;
            }
        }

        System.out.println(answer);

    }

    private static boolean check(long[] computer, long mid, long b) {
        long cost = 0;
        for(int i=0; i < computer.length ; i++){
            cost += mid - computer[i] > 0 ? Math.pow(mid-computer[i],2) : 0; // 성능 최소 값 - 지금 성능
            if(cost > b) return false;
        }
        return true;
    }
}

📚알고리즘 분류

이진 탐색

📝 문제

동호는 종이를 접는데 옆에서 보고 접으려고 한다. 옆에서 본다는 말은 아래 그림과 같이 본다는 뜻이다. 동호는 종이를 반으로 접을 때, 아래와 같이 두가지중 하나로만 접을 수 있다.

1. 오른쪽 반을 반시계 방향으로 접어서 왼쪽 반의 위로 접는다.
2. 오른쪽 반을 시계 방향으로 접어서 왼쪽 반의 아래로 접는다.

아래의 그림은 위의 설명을 그림으로 옮긴 것이다.

한 번의 종이 접기가 끝났을 때, 동호는 종이 접기를 원하는 만큼 더 할 수 있다. 종이 접기를 한번 접을 때 마다 두께는 2배가 되고 길이는 절반이 될 것이다.

종이 접기를 여러 번 했을 때 (안접을 수도 있다), 동호는 종이를 다시 피기로 했다. 그러고 나서 다시 접고 이렇게 놀고 있었다. 옆에서 보고 있던 원룡이는 동호를 위해 종이를 접어서 주기로 했다.(원룡이는 동호의 규칙대로 접지 않는다.) 동호는 그리고 나서 원룡이가 접었다 핀 종이를 다시 동호의 규칙대로 접을 수 있는지 궁금해졌다.

위의 저 종이를 접었다 피면 다음과 같은 그림처럼 펴진다.

종이가 시계방향으로 꺽여있으면 OUT이고, 반시계방향으로 꺾여있으면 IN이다.

종이가 접혀있는 정보가 왼쪽부터 오른쪽까지 차례대로 주어졌을 때, 이 종이를 동호의 규칙대로 접을 수 있는지 없는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1은 위의 그림에서 OUT을 의미하고 0은 위의 그림에서 IN을 의미한다. 예를 들어, 위의 그림과 같은 모양은 100으로 나타낼 수 있다. 문자열의 길이는 3000보다 작으며, 항상 2^N-1꼴이다. (N ≥ 1)

출력

T개의 줄에 차례대로 각각의 종이를 동호의 방법대로 다시 접을 수 있으면 YES를, 접을 수 없으면 NO를 출력한다.

💡 Solution

분할정복으로 푸는 문제이다. 문자를 반씩 쪼개며 접히는 종이인지 확인한다. 접히는 종이인지 확인 하는 방법은 들어온 값에서 가운데 글자를 기준으로 대칭인 글자가 서로 달라야 한다. (대칭인 부분 합이 1이 되어야 한다.)

🔑 code

package 백준;


import java.util.Scanner;

public class 종이접기_1802 {
    static boolean result;

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

        int t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            result = true;
            String input = sc.next();
            check(input);

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

        }
    }
    private static void check(String input) {
        //길이가 1이거나 이미 result가 false 이면 return
        if (!result) return;
        if(input.length() == 1) return;

        char[] fold = input.toCharArray();
        int mid = fold.length / 2;
        int left = mid - 1;
        int right = mid + 1;

        while (left >= 0) {
            if (fold[left] != fold[right]) {
                left -= 1;
                right += 1;
            } else {
                result = false;
                return;
            }
        }
        //분할 정복
        check(input.substring(0, mid));
        check(input.substring(mid + 1));

    }
}

📚알고리즘 분류

애드 혹, 분할정복

📝 문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

💡 Solution

• 5의 배수 마다 0의 개수가 1씩 늘어나는데 n제곱근의 경우 n씩 늘어난다.
• 팩토리얼을 계산 할 때 계산되는 값dl 5의 배수일 경우 그 값에 포함된 5의 배수의 지수만큼 더해진다.

🔑 code

import java.util.Scanner;

public class Main {

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

        for (int i = 1; i <= n; i++) {
            int temp = i;
            while (temp % 5 == 0) { //5의 배수이면 0이 하나씩 증가 n제곱근이면 n 만큼 수 추가
                answer++;
                temp /= 5;
            }
        }
        System.out.println(answer);
    }
}

📚알고리즘 분류

임의 정밀도 / 큰 수 연산(arbitrary_precision), 수학(math)

📝 문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N², 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

💡 Solution

❗ 조심할 점

• 최단 거리가 같은 손님이 두명이면 손님의 x좌표로 비교해 작은거!! 그것도 같으면 y좌표 비교

• 손님을 태울수 없는 경우, 연료가 없을 경우 -1 출력 단, 목적지에 왔을때 연료가 0인건 괜찮

• 손님카운트를 뺄때 리스트에서도 손님을 제거해줘야함

• 손님위치와 도착지점을 class로 만듬

• 손님수만큼 택시 이동하기(메소드 만들기)

• 택시에서 최단거리인 손님 찾기(bfs 사용) -> 손님 찾았는데 연료가 없음 -1 출력, 택시 위치 변경

• 손님 태우고 목적지까지 최단 거리 찾기(bfs 사용) -> 목적지 도착했는데 연료가 음수면 -1 출력, 아니면 연료 2배

🔑 code

package Baekjoon;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Guest{
    int nowx;
    int nowy;
    int arrivex;
    int arrivey;

    public Guest(int nowx, int nowy, int arrivex, int arrivey) {
        super();
        this.nowx = nowx;
        this.nowy = nowy;
        this.arrivex = arrivex;
        this.arrivey = arrivey;
    }


}
public class 스타트택시_19238 {
    static int n,m,fuel;
    static int[][] road;
    static int taxix,taxiy;
    static ArrayList<Guest> guest;

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

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

        taxix = sc.nextInt()-1; //taxi x 위치
        taxiy = sc.nextInt()-1; //taxi x 위치

        //guest 위치와 목표 지점 저장 배열
        guest = new ArrayList<>();

        //guest 위치와 목표 지점 배열에 추가하기
        for(int i=0; i<m;i++) { 
            int startx = sc.nextInt()-1;
            int starty = sc.nextInt()-1;
            int endx = sc.nextInt()-1;
            int endy = sc.nextInt()-1;
            guest.add(new Guest(startx,starty,endx,endy));
        }

        //손님 수 만큼 택시 이동
        int firstguestnum = m; //나중엔 guest 수가 바뀜
        for(int i=0; i<firstguestnum;i++) {
            findGuest();            

        }

        System.out.println(fuel);

    }
    private static void findGuest() {

        int shortest = Integer.MAX_VALUE; //최단거리
        int shorttestguestidx = -1;          //최단거리일떄 인덱스

        for(int i=0; i<m;i++) {
            int nowx = guest.get(i).nowx; //게스트 x위치
            int nowy = guest.get(i).nowy; //게스트 y위치

            int starttoguest = bfs(nowx,nowy); //택시 ~ i 손님까지 최단 거리
            if(starttoguest == -1) { //손님을 이동할 수 없는 경우
                System.out.println(-1);
                System.exit(0);
            }
            if(shortest >=starttoguest){ //현재 손님의 최단 거리가 가장 짧을떄
                if(shortest == starttoguest) { //만약 같으면
                    if(guest.get(shorttestguestidx).nowx <guest.get(i).nowx) {//기존에 있던 최단거리의 행이 더 작으면 continue
                        continue;
                    }else if (guest.get(shorttestguestidx).nowx == guest.get(i).nowx) {//두개 같으면 열까지 비교
                        if(guest.get(shorttestguestidx).nowy < guest.get(i).nowy) {
                            continue;
                        }
                    }
                }
                shortest = starttoguest; //최단 거리 갱신
                shorttestguestidx = i;   //인덱스 갱신
            }
        }
        int tempx = guest.get(shorttestguestidx).nowx; //최단 거리 손님의 x
        int tempy = guest.get(shorttestguestidx).nowy; //최단 거리 손님의 y
        int arrivex = guest.get(shorttestguestidx).arrivex; //최단 거리 손님 도착 지점 x
        int arrivey = guest.get(shorttestguestidx).arrivey; //최단 거리 손님 도착 지점 y

        //택시 위치 변경
        taxix = tempx;
        taxiy = tempy;
        fuel -= shortest; //연료 뺴기
        if(fuel<0) { //사람은 남아있는데 연료가 없으면 
            System.out.println(-1);
            System.exit(0);
        }
        //guest태우고 목적지로 가기
        int guesttoarrive = bfs(arrivex,arrivey);
        taxix = arrivex;
        taxiy = arrivey;
        fuel-=guesttoarrive; //최단 거리 뺴기
        if(fuel<0) {
            System.out.println(-1);
            System.exit(0);
        }
        m-=1; //손님 한명 빼기
        guest.remove(shorttestguestidx);//값도 지우기
        fuel+= guesttoarrive*2; //연료 2배


    }

    private static int bfs(int nowx, int nowy) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {taxix,taxiy,0});
        int[] dx = {1,-1,0,0};
        int[] dy = {0,0,1,-1};
        boolean[][] check = new boolean[n][n];
        check[taxix][taxiy] = true;

        while(!queue.isEmpty()) {
            int[] nowPosition = queue.poll();
            int nx = nowPosition[0];
            int ny = nowPosition[1];
            int cnt = nowPosition[2];

            if(nx==nowx &&ny== nowy) return cnt;
            for(int i=0; i<4;i++) {
                int nextx = nx+dx[i];
                int nexty = ny+dy[i];
                if(nextx>=0 && nextx<n && nexty>=0 && nexty<n && !check[nextx][nexty] && road[nextx][nexty]!= 1) {
                    check[nextx][nexty] = true;
                    queue.add(new int[] {nextx,nexty,cnt+1});
                }
            }
        }
        return -1;
    }

}

📚알고리즘 분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 구현(implementation), 시뮬레이션(simulation)

📝 문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

💡 Solution

• 이미 밟은 계단은 dp 배열에 넣는다.
• 첫번째 계단과 두번째 계단은 값 채워 넣기 dp[1], dp[2]
• bottom up 방식으로 풀었다.
• 계단 올라올 수 있는 경우의 수 2가지 1) 전전칸 밟고 오기(-2) 2)전전전칸 밟고, 전칸 밟고 오기(-3,-1)

  dp[i] = Math.max(dp[i - 3] + floor[i - 1], dp[i - 2]) + floor[i];

전전칸과 전칸 밟고 올라오는 경우 -> dp[i - 3] + floor[i - 1] 전칸은 dp 값이 아닌 계단 값으로 계산해줘야한다. 만약 dp[i-1] 값으로 했을 경우 dp[i-1]에 전칸과 전전칸 밟은 합이 저장 될 수 있다. 그러면 전전전칸, 전전칸, 전칸을 연속으로 밟는것이 되기 때문에 조건에 성립되지 않는다.

🔑 code

package Baekjoon;

import java.util.Scanner;

public class 계단오르기_2579 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] dp = new int[n + 1];
        int[] floor = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            floor[i] = sc.nextInt();
        }

        // dp의 1,2칸 채우기
        dp[1] = floor[1];

        if (n >= 2) {// n이 1일 수도 있으니
            dp[2] = floor[1] + floor[2];
        }

        // 계단 올라올 수 있는 경우의 수 2가지
        // 1. 전전칸 밟고 오기 (-2칸)
        // 2. 전전전칸 밟고, 전칸 밟고 오기(-3칸, -1칸)
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 3] + floor[i - 1], dp[i - 2]) + floor[i]; // 올라올 수 있는 경우의 수 2가지 중 큰 값 + 현재 값
        }

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

    }

}

📗 Plus

Top down 방식인 재귀를 사용할 수 있다.

static int find(int N) {

    if(dp[N] == null) {
        dp[N] = Math.max(find(N - 2), find(N - 3) + arr[N - 1]) + arr[N];
    }

    return dp[N];
}

📚알고리즘 분류

다이나믹 프로그래밍(dp)