<stdio.han>

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

[정답코드]

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

public class Main {
    static int[][] graph;
    static boolean[][] visited;
    static int[][] result;
    static int n, m;
    static int[] dx = {-1, 1, 0, 0}; // 상,하,좌,우
    static int[] dy = {0, 0, -1, 1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        graph = new int[n][m];
        visited = new boolean[n][m];
        result = new int[n][m];
        int x=0, y=0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 2) {
                    x = i;
                    y = j;
                } else if (graph[i][j] == 0) {
                    visited[i][j] = true;
                }
            }
        }
        bfs(x, y);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                    result[i][j] = -1;
                }
                System.out.print(result[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && graph[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        result[nx][ny] = result[tmp[0]][tmp[1]] + 1;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }
    }
}

[설명]

bfs를 활용해야하는 문제이다. 시작지점의 위치를 입력받고 입력받은 위치를 큐에 넣고 bfs로직을 돌려준다.

bfs로직은 입력받은 x, y 를 큐에 넣고  해당 위치를 기준으로 4방탐색을 한다. 4방탐색을 했을 때 방문하지않은장소이고, 갈 수 있는 장소이고, 지도 내에 있다면 visited를 true로 변경해주고, 새로 탐색한 위치의 값을 이동할 때 마다 1씩 증가시켜준다. 그리고 새로탐색한 위치를 큐에 넣어준다.

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int X = Integer.parseInt(st.nextToken());
        int Y = Integer.parseInt(st.nextToken());
        int Z = (int) ((long) Y * 100 / X);
        int answer = -1;
        int left = 0;
        int right = (int) 1e9; // 범위는 문제에서 주어짐
        while (left <= right) { // left가 right를 넘어서면 종료
            int mid = (left + right) / 2;
            int newRate = (int) ((long) (Y + mid) * 100 / (X + mid));
            if (newRate != Z) {
                answer = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(answer);
    }
}

[설명]

이 문제는 이분탐색 문제이다. 처음에 이 문제를 풀 때 오른쪽 끝 범위를 몇으로 정해야 하는지 몰라 잠깐 막혔는데 문제에서 X의 범위는 10억이라고 정해줬다. 간단하게 알고리즘을 설명하자면

1. 범위내의 중간 값 mid 를 초기화해주고 X 외 Y 에 각각 mid를 더했을 때의 승률을 새로 구해준다.

2 - 1. 승률이 변했다면 횟수를 더 줄여야 하기 때문에 right = mid - 1 을 해준다.

2 - 2. 승률이 안변했다면 횟수를 더 늘여야 하기 때문에 left = mid + 1 을 해준다.

생각보다 간단한데 막상 아이디어가 떠오르지 않는다.

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

[시간초과가 발생한 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        // ArrayList에 값을 담아줌
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            if (list.contains(Integer.parseInt(st.nextToken()))) { // list.contains() 함수를 사용
                bw.write("1");
            } else {
                bw.write("0");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

[정답코드]

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

public class Main {
    public static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 이분탐색은 반드시 정렬이 되어야만 한다.
        Arrays.sort(arr);

        int M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            if (binarySearch(Integer.parseInt(st.nextToken())) >= 0) {
                bw.write("1");
            } else {
                bw.write("0");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static int binarySearch(int key) {
        int low = 0; // 탐색 범위의 왼쪽 끝 인덱스
        int high = arr.length - 1; // 탐색 범위의 오른쪽 끝 인덱스

        // low 가 high 보다 커지면 종료
        while (low <= high) {
            int mid = (low + high) / 2; // 찾는 범위의 중간 값

            if (key < arr[mid]) { // key 가 중간값보다 작을 경우
                high = mid - 1;
            } else if (key > arr[mid]) { // key 가 중간값보다 클 경우
                low = mid + 1;
            } else { // key 가 중간값과 같을 경우
                return mid;
            }
        }
        // 끝까지 탐색했지만 값이 존재하지 않을 경우
        return -1;
    }
}

[설명]

이 문제는 이분 탐색을 활용하면 풀 수 있는문제다. 하지만 처음에 봤을때 간단하게 보여서 list.contains() 메서드를 활용하면 풀릴것같아서 시도해보았다. 결과는 시간초과가 발생했다. 

contains 메서드의 설명을 보면 알 수 있듯이 contains 메서드도 결국에는 리스트의 처음부터 끝까지 탐색하기 때문에 내가 직접 반복문을 시행하나 메서드를 활용하나 별 차이가 없기 때문에 시간초과가 발생했다.

그래서 이분탐색을 활용해 다시 정답을 구해냈다. 코드는 간단해서 설명할것이 없을것 같고 나는 시간복잡도가 궁금해 자료를 검색해봤다.

이러한 일반적인 이분탐색은 거의 대다수가 O(logN) 의 시간 복잡도를 가진다.

N개의 요소를 가진 리스트를 K번 반복한다는 함수를 구한다면 다음과 같다.

운이 좋아 1번만에 찾는다면 (1/2)*N 가 될것이고 3번만에 찾는다면 (1/2)*(1/2)*(1/2)*N 이 될것이다.

운이 안좋아 최악의 경우로  마지막 탐색범위가 1인 경우가 있을수도있다. K번 반복 했을 때 쪼개진 크기가 1이라고 가정한다면, 결국  K번 반복한다고했으니 이를 다음과같이 풀어볼 수 있다.

결국 시간복잡도는 O(logN) 이 되는것이다.

원래 내가 작성했던 코드는 간단히 보자면 이중for문이 되는것이기 때문에 시간복잡도는 O(N^2) 혹은 O(NM)이 된다.

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

[정답 코드]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()); // 지방의 수
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine(), " "); // 각 지방의 예산요청
        int left = 0;
        int right = -1; // 예산의 최대 금액
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            right = Math.max(right, arr[i]);
        }
        int M = Integer.parseInt(br.readLine()); // 총 예산
        while (left <= right) {
            int mid = (left + right) / 2;
            long budget = 0;
            for (int i = 0; i < N; i++) {
                budget += Math.min(arr[i], mid);
            }
            if (budget <= M) {
                left = mid + 1;
            } else {
                right = mid -1;
            }
        }
        System.out.println(right);
    }
}

[설명]

이 문제는 이분탐색, 매개변수 탐색(파라매트릭 서치)을 활용하는 문제이다. 그 중에 매개변수 탐색을 활용했다. 나는 이분탐색, 매개변수 탐색문제를 풀어본적이없어서 어떻게 접근해야할지 막막해 다른사람이 작성한 글을 참고했다.

매개변수탐색은 주어진 범위 내에서 원하는 값 또는 조건에 일치하는 값을 찾아내는 알고리즘이다.

범위는 left 와right로 왼쪽 끝 값과 오른쪽 끝 값을 설정하고 그 범위의 중간값을 계속 찾아내며 조건을 찾아내는 방법이다.

문제를 예로들면 문제의 정답은 127인데 해당 조건을 향해 left 와 right 값을 조정해 나아가는것이다. 처음 left 값은 0 right 값은 150으므로 mid는 75이다. 

반복문을 1회 더 시행하면

이런식으로 left 76, mid 113, right 150 이다. 1회 더 실시하면

left 114, mid 132, right 150 이다.

이런식으로 mid가 해당조건을 넘어서지 못하면 left를 mid + 1로 변경하고 해당조건을 넘어가버리면 right를 mid -1로 설정해나아가면 범위를 좁히는 것이다. 이 문제에서 중요한 점은 해당 지방마다 예산의 한도가 정해져 있기때문에 각 지방의 예산 한도를 넘어서지 않게 주의해야한다. 아래 코드처럼 mid가 해당 지방의 예산보다 작을경우에는 mid를 budget에 추가해주고 지방의 예산을 넘어설 경우에는 해당 지방의 최대예산을 추가해준다.

            for (int i = 0; i < N; i++) {
                budget += Math.min(arr[i], mid);
            }

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

[정답 코드]

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

public class Main {
    static int[][] houses;
    static int[][] cost;
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

        // 초기값 세팅
        cost[0][0] = houses[0][0];
        cost[0][1] = houses[0][1];
        cost[0][2] = houses[0][2];

        System.out.println(Math.min(Math.min(dp(N-1,0), dp(N-1,1)), dp(N-1,2)));
    }

    // 로직
    public static int dp(int N, int color) {
        if (cost[N][color] == 0) {
            if (color == 0) {
                return cost[N][color] = Math.min(dp(N-1, 1), dp(N-1, 2)) + houses[N][color];
            }
            if (color == 1) {
                return cost[N][color] = Math.min(dp(N-1, 0), dp(N-1, 2)) + houses[N][color];
            }
            if (color == 2) {
                return cost[N][color] = Math.min(dp(N-1, 0), dp(N-1, 1)) + houses[N][color];
            }
        }
        return cost[N][color];
    }
}

[설명]

저번 DP문제에서 설명했듯이 DP 문제는 3가지 방법을 따라야 한다.

1. 테이블 정의

2. 점화식 찾기

3. 초기값 정하기

1. 테이블 정의하기

dp[N] = N일째 집일 때 집을 칠하는 최소 비용

2. 점화식 찾기

cost [N][Red] = Math.min(dp[N-1][Green], dp[N-1][Blue]) + houses[N][Red]

cost [N][Green] = Math.min(dp[N-1][Red], dp[N-1][Blue]) + houses[N][Green]

cost [N][Blue] = Math.min(dp[N-1][Red], dp[N-1][Green]) + houses[N][Blue]

Math.min(Math.min(dp[N-1][Red], dp[N-1][Green]), dp[N-1][Blue])

3. 초기값 세팅

cost[0][0] = houses[0][0];
cost[0][1] = houses[0][1];
cost[0][2] = houses[0][2];

나머지는 코드와 같다.

나는 스스로 테이블정의, 점화식찾기, 초기값 세팅을 처음으로 스스로 구해냈다! 하지만 여기까지였다. 그 다음 코드로 구현하는 부분에서 막혀버려서 구글링을해 코드를 구현했다.

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

[시행 착오]

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        String basket = "0";
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[j][moves[i] - 1] != 0){
                    int tmp = board[j][moves[i] - 1];
                    board[j][moves[i] - 1] = 0;
                    if(basket.substring(basket.length()-1).equals(Integer.toString(tmp))){
                        answer+=2;
                        basket = basket.substring(0,basket.length()-1);
                        break;
                    } else {
                        basket += (String.valueOf(tmp));
                    }
                    break;
                }
            }
        }
        return answer;
    }
}

[정답 코드]

import java.util.*;

class Solution {
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0;i<moves.length;i++){
            for(int j=0;j<board.length;j++){
                if(board[j][moves[i]-1] != 0){
                    if(!stack.empty() && stack.peek() == board[j][moves[i]-1]){
                        answer+=2;
                        stack.pop();
                            board[j][moves[i]-1]=0;
                        break;
                    } else {
                        stack.push(board[j][moves[i]-1]);
                        board[j][moves[i]-1]=0;
                        break;
                    }
                } 
            }
        }     
        return answer;
    }
}

[설명]

이 문제는 시물레이션 문제로 보기에는 어려워 보이지만 생각보다 쉬운 문제라고 생각한다.

아이디어는 크레인이 인형을 뽑을 때마다 해당 위치에 가장 위에 쌓여있는 인형을 뽑은 후 해당 위치를 0 으로 변경해준다.

뽑은 인형은 stack에 담고, stack.peek() 함수를 사용해 stack의 가장 최근 숫자를 확인 후 뽑은 인형과 같다면 stack.pop()을 해 스택에서 제거해준다.

이론은 간단한데 처음에 틀렸던 이유는 스택을 사용하면 쉬운데 스택이 순간 생각나지 않아서 문자열로 풀다가 문제 일부분만 맞았었다. 문자열의 마지막숫자와 뽑은 인형을 비교해 나가는 로직이였는데 안되는 이유는 문제에서 인형의 번호가 0~100 까지 존재해 문자열의 마지막숫자로 비교하면 틀리게 되는것이였다. 

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

[시행 착오]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        if (N <= 3) {
            System.out.println(1);
        } else if (N % 3 == 0) {
            System.out.println(N / 3);
        } else if (N % 3 == 1 && N % 2 == 0) {
            System.out.println((N / 3));
        } else if (N % 3 == 1){
            System.out.println((N / 3) + 1);
        } else if (N % 2 == 0) {
            System.out.println(N / 2);
        } else {
            System.out.println((N / 3) + 1);
        }
    }
}

[정답 코드]

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int[] dp = new int[N + 1];
        dp[0] = dp[1] = 0;

        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + 1; // 1을 뺀값
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1); // 1을 뺀값과 2로 나눈값준 최솟값
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1); // (1을 뺀 값과 2로 나눈 값중 최솟값) 과 3으로 나눈값중 최솟값
            }
        }
        System.out.println(dp[N]);
    }
}

[설명]

이 문제는 DP 문제이다.

DP 문제는 3가지 단계를 생가해야 된다고 한다.

1. 테이블 정의

2. 점화식 찾기

3. 초기값 정하기

1. 테이블 정의

dp[i] = i를 1로 만들때 연산을 해야하는 횟수의 최솟값

2. 점화식 찾기

dp[12] 을 예로들자면

3으로 나누거나 (dp[12] = dp[4] + 1) = (dp[i] = dp[i/3] + 1)

2로 나누거나 (dp[12] = dp[6] + 1) = (dp[i] = dp[i/2] + 1)

1을 빼거나 (dp[12] = dp[11] + 1) = dp[i] = dp[i-1] + 1)

-> dp[12] = min(dp[4] + 1, dp[6] + 1, dp[11] + 1)

-> dp[i] = min(dp[i/3] + 1, dp[i/2] + 1, dp[i-1] + 1)

3. 초기값 정하기

dp[0] = dp[1] = 0

사실 이 모든 아이디어는 내 아이디어가 아니다. dp 문제는 가장 자신없어 하는 분야이기도하고 점화식을 계산하는법을 도저히 떠올릴수가 없다ㅠㅠ. 그래서 어느 한 블로그를 참고했다. 내가 푼 문제라고 볼 수 없다.

참고 : 

https://velog.io/@kimmjieun/%EB%B0%B1%EC%A4%80-1463%EB%B2%88-1%EB%A1%9C-%EB%A7%8C%EB%93%A4%EA%B8%B0-Java-%EC%9E%90%EB%B0%94

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

[정답 코드1]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int count = 0;
        while (N > 0) {
            if (N % 5 == 0) { // N이 5로 나눠질수 있을 경우 5로 나눠버린 후 출력
                count += N / 5; // 5로 나눈 몫을 count 에 더함
                System.out.println(count);
                return;
            }
            if (N < 3) {
                System.out.println("-1"); // N이 3보다 적을 경우에는 -1
                return;
            }
            N-=3; // N이 5로 안나눠질 경우에는 3kg 짜리 하나를 만듬
            count++;
        }
        System.out.println(count);
    }
}

[설명]

처음에 작성했던 코드이다. 정말 단순하게 N이 5로 나눠질 때 까지 3씩 빼면서 count 를 늘렸다. 풀고나서 다른사람들이 작성했던 코드를 봤을때 깜짝놀랐었다. 이렇게 단순하게 푸는게 아닌 수학적인 방법을 사용하면 코드도 더 간결하고 쉽게 풀 수 있엇다.

[정답 코드 2]

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());

        if (N == 4 || N == 7) { // N이 4이거나 7일 경우에는 3이나 5로 나눌수 없다.
            System.out.println(-1);
        } else if (N % 5 == 0) { // N이 5로 바로 나눠질 경우
            System.out.println(N / 5);
        } else if (N % 5 == 1 || N % 5 == 3) { // N이 6, 8, 11, 13, 16 등일 경우
            System.out.println((N / 5) + 1);
        } else if (N % 5 == 2 || N % 5 == 4) { // N이 9, 12, 14, 17, 19 등일 경우
            System.out.println((N / 5) + 2);
        }
    }
}

[설명]

다른 사람이 작성한 글을 보며 대단하다고 생각했다. 조건문이 4개가 있는데 먼저

N이 4 또는 7일 경우에는 3kg 포대와 5kg 포대를 아무리 사용해도 나눠지지 않기 때문에 "-1" 을 출력해준다.

혹은 N이 5로 나눠질 경우에는 N/5 를 출력해준다.

혹은 N이 6, 8, 11, 13, 16 등 N%5 의 값이 1 또는 3일 경우 (N / 5) + 1 을 출력해준다.

혹은 N이 9, 12, 14, 17, 19 등 N%5의 값이 2 또는 4 일 경우 (N / 5) + 2 를 출력해준다.

자세한 설명은 참고한 블로그를 링크로 달아놓겠다.

참고한 블로그 : 

https://st-lab.tistory.com/72