선장 일지

• 코드

정답 코드 : 동영상을 보면서 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;
    }
}

• 코드

정답 코드 : 기존 연속합 문제에서 다른 점은 최소값 수 하나를 제거할 수 있다는 점! 그래서 기존 연속합 코드에서 DP하나를 더 추가해 최소값을 하나 제외했을 때의 최대값도 유지시켜 주었다.

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

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

	    System.out.println(max);
    }
}

• 코드

정답 코드 : 처음 P의 길이만큼 넣고 같지않을때 같을때까지의 문자열의 길이 -1을 빼줘서 copy개수를 맞춤. 그 다음 i가 p의길이만큼 됐을때가 처리가 안되서 추가시켜주엇다.

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 S = br.readLine();
		String P = br.readLine();
		
		String temp="";
		int count=P.length();
		
		for(int i=0;i<P.length();i++) {
			temp+=P.charAt(i);
			if(i==P.length()-1 && S.contains(temp))
				count-=temp.length()-1;
			if(!S.contains(temp)) {
				if(temp.length()>2)
					count-=temp.length()-2;
				temp=P.charAt(i)+"";
			}
		}
		System.out.println(count);
	}
}

• 코드

실패 코드 : factorial구해주는 것만 메소드를 만들어서 구해준 뒤 이항계수를 계산해 % 1000000007로 나머지 출력해주었다. 결론은 런타임에러....

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
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());
		long N = Integer.parseInt(st.nextToken());
		long K = Integer.parseInt(st.nextToken());
		
		System.out.print((int)(Factorial(N)/(Factorial(K)*Factorial(N-K))% 1000000007));
	}
	
	private static long Factorial(long number) {
	    long factorialNumber = 1;
	    for(int i=2;i<=number;i++)
	    	factorialNumber = factorialNumber*i;
	    return factorialNumber;
	}
}

• 코드

정답 코드 : 이분 탐색을 통해 푼 코드이다. 자세한 설명은 밑에

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

public class Main {
	private static long N;
	private static long k;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Long.parseLong(br.readLine());
		k = Long.parseLong(br.readLine());
		
        long left = 1, right = k;
        long printValue = 0;
        
        // 이분 탐색 수행
        while (left <= right) {
            long mid = (left + right) / 2;
            long cnt = 0;
            
            // mid보다 작거나 같은 수는 몇 개인지 계산.
            for (int i = 1; i <= N; i++) {
                cnt += Math.min(mid/i, N);
            }
 
            if (cnt < k) {
                left = mid + 1;
            } else {
            	printValue = mid;
                right = mid - 1;
            }
        }
		
		System.out.print(printValue);
	}
}

• 설명

만약, N이 3이라 할때 A배열이다. B 배열은 (1,2,2,3,3,4,6,6,9)순서가 될 것이다.

예를들어, 4가 B배열의 몇번째 인지 찾는다고 볼때 0번째 열은 4이하가 3개, 1열은 2개, 2열은 1개이다.

총 개수는 6개이고  실제로 4는 6번째 오는 수 였습니다.

이 부분에서

count = Math.min(mid/i,N)  (i는 i번째 열을 의미)

즉, 이 식을 세운 순간부터 우리가 할 일은 1가지로 줄어들게 됩니다.

left = 1, right = K로 두고, left <= right일 때까지 while문을 진행하면서 위 식에 따라서 cnt를 계산한 후, cnt와 K를 비교하면서 left 혹은 right를 초기화하는 것입니다.

• 코드

정답 코드 : 기존 N과 M (11)의 코드에서 StringBuilder에 추가하는 곳에서 오름차순의 형태의 수만 추가해줄 수 있게 boolean을 만들어주었다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	private static int list[];
	private static int listvalue[];
	private static int n, m;
	private static StringBuilder sb;

	private static void dfs(int cnt) {
		if (cnt == m) {
			boolean check = true;
			for (int i = 1; i < m; i++) {
				if(list[i-1]>list[i])
					check = false;
			}
			if(check) {
				for (int i = 0; i < m; i++) {
					sb.append(list[i]).append(" ");
				}
				sb.append("\n");
			}
			return;
		}

		int saveValue=-1;
		for (int i = 1; i <= n; i++) {
			if (saveValue==listvalue[i-1])
				continue;
			list[cnt] = listvalue[i - 1];
			saveValue = listvalue[i - 1];
			dfs(cnt + 1);
		}
	}

	public static void main(String[] args) throws IOException {
		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());

		list = new int[9];
		listvalue = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++)
			listvalue[i] = Integer.parseInt(st.nextToken());
		sb = new StringBuilder();
		Arrays.sort(listvalue);

		dfs(0);

		bw.write(sb.toString());

		bw.close();
		br.close();
	}

}