선장 일지

• 코드

코드 설명 :

만약 입력에 5 3 가 주어졌다고 가정하면 우리는 이를 0+5, 1+4, 2+3, 3+2, 4+1, 5+0로나눌수있다.

0(2번 더해서 0이 되는 경우)+5(1번 더해서 5가 되는 경우)

1(2번 더해서 1이 되는 경우)+4(1번 더해서 4가 되는 경우)

2(2번 더해서 2이 되는 경우)+3(1번 더해서 3가 되는 경우)

3(2번 더해서 3이 되는 경우)+2(1번 더해서 2가 되는 경우)

4(2번 더해서 4이 되는 경우)+1(1번 더해서 1가 되는 경우)

5(2번 더해서 5이 되는 경우)+0(1번 더해서 0가 되는 경우)

즉, DP[2][5] = DP[1][0] + DP[1][1] + DP[1][2] + DP[1][3] + DP[1][4] + DP[1][5] 가 된다. 

K와 N으로 바꾸면 DP[K][N] = DP[K-1][0] + DP[K-1][1] + … + DP[K-1][N] 임을 알 수 있다.

풀어서 표로 확인해보면

표를 토대로 좀 더 간단하게 점화식을 세우면 DP[K][N] = DP[K][N-1] + DP[K-1][N-1]라는 것을 유추할 수 있다.

정답 코드 : 나온 DP[K][N] = DP[K][N-1] + DP[K-1][N-1] 식을 사용하여 구현 하였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());

		int[][] dp = new int[201][201];
		
		for(int i=1;i<=K;i++) {
			dp[i][0]=1;
		}
		for(int i=1;i<=K;i++) {
			for(int j=1;j<=N;j++) {
				dp[i][j] = dp[i][j-1] + dp[i-1][j];
			}
		}
		System.out.println(dp[K][N]%1000000000);
		
	}

}

• 코드

정답 코드 : 기존 LCS 길이구하는 알고리즘 + dp배열을 통해 최장길이 문자열도 가져왔다. 문자열은 거꾸로가면서 같으면 추가해준 뒤 --, dp배열의 수가 x-1이 현재위치보다 값이 낮으면 x--, y-1이 현재위치보다 값이 낮으면 y--를 해주면서 반복문을 돌린다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String firstInput = br.readLine();
		String secondInput = br.readLine();

		int[][] dp = new int[firstInput.length() + 1][secondInput.length() + 1];

		for (int i = 1; i <= firstInput.length(); i++) { 
			for (int j = 1; j <= secondInput.length(); j++) { 
				if (firstInput.charAt(i - 1) == secondInput.charAt(j - 1)) { 
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else { 
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);				
				}
			}
		}
		
		int x = firstInput.length();
		int y = secondInput.length();
		StringBuilder sb = new StringBuilder();
		while(x != 0 && y != 0) {
			if(firstInput.charAt(x-1) == secondInput.charAt(y-1)) {
				sb.append(firstInput.charAt(x-1));
				x--;
				y--;
			}
			else if(dp[x][y] == dp[x-1][y])
				x--;
			else if(dp[x][y] == dp[x][y-1]) 
				y--;
		}
		

		System.out.println(dp[firstInput.length()][secondInput.length()]);
		System.out.print(sb.reverse().toString());

	}
}

• 코드

정답 코드 : LIS 알고리즘(가장 긴 증가하는 부분 수열을 구할 때 사용한 알고리즘 DP)을 통해 가장 긴 증가하는 부분수열의 수를 찾은다음 총 N-증가하는 부분수열의 수 => 줄세우는 최단 교체 수

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

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 [] array = new int[N];
        int [] dp = new int[N];
        
        for (int i = 0; i < N; i++) 
            array[i] = Integer.parseInt(br.readLine());
        
        int max = 1;
        for (int i = 0; i < N; i++) {
        	if (dp[i] == 0) 
        		dp[i] = 1;
        	for (int j = 0; j < i; j++) {
        		if (array[i] > array[j]) 
        			dp[i] = Math.max(dp[i], dp[j]+1);
        	}
            if(max<dp[i])
            	max=dp[i];
        }

        System.out.println(N-max);
    }
        
}

• 코드

정답 코드 : 어디 순서에 있던지 상관없기 때문에 기둥의 높이만큼의 index에 +1 해주면서 개수만 체크해준다. down, up 배열과 downTotal, upTotal 배열로 합을 누적해줌.

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

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

        int[] down = new int[H];
        int[] up = new int[H];

        for(int i = 0;i<N;i+=2){
            down[Integer.parseInt(br.readLine()) - 1]++;
            up[Integer.parseInt(br.readLine()) - 1]++;
        }

        int[] downTotal = new int[H];
        int[] upTotal = new int[H];

        downTotal[H - 1] = down[H - 1];
        upTotal[0] = up[H - 1];

        for (int i = H - 2; i >= 0; i--) {
        	downTotal[i] = downTotal[i + 1] + down[i];
        }
        for (int i = 1; i < H; i++) {
        	upTotal[i] = upTotal[i - 1] + up[H - i - 1];        
        }

        int min = 1000000000;
        for (int i = 0; i < H; i++) {
            if(min >= downTotal[i] + upTotal[i])
            	min = downTotal[i] + upTotal[i];
        }
        int count = 0;

        for (int i = 0; i < H; i++) {
            if (min == downTotal[i] + upTotal[i]) count++;
        }

        System.out.println(min+" "+count);
    }
        
}

• 코드

정답 코드 : bfs로 구현하였고, priorityqueue를 이용하면 알아서 오름차순으로 출력해준다는 걸 알았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
    static int[][] array;
    static boolean[][] check;
    static int N;
    static int[] x = {-1,1,0,0};
    static int[] y = {0,0,-1,1};
    static PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

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

        N = Integer.parseInt(br.readLine());

        array = new int[N][N];
        check = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                array[i][j] = s.charAt(j) - '0';
            }
        }

        for(int i = 0; i < N; i++) {
        	for(int j = 0; j < N; j++) {
        		if(!check[i][j] && array[i][j] == 1) {
        			bfs(i,j);
        		}
        	}
        }
        
        System.out.println(priorityQueue.size());
        while (!priorityQueue.isEmpty())
            System.out.println(priorityQueue.poll());
    }

    public static void bfs(int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i,j});
        
        int count = 0;
        while(!queue.isEmpty()){
            int location[] = queue.poll();            	

            for(int direction = 0; direction<4; direction++){
                int r = location[0] + x[direction];
                int c = location[1] + y[direction];
                
                if(r >= 0 && c >= 0 && r < N && c < N){
                    if(array[r][c] == 1 && !check[r][c]){
                        queue.offer(new int[] {r,c});
                        check[r][c] = true;
                        count++;
                    }
                }
            }
        }
        if(count == 0)
        	priorityQueue.offer(1);
        else
        	priorityQueue.offer(count);
    }
}

• 코드

정답 코드 : 100,000개의 배열을 만들어 n+1, n-1, n*2 번째 체크, 체크하다가 N과 K가 같아지면 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int N;
    private static int K; 
    private static int[] Check;
 
    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());
        K = Integer.parseInt(st.nextToken());
        Check = new int[100001];
        bfs();
        System.out.println(Check[K]);
    }
    private static void bfs(){
        Queue<Integer> queue = new LinkedList<>();
 
        queue.offer(N);
 
        while (!queue.isEmpty()){
            int n = queue.poll();
            if(n==K) break;
            if(n > 0 && Check[n-1] ==0){
                queue.offer(n-1);
                Check[n-1] = Check[n]+1;
            }
            if(n<100000 && Check[n+1]==0){
                queue.offer(n+1);
                Check[n+1] = Check[n] +1;
            }
            if(n*2<=100000 && Check[n*2]==0){
                queue.offer(n*2);
                Check[n*2] = Check[n] +1;
            }
        }
    }
}
 

• 코드

정답 코드 : bfs를 이용하여 방문자가 없으면 해당 위치의 하위 연결 요소를 다 방문하고 result를 +1 해줘서 첫째줄의 연결된 개수를 찾아준다.

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

public class Algorithm {
	static int [][] graph;
	static boolean[] check;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
		graph = new int[1001][1001];
		check = new boolean[1001];
		
		for (int i = 0; i < b; i++) {
			st = new StringTokenizer(br.readLine());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			graph[c][d] = graph[d][c] = 1;
		}
		
		int result = 0;
		
		for(int i = 1; i <= a; i++) {
			if(check[i] == false) {
				bfs(a, i);
				result++;
			}
		}
		
		System.out.print(result);
	}

	public static void bfs(int a, int index) {
		if(check[index] == true)
			return;
		else {
			check[index] = true;
			for(int i = 1; i <= a; i++) {
				if(graph[index][i] == 1)
					bfs(a, i);
			}
		}
	}
}

• 코드

정답 코드 : 동영상을 보면서 DFS와 BFS를 공부했다. 대체적으로 DFS는 스택이나 재귀, BFS는 큐를 이용하여 푼다고하여서 dfs는 재귀, bfs는 큐를 이용하여 풀었다.

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

public class Main {
	static ArrayList<Integer>[] array;
	static boolean[] check;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		array = (ArrayList<Integer>[]) new ArrayList[a + 1];
		for (int i = 1; i <= a; i++) {
			array[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < b; i++) {
			st = new StringTokenizer(br.readLine());
			int c = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			array[c].add(d);
			array[d].add(c);
		}
		for (int i = 1; i <= a; i++) {
			Collections.sort(array[i]);
		}
		check = new boolean[a + 1];
		dfs(start);
		System.out.println();
		check = new boolean[a + 1];
		bfs(start);
	}

	public static void dfs(int x) {
		if (check[x]) {
			return;
		}
		check[x] = true;
		System.out.print(x + " ");
		for (int y : array[x]) {
			if (check[y] == false) {
				dfs(y);
			}
		}
	}

	public static void bfs(int start) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(start);
		check[start] = true;
		StringBuilder sb = new StringBuilder();
		while (!queue.isEmpty()) {
			int x = queue.remove();
			sb.append(x + " ");
			for (int y : array[x]) {
				if (check[y] == false) {
					check[y] = true;
					queue.add(y);
				}
			}
		}
		System.out.print(sb);
	}
}