선장 일지

• 코드

정답 코드 : 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);
	}
}

• 코드

정답 코드 : 문제만 보면 초기값만 다른 피보나치 문제란걸 알 수 있다. 첫 번째 수를 first 두번째 수를 second 라고 하면 일차 방정식이 세워진다.

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 d = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		int[][] array = new int[30][2];
		array[0][0] = array[1][1] = 1;
		array[0][1] = array[1][0] = 0;
		
		for(int i=2; i<array.length; i++) {
			array[i][0] = array[i-1][0] + array[i-2][0];
			array[i][1] = array[i-1][1] + array[i-2][1];
		}
		
		int x = array[d-1][0];
		int y = array[d-1][1];
		int second = k/y;
		int first = 0;
		boolean check = false;
		
		while(!check) {
			first = k - (second * y);
			if(first%x==0) {
				first /= x;
				check = true;
			}else {
				second--;
			}
		}
		
		System.out.println(first);
		System.out.println(second);
		
	}

}

• 코드

정답 코드 : 계속해서 증가하는 부분수열을 찾는 것이 LIS 같아서 LIS 알고리즘을 활용하여 구현하였다.

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));
        String s;
        
        while((s=br.readLine())!=null) {
        	s = s.trim();		//이걸 안해주면 runtime이 뜬다. 질문 검색에서 알려줘서 이렇게 했는데 잘모르겠음.
            int n = Integer.parseInt(s);
            int[] array = new int[n+1];
            int[] LIS = new int[n+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=1;i<=n;i++) {
                array[i] = Integer.parseInt(st.nextToken());
            }
            LIS[0] = array[0];
            int count = 0;
            for(int i=1;i<=n;i++) {
                int idx = binary(LIS, 1,count+1,array[i]);
                LIS[idx] = array[i];
                if(idx == count+1) count++;
            }
            System.out.println(count);
        }
    }
    private static int binary(int[] LIS, int startIndex,int endIndex,int key) {
        while(startIndex<endIndex) {
            int mid = (startIndex+endIndex) /2;
            if(LIS[mid]<key) startIndex = mid + 1;
            else endIndex = mid;
        }
        return endIndex;
    }
}