CodingTest - Baekjoon

1. 기본 자료구조 및 알고리즘 : 230307 ~

1) 배열 : 11720번

230307
문제 : 숫자의 합 구하기

1) parseInt() 메소드를 사용하여 Java에서 char 배열을 int로 변환할 수 있습니다.

이 메서드는 String 객체를 가져와 정수 값을 반환합니다.
이 메서드는 Integer 클래스에 속하므로 정수로 변환하는 데 사용할 수 있습니다.

2) parseInt() 메소드와 valueOf() 메소드를 사용하여 Java에서 char 배열을 int로 변환할 수 있습니다.

parseInt() 메서드는 valueOf() 메서드가 반환하는 String 객체를 가져와 정수 값을 반환합니다.
이 메서드는 Integer 클래스에 속하므로 정수로 변환하는 데 사용할 수 있습니다.

package com.wogjs0911.codetest;

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

public class Day1TestArray11720_230307 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 11720번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		String sNum = br.readLine();
		
		char[] cNum = sNum.toCharArray();
		
		int sum = 0;
		
		for(int i=0; i<N; i++) 
			sum += Integer.parseInt(String.valueOf(cNum[i]));	
			// char 배열을 정수를 만드는 방법이 sum += cNum[i] - ’0’;도 가능하다!
		
		
		System.out.println(sum);
	 
	}

}

2-1) 배열 : 1546_1

230307
1546번 중간 과정

package com.wogjs0911.codetest;

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

public class Day1TestArray1546_1_230307 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1546번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		
		int n = Integer.parseInt(br.readLine());
		int sum = 0;
		
		for(int i=0; i<n; i++) {

			StringTokenizer st = new StringTokenizer(br.readLine());	// split 
			int s =Integer.parseInt(st.nextToken());
			
			for(int j=0; j<s; j++) {
				int data = Integer.parseInt(st.nextToken());
				sb.append(data).append('\n');
			}
			
//			for(int j=0; j<n; j++) {
//				sum += s; 
//				sb.append(sum).append('\n');
//			
//			}

		}
	
		System.out.println(sb);
	}

}

2-2) 구간 합 1 : 1546_2번

230308
구간 합, 이차 배열

문제 : 평균 구하기

출력문 : StringBuilder sb = new StringBuilder();
split 역할 : StringTokenizer st = new StringTokenizer(br.readLine());
- split 역할이고 구분인자도 넣을 수 있다. 기본 구분인자는 “ “이다.

package com.wogjs0911.codetest;

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

public class Day1TestArray1546_2_230308 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1546번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		
		int n = Integer.parseInt(br.readLine());
		int sum = 0;
		int[] s1 = new int[n];
		float avg = 0;
		int max = 0;
		
		StringTokenizer st = new StringTokenizer(br.readLine());	
		// split 역할이고 구분인자도 넣을 수 있다. 기본 구분인자는 " "이다.
		
		for(int i=0; i<n; i++) {
			int s = Integer.parseInt(st.nextToken()); 
			s1[i] = s;
		}
		
		 
		for(int i=0; i<s1.length; i++) {
			if(s1[i]>max)
				max = s1[i];
				
			sum += s1[i]; 
		}
		avg = sum*100/ max/n;
		sb.append(avg);
		System.out.println(avg);
	}

}

3-1) 구간 합 1 : 11659_1번

230308

package com.wogjs0911.codetest;

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

public class Day1TestArray11659_1_230308 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 11659번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
//		int index1 = 0; 
//		int index2 = 0;
		StringTokenizer st1 = new StringTokenizer(br.readLine());	// 5 3
		
		int num1 = Integer.parseInt(st1.nextToken());	// 5 
		int num2 = Integer.parseInt(st1.nextToken());	// 3 
		
		long[] count = new long[num1];
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());	// 5 4 3 2 1
		
		// 5 4 3 2 1 받을 때 처리 
		for(int i=0; i < num1; i++) {	
			count[i] = Integer.parseInt(st2.nextToken());	// 5 4 3 2 1 
			
		}
				
		
		// index를 토큰으로 입력받기 
		// 이렇게하는게 아니라 index를 받아서 점화식 이용하기!
		// 합 배열 : s[i] = s[i-1] + A[i] -> A가 원래 배열, S가 합 배열(S[0]은 '0'이다. ) 
		// 구간 합 : i~j 구간 = s[j] - s[i-1]
		for(int j=0; j<num2; j++) {
			StringTokenizer st3 = new StringTokenizer(br.readLine());	// index
			int sum = 0;
			int index1 = Integer.parseInt(st3.nextToken());
			int index2 = Integer.parseInt(st3.nextToken()); 
			
			for(int k=index1-1; k<index2; k++) {
				sum += count[k];
			}
			
			sb.append(sum).append('\n');
			
			
		}
		System.out.println(sb);
		//}

	}
}

3-2) 구간 합 1 : 11659_2번

230308
문제 : 구간 합 구하기

합 배열 : s[i] = s[i-1] + A[i] -> A가 원래 배열, S가 합 배열(S[0]은 ‘0’이다. )
구간 합 : i~j 구간 = s[j] - s[i-1]

package com.wogjs0911.codetest;

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

public class Day1TestArray11659_2_230308 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 11660번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		StringTokenizer st1 = new StringTokenizer(br.readLine());	// 5 3
		
		int num1 = Integer.parseInt(st1.nextToken());	// 5 
		int num2 = Integer.parseInt(st1.nextToken());	// 3 
		
		long[] count = new long[num1];
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());	// 5 4 3 2 1
		
		// 5 4 3 2 1 받을 때 처리 
		for(int i=0; i < num1; i++) {	
			count[i] = Integer.parseInt(st2.nextToken());	// 5 4 3 2 1 
		}
				
		// index를 토큰으로 입력받기 
		// 이렇게하는게 아니라 index를 받아서 점화식 이용하기!
		// 합 배열 : s[i] = s[i-1] + A[i] -> A가 원래 배열, S가 합 배열(S[0]은 '0'이다. ) 
		// 구간 합 : i~j 구간 = s[j] - s[i-1]
		for(int j=0; j<num2; j++) {
			StringTokenizer st3 = new StringTokenizer(br.readLine());	// index
			int sum = 0;
			int index1 = Integer.parseInt(st3.nextToken());
			int index2 = Integer.parseInt(st3.nextToken()); 
			
			for(int k=index1-1; k<index2; k++) {
				sum += count[k];
			}
			
			sb.append(sum).append('\n');	
			
		}
		System.out.println(sb);

	}
}

4) 구간 합 2 : 11660번

230308

문제 : 구간 합 구하기 2

package com.wogjs0911.codetest;

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

public class Day1TestArray11660_1_230308 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 11660번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());	// 5 3
		
		int num1 = Integer.parseInt(st1.nextToken());	// 4 
		int num2 = Integer.parseInt(st1.nextToken());	// 3 
		
		int[][] S = new int[num1+1][num1+1];
		int[][] A = new int[num1+1][num1+1];

		
		// 크기별 배열의 원소 매핑 
		for(int k=1; k<num1; k++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());	
			
			for(int i=1; i<num1; i++) {
				A[k][i] = Integer.parseInt(st2.nextToken());
			}
		}
		
		// 구간합 생성
		// 2차원 배열 구간합 생각해보기!!
		for(int k=1; k<num1; k++) {
			
			// 여기서 또 st를 생성해서 초기화 안해도 된다!!
			// StringTokenizer st2 = new StringTokenizer(br.readLine());	
			for(int i=1; i<num1; i++) {
				S[k][i] = S[k][i-1]-S[k-1][i-1] +S[k-1][i]+A[k][i];
			}
		}
			
		// 질의별 좌표 && 2차원 배열의 구간별 합
		for(int j=0; j<num2; j++) {
			StringTokenizer st3 = new StringTokenizer(br.readLine());	
			int x1 = Integer.parseInt(st3.nextToken());
			int y1 = Integer.parseInt(st3.nextToken());
			int x2 = Integer.parseInt(st3.nextToken());
			int y2 = Integer.parseInt(st3.nextToken());
			int sum = S[x2][y2] - S[x2][y1-1] + S[x1-1][y1-1]- S[x1-1][y2];
			sb.append(sum).append('\n');	
		}	
		System.out.println(sb);
//		
//		
//		
//		StringTokenizer st2 = new StringTokenizer(br.readLine());	// 5 4 3 2 1
//		
//		// 합 배열 처리
//		for(int i=1; i < num1+1; i++) {	
//			S[i] = S[i-1] + Integer.parseInt(st2.nextToken());	
//		}
//			
//		// index를 토큰으로 입력받기 
//		// 이렇게하는게 아니라 index를 받아서 점화식 이용하기!
//		// 합 배열 : s[i] = s[i-1] + A[i] -> A가 원래 배열, S가 합 배열(S[0]은 '0'이다. ) 
//		// 구간 합 : i~j 구간 = s[j] - s[i-1]
//		for(int j=0; j<num2; j++) {
//			StringTokenizer st3 = new StringTokenizer(br.readLine());	// index
//			int sum = 0;
//			int index1 = Integer.parseInt(st3.nextToken());
//			int index2 = Integer.parseInt(st3.nextToken()); 
//			
//			sum += S[index2] - S[index1-1];
//			
//		}
		

	}
}

5) 구간 합 3 : 10986번

230309
구간합
문제 : 나머지 합 구하기

package com.wogjs0911.codetest;

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

public class Day1TestArray10986_1_230309 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 10986번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());	// 5 3
		
		int num1 = Integer.parseInt(st1.nextToken());	// 5
		int num2 = Integer.parseInt(st1.nextToken());	// 3 
	
		int[] A = new int[num1+1];	// 기본 배열
		int[] S = new int[num1+1];	// 합 배열 
		int[] C = new int[num2];	// 같은 나머지의 인덱스를 카운트하는 배열
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());	
		// 1 2 3 1 2	// 1 3 6 7 9	// 1 0 0 1 0 
		
		// 기본 배열 매핑 
		for(int i=1; i<num1; i++) {
			A[i] = Integer.parseInt(st2.nextToken());
		}
		
		// 합 배열의 원소 매핑 
		for(int i=1; i<num1; i++) {			
				S[i] = S[i-1]+ A[i];
		}
		
		// 변수 주의!! 생각해보기!!
		int remain = 0;
		int answer = 0;
		
		// 나머지가 같은 수 별로 count 더하기
		for(int j=0; j<num1; j++) {
			remain = S[j]%num2;
			
			if(remain == 0) {
				C[remain]++;
				answer++;
			}
			else if(remain == 1) {
				C[remain]++;
			}
		}	
		
		// 2개를 뽑는 모든 경우의 수 : 순열/조합에서 조합 공식(Combination)
		for(int j=0; j<num2; j++) {
			answer += (C[j]*(C[j] -1 ) / 2);
		}	
		
		sb.append(answer).append('\n');	
		System.out.println(sb);

	}
}

6) 투포인터 1 : 2018변

230309

문제 : 연속된 자연수의 합 구하기
- 문제 접근법 : 2개의 포인터로 알고리즘의 시간복잡도를 최적화한다.

중요 : 이 문제는 입력 값이 1개라서 start와 end의 위치가 같아서 생각을 더 해보기.. 뒷 문제와 비교할 것.

ex) 어떠한자연수 N은 몇 개의 연속된 자연수의 합 문제

package com.wogjs0911.codetest;

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

public class Day1TestArray2018_1_230309 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 2018번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		// StringTokenizer st1 = new StringTokenizer(br.readLine());	// 15
		
		int num1 = Integer.parseInt(br.readLine());	// 15
		
		int count = 1;
		int sum = 1;
		int start = 1;
		int end = 1;
		
		while(end != num1 ) {
			if(sum == num1) {
				count++;
				end++;
				sum = sum + end;
			}
			
			// sum 값을 변동시키고 인자 변동 
			else if(sum>num1) {
				sum = sum-start;
				start++;
			}
			else if(sum< num1) {
				sum=sum+end;
				end++;
			}
		}
		
		sb.append(count).append('\n');	
		System.out.println(sb);

	}
}

7) 투포인터 2 : 1940변**

230309
문제 : 주몽의 명령

중요 : 이 문제는 입력 값이 여러 개라서 start와 end의 위치가 같지 않고 완전 반대 방향 양끝에 있다.
- 생각을 더 해보기.. 앞 문제와 비교할 것.

번호의 합이 M보다 크므로 큰 번호 index를 내린다.
번호의 합이 M보다 작으므로 작은 번호 index를 올린다.
번호의 합이 M이랑 같으면, 앙쪽 포인터를 모두 이동시키고(서로 멀어지게) count를 증가시킨다.

package com.wogjs0911.codetest;

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

public class Day1TestArray1940_1_230309 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1940번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int num1 = Integer.parseInt(br.readLine());	// 6
		int num2 = Integer.parseInt(br.readLine());	// 9 
		
		int[] A = new int[num1];
		StringTokenizer st = new StringTokenizer(br.readLine());	// 2 7 4 1 5 3
		
		// 기본 배열 매핑 
		for(int i=1; i<num1; i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		// 정렬 중요!!
		Arrays.sort(A);
		
		
		int start =0;
		int end = num1-1;
		int count =0;
		
		// 이런 식으로도 풀 수 있다.
		while(start < end) {
			if(A[start]+A[end] < num2) {
				start++;
				
			}
			else if(A[start]+A[end] > num2) {
				end--;
			}
			else {
				count++;
				start++;
				end--;
			}
		}
		
		sb.append(count).append('\n');	
		System.out.println(sb);

	}
}

2. 응용 알고리즘 문제 : 230315 ~

1) 그리디 문제1 : 11047번

230315
동전 개수의 최솟값 구하기

package com.wogjs0911.codetest;

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

public class TestGreedy11047_1_230315 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
	// 11047번
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	
	
	
	StringTokenizer st1 = new StringTokenizer(br.readLine());	// 5 3
	
	int num1 = Integer.parseInt(st1.nextToken());	// 10
	int num2 = Integer.parseInt(st1.nextToken());	// 4200 
	
	
	int[] A = new int[num1];
	int count = 0;
	
	for(int i=0; i<num1; i++) {
		// 10개 입력
		A[i] = Integer.parseInt(br.readLine());
	
	}
	
	for(int i=num1-1; i>=0; i--) {
		// 10개 입력
		// 여기 조건식 중요!! 생각 다시!! 
		if(A[i] <= num2) {	
			count += num2 / A[i];
			num2 = num2 % A[i];
		}
	}
	
	sb.append(count);
	
	System.out.println(sb);
	
	}
}

2) DFS 문제1 : 11724번

230315
문제 : 연결 요소의 개수 구하기
연결 요소나 간선이라고 하면 DFS 이용하기!

문제 잘 읽기
- 문제의 변수 범위 주의

DFS 개념 다시 생각
- 로직 : 그 노드에 방문 했는지 안했는지 체크
- 방문 배열이 없다면 무한 루프에 빠지며, 완전 탐색을 위해 사용한다.

package com.wogjs0911.codetest;

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

public class TestDFS11724_1_230315 {
	
	// 선언 중요! 
	static ArrayList<Integer>[] A;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		// 11724번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st1.nextToken()); 
		int m = Integer.parseInt(st1.nextToken());
		
		// 초기화 : 노드의 개수로 배열 초기화! 
		// 왜 n+1개 일까? 문제에서 노드의 개수가 1개부터 시작하라고 했기 때문이다.
		A = new ArrayList[n+1];	
		visited = new boolean[n+1];
		
		// ArrayList에 초기화하기 
		// 왜 1부터 시작? 위의 배열을 (n+1)개로 초기화해서 
		for(int i=1; i < n+1; i++) {
			A[i] = new ArrayList<Integer>();
		}
		
		for(int i=0; i < m; i++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			int num1 = Integer.parseInt(st2.nextToken()); 
			int num2 = Integer.parseInt(st2.nextToken());
			
			// 노드와 에지의 관계라서 List를 이용해서 인접 값을 add로 저장만 할 것 
			A[num1].add(num2);
			A[num2].add(num1);
		}
		
		int count = 0;
		
		// 한 번도 방문을 안 했으면, count 해줄 것 
		// visited 배열의 원소 개수 주의!!
		for(int i=1; i < n+1; i++) {
			if(!visited[i]) {
				count++;
				DFS(i);
			}
		}
		
		sb.append(count);
		System.out.println(sb);
	}
	
	// 방문하는 것을 체크해주는 DFS!! 중요!!
	private static void DFS(int v) {
		
		// 한 번이라도 방문했으면 return; 위의 코드와 상반된다.
		if(visited[v])
			return;
		
		// 처음으로 False 였다면, true로 바꿔 주기 !! 
		visited[v] = true;
		
		// 그래도 false라면 DFS 다시 실행!! true 될때까지 무한 반복 
 		for(int i : A[v]) {
			if(visited[i] == false)
			DFS(i);
		}
		
	}

}

3) BFS 문제1 : 1260번

230318
문제 : DFS와 BFS 프로그램

ArrayList라서 정렬하는 방법을 Collections의 sort 메서드 이용!
Queue 자료형 쓰는 방법(LinkedList으로 설계된 Queue이다.)
나머지 위치 방문하는 방법 중요!!

문제 접근 법 :
- 빅 - O 표기법에서 입력값을 모두 곱했을 때, 1억개 이하라서 1초 이하가 걸린다. 따라서, 시간 복잡도 NlogN이하의 알고리즘을 사용할 수 있다. 여기서는 Collections 객체 이용
- 기존 11659번 문제의 경우에는 10만개 * 10만개의 입력값 때문에 시간복잡도 1이하의 알고리즘을 이용해야만 했다. 그래서 구간합 배열을 이용했다.
- 연결 요소나 간선이라고 하면 DFS 이용하기!
- 방문 배열이 없다면 무한 루프에 빠지며, 완전 탐색을 위해 사용한다.

package com.wogjs0911.codetest;

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

public class TestDFS1260_1_230318 {
	
	static ArrayList<Integer>[] A;
	static boolean visited[];
	
	public static void main(String[] args) throws IOException {
		// 1260번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st1.nextToken()); // 노드 개수
		int m = Integer.parseInt(st1.nextToken()); // 에지 개수
		int start = Integer.parseInt(st1.nextToken()); // 시작점
		
		A = new ArrayList[n+1];
		
		for(int i=1; i<n+1; i++) {
			A[i] = new ArrayList<Integer>();	
			// List라서 총 3단계로 나누어 초기화(전역변수로 선언, 개수설정, 타입설정)
		}
		
		for(int i=0; i<m; i++) {
			
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			
			int s = Integer.parseInt(st2.nextToken()); // 노드 
			int e = Integer.parseInt(st2.nextToken()); // 에지
			
			A[s].add(e);	// 서로 연결(데이터 저장하는 것)
			A[e].add(s);
		}
		
		// 이게 아니라 그냥 ArrayList가 Collections이라서
		// Collections의 정렬 메서드 이용!!! 엄청 편하다.
		for(int i=1; i<n+1; i++) {
//			if(A[i] > A[i+1]) {
//				ArrayList<Integer> temp = A[i];
//				A[i] = A[i+1];
//				A[i+1] = temp;
//			}
			Collections.sort(A[i]);
		}
		
		visited = new boolean[n+1];
		
		DFS(start);	// 문제가 순서 출력이라서 여기서 다 끝내야 한다.
		
		System.out.println();
		
		visited = new boolean[n+1];
		
		BFS(start);		
		
	}


	private static void DFS(int d) {
		
		// 결과값이 순서 출력이라서 바로 출력하기!!
		System.out.print(d + " ");
		
		visited[d] = true;
		
		// false이면 true가 될 때까지 반복 
		// 위에서 출력되어서 start 위치 빼고 완전 탐색(나머지 위치 방문)
		for(int i : A[d]) {
			if(visited[i] == false)
				DFS(i);	// 재귀함수로서 여기서 출력을 다 끝내야 한다.
		}
	}
	
	private static void BFS(int b) {
		
		// b는 BFS하는 탐색의 시작값이다. 
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(b);
		
		visited[b] = true;
		
		while(!queue.isEmpty()) {
			
			// queue의 poll이 stack에서 pop과 같다.
			int result = queue.poll();
			System.out.print(result + " ");
			
			// 여기서 for-each문 중요!! 
			// 위에서 poll되어서 start 위치 빼고 완전 탐색(나머지 위치 방문)
			for(int i : A[b]) {
				if(!visited[i]) {
					visited[i] = true;
					queue.add(i);
				}
			}
		}
	}

}

4) 이진 탐색 1 : 1920번

230318
문제 : 원하는 정수 찾기
이번에는 Collections가 아니라 Array이라서 Arrays로 정렬!!
나는 미리 배열의 값으로 바꿔서 비교하는 것이 편하다.
이진 탐색 로직 거의 암기하기!!

package com.wogjs0911.codetest;

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

public class Test2BS1920_1_230318 {
	
	public static void main(String[] args) throws IOException {
		// 1920번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int num1 = Integer.parseInt(br.readLine());
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		int[] arr = new int[num1];
		int select = 0;
		
		
		for(int i =0; i < num1; i++) {
			arr[i] = Integer.parseInt(st1.nextToken()); 
		}
		
		// 이번에는 Collections가 아니라 Array이라서 Arrays로 정렬!!
		Arrays.sort(arr);
		
		// ==================================================
		
		int num2 = Integer.parseInt(br.readLine()); 
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		
		for(int i=0; i<num2; i++) {
			select = Integer.parseInt(st2.nextToken()); 
			boolean result = false;	// boolean 형 중요!! 판단용!
			
			int start = arr[0];
			int end = arr[num1-1];
			
			// while 문 중요!! 로직!! 거의 암기임..
			while(start <= end) {
				int mid = (start+end) / 2;
				
				if(mid > select) {
					end = mid - 1;
				}
				else if (mid < select) {
					start = mid + 1;
				}
				else {
					result = true;
					break;
				}
			}
			
			// 정답 출력용!
			if(result) {
				sb.append(1+"\n");
			}
			
			else {
				sb.append(0+"\n");
			}
			
		}
		
		System.out.println(sb);
		
		
	}

}

5) DP 개념**

230318
난이도 상 중의 상이다.

a. DP의 구현 방식 :

큰 문제를 작은 문제로 나누기
작은 문제들이 반복적으로 나타나서 이 작은 문제들의 결과값은 항상 동일
모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장되며 추후 재사용에는 이 DP 테이블을 이용한다.
동적 계획법은 톱-다운 or 바텀-업 방식으로 구현 가능

b. 톱-다운 방식으로 구현

이해하기 쉽다. 가독성이 좋다.
메모이제이션: 구한 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴하도록 로직을 구현
- 재귀 함수 같다.

c. 바텀-업 방식으로 구현

작은 문제에서 큰 문제로 확장해나가서 반복문이 사용된다.
톱-다운 보다 더 안전한 방식이다. 톱-다운은 재귀함수의 깊이가 깊어지면 런타임 에러가 발생할 수 있다.

6) DP 문제 1 : 1463번**

230318
문제 : 정수를 1로 만들기
다시 풀기!! 반복하기
Top-down 방식으로도 풀기 : 어렵다.

점화식 정하기(핵심) :
- D[i] : i에서 1로 만드는 데 걸리는 최소 연산 횟수

a. bottom-up 문제 풀이

a) `d[i] = d[i-1] + 1` 풀이 :

d[i] = d[i-1] + 1 : d[i]는 숫자 i가 1이 되는데 걸리는 최소한의 연산 횟수를 저장해야 합니다.
i에서 1을 빼면 i-1이 되므로, d[i-1]+1을 함으로써, d[i-1] (i-1이 1이 되는데 필요한 최소한의 연산) + 1 (i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화합니다.

예를 들어, d[3] = d[2] + 1 이라고하면, 3에서 1을 빼는 1회 연산을 통해 2가 되므로, d[2] + 1은 3에서 1을 빼서 2가 되고, d[2] (2에서 1이 되는데 필요한 최소 연산 횟수)를 더해준 것입니다.

b) `if(i % 2 == 0) D[i]= Math.min(D[i], D[i/2] + 1);` 풀이 :

d[i]는 위에서 초기화한 d[i-1] + 1 값이 들어있습니다. 이것과 d[i/2]+1을 비교해 최솟값을 d[i]에 넣습니다.
d[i/2]의 의미는 i가 2로 나누어 떨어진다고 조건문에서 확인했으니, i를 2로 나눈 값이 1이 되는데 걸리는 최소한의 연산 횟수를 의미합니다.
즉, d[i/2] + 1은 i를 2로 나눈 값이 1이 되는데 걸리는 최소 연산 횟수 + i를 2로 나누는 연산횟수 1회입니다.

c) `if(i % 3 == 0) D[i]= Math.min(D[i], D[i/3] + 1);` 풀이 :

if(i % 3 == 0) D[i]= Math.min(D[i], D[i/3] + 1); : i가 3으로 나누어 떨어질 때, d[i]와 d[i/3]+1 중 최솟값을 d[i]에 저장합니다.
현재 d[i]는 d[i-1]+1과 i가 2로 나누어 떨어지는 경우, d[i/2]+1 중 최솟값이 들어있습니다.
여기에 i가 3으로 나누어 떨어지는 경우 d[i/3]+1과도 값을 비교해 최솟값을 d[i]에 넣습니다.(중첩의 중첩이다.)

d) 결론 :

이렇게 for문을 반복하면 d[x]에는 x가 1이 되는데 필요한 연산의 최소 횟수가 들어갑니다.

e) 코드 :

package com.wogjs0911.codetest;

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

public class TestDP1463_1_230318 {
	
	static int num1;
	static int[] D;	// 최소 연산 횟수
	
	public static void main(String[] args) throws IOException {
		// 1463번
		// 이거도 어렵다.
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		num1 = Integer.parseInt(br.readLine());
		
		int count = 0;
		
		// 점화식이라서 num1 + 1개가 필요!
		D = new int[num1 + 1];
		D[1] = 0;
		
		// 2부터 num1까지 반복한다.**
		// 이게 왜 적절한 횟수를 찾는 문제인가?
		// 빼기 말고는 나누어 떨어지면 동작하기 때문이다. 
		for(int i = 2; i< num1+1; i++) {
			
			D[i] = D[i-1] + 1;
			// 점화식 개념** : 
			// d[3] = d[2]+1 이라고하면, 3에서 1을 빼는 1회 연산을 통해 2가 되므로, 
			// d[2] + 1은 3에서 1을 빼서 2가 되고, d[2](2에서 1이 되는데 필요한 최소 연산 횟수)를 더해준 것입니다. 
		
			if(i % 2 == 0) 
	 			D[i]= Math.min(D[i], D[i/2]+1);
			
	 		if(i % 3 == 0) 
	 			D[i]= Math.min(D[i], D[i/3]+1);
	 		
	 	
		}
		
		System.out.println(D[num1]);
	}

}

7) DP 문제 2 : 14501번

230318
문제 : 퇴사 준비하기

점화식 정하기(중요!!)
D[i] : i번째 날부터 퇴사날까지 벌 수 있는 최대 수입

D 배열의 개수 초기화가 N+2인 이유
- 인덱스가 “1”부터 시작하기 때문이고 N+1일부터 퇴사처리되고 그 다음날에 임금을 받기 때문이다.
- t와 p는 n-1까지 있지만, dp는 n까지 있습니다.
- 1일 차에 1일짜리 일을 한다면 2일 차에 돈을 받기 때문입니다.

최대 이익 판단 코드 부분 :
- 앞의 코드에서 D[i]가 D[i + 1]되기 때문에 D[i + 1]와 비교한다.
- D[i+T[i]] = 현재 날짜부터 그 만큼의 상담 시간들 = “진짜 마감일”
- P[i] + D[i+T[i]] = 금액 + 현재 날짜부터 그 만큼의 상담 시간들로서 “최대 이익 판단”

package com.wogjs0911.codetest;

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

public class TestDP14501_1_230318 {
	
	static int N;
	static int D[];
	static int T[];
	static int P[];
	
	public static void main(String[] args) throws IOException {
		// 14501번
		// 이거도 어렵다.
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		D = new int[N+2];	// D[i]는 i날째 부터 최대로 벌어들이는 최대 수입
		T = new int[N+1];
		P = new int[N+1];
		
		// 점화식이라서 1부터 시작
		for(int i=1; i<N+1; i++) {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			
			T[i] = Integer.parseInt(st1.nextToken()); 
			P[i] = Integer.parseInt(st1.nextToken()); 
		
		}
		
		// 역으로 날짜 계산
		for(int i = N; i > 0; i--) {
			
			if(i+T[i] > N+1) {		
				// 퇴사일이 안 끝난다..
				// 퇴사 날짜인 N+1보다 i(현재 일자)+T[i](상담 일수)가 더 큰 경우
				// 상담을 할 수 없어서 +0원 이다.
				
				D[i] = D[i + 1];	
				
			} else {				
				// 퇴사일 안에 끝나는 경우, 상담을 추가로 할 수 있기 때문에
				// 최대 수입이 + 된다.
				// 앞의 코드에서 D[i]가 D[i + 1]되기 때문에 D[i + 1]와 비교한다.
				// D[i+T[i]] = 현재 날짜부터 그 만큼의 상담 시간들 = 진짜 마감일
				// P[i] + D[i+T[i]] = 금액 + 현재 날짜부터 그 만큼의 상담 시간들의 최대 이익 판단
				
				D[i] = Math.max(D[i+1], P[i] + D[i+T[i]]);
			}


		}
		
		System.out.println(D[1]); 	// 첫 날부터 시작할 때, 최대 이익!
		
		
	}
}

8) DP 문제 3 : 2193번

230319
문제 : 이친수 구하기

여전히 점화식 짜는 것이 어렵다. 연습 더 할 것. 이게 핵심이다. 주어로 잡는 것
D[i][0] : i 길이에서 끝이 0으로 끝나는 이친수의 개수
D[i][1] : i 길이에서 끝이 1로 끝나는 이친수의 개수

a. 첫 번째 풀이 방법 :

n번째 자리에 0이 올 땐 n-1의 숫자가 0 또는 1 상관이 없으므로 D[n-1]만큼 정답에 더하고
n번째 자리에 1이 올 땐 n-1의 자리에 무조건 0이 와야하기 때문에 D[n-1]에서 0이 올때를 생각해서2
D[n-1]가 있는 상태에서 D[n-2]를 정답에 더하면 된다.
따라서, 점화식은 D[n] = D[n-1] + D[n-2]이다.

b. 두 번째 풀이 방법 :

나는 이게 더 이해하기 쉽다.

package com.wogjs0911.codetest.dp;

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

public class TestDP2193_1_230319 {
	
	static int N;
	static long[][] D;	// 최소 연산 횟수
	
	public static void main(String[] args) throws IOException {
		// 2193번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		// 초기화 주의!! 무조건 0아니면 1만 들어가서 2개만 할당해도 된다.
		// D = new int[N+1][N+1]; 이게 아니다.
		// long 형인 이유도 중요!!
		D = new long[N+1][2];
		
		// 끝나는 숫자
		D[1][1] = 1; 
		D[1][0] = 0;
		
		// 연속되는 값 처리 방법(이전 값을 계속 더해지는 점화식으로 비교!!)
		for(int i = 2; i < N+1; i++) {
			D[i][0] = D[i - 1][1] + D[i - 1][0];
			D[i][1] = D[i - 1][0];
		}
		
		sb.append(D[N][0] + D[N][1]);
		
		System.out.println(sb);
	}

}

c. 주의 할 것

D배열을 int로 선언해줘서 N이 크면 값이 int형으로 담을 수 있는 수보다 컸기 때문이였다. 문제에서 90자리까지 들어 갈 수 있었기 때문이다.
암튼 제출하기 전에 혼자 N에 들어갈 수 있는 수들 중 가장 작은 수와 가장 큰 수는 기본적으로 검사해보고 제출하는 버릇을 들여야 겠다.

9) DP 문제 4 : 11726번

230319
문제 : 2*N 타일 채우기
바텀-업 방식의 점화식은 작은 문제들을 모아서 찾아가는 과정이므로 여러 번 생각해보자!

D[N] : 길이 N으로 만들 수 있는 타일의 경우의 수
- 이런 식으로 점화식을 정의 내리는 것이 중요하다!

package com.wogjs0911.codetest.dp;

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

public class TestDP11726_1_230319 {
	
	public static void main(String[] args) throws IOException {
		// 2193번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		int[] D = new int[N+3];
		
		// 점화식이라서 항상 초기값 필수!!
		D[1] = 1;
		D[2] = 2;
		
		// 이렇게 점화식 생각하는게 어렵다..
		// 그래도 작은문제를 찾아가는 과정이라서 익숙해져가고 있다.
		for(int i = 3; i<N+3; i++) {
			D[i] = D[i-1] + D[i-2];
			D[i] = D[i] % 10007;	// 이건 문제의 조건이다.
		}
		
		System.out.println(D[N]);
	}

}

10) 그리디 문제2 : 1715번

230319
문제 : 카드 정렬하기

우선순위 큐는 자동 정렬이 되어서 순서가 뒤바뀌어도 작은 카드 묶음 2개를 쉽게 뽑을 수 있다.
우선순위 큐를 사용하는 방법과 최소 횟수를 위해서 while문에 반복되어도 누적해져서 더 해진다!!

package com.wogjs0911.codetest.greedy;

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

public class TestGreedy1715_1_230319 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// 1715번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		
		Queue<Integer> queue = new PriorityQueue<>();
		
		// 우선순위 큐는 자동 정렬이 되어서 순서가 뒤바뀌어도
		// 작은 카드 묶음 2개를 쉽게 뽑을 수 있다.
		for(int i = 0; i < N; i++) {
			
			int data= Integer.parseInt(br.readLine());
			queue.add(data);
		}
		
		int card1 = 0;
		int card2 = 0;
		int sum = 0;
		
		while(queue.size() != 1) {
			card1= queue.remove();
			card2 = queue.remove();
			
			// while문에 반복되어도 누적해져서 더 해진다!!
			sum += card1 + card2;
			queue.add(sum);
		}
		
		System.out.println(sum);
	}
}

11) 그리디 문제3 : 1744번

230322
아직 우선순위 큐라는 자료구조가 익숙하지 않다.

package com.wogjs0911.codetest.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestGreedy1744_1_230320 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1744번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());	// 9 
		
		// 정렬을 위해 우선 순위 
		// 우선 순위 큐를 역정렬하기 위해서는 Collections.reverseOrder()를 생성자(())에 넣어준다.
		// 양수 큐는 내림차순한다. 
		Queue<Integer> pqplus = new PriorityQueue<>(Collections.reverseOrder()); 
		Queue<Integer> pqminus = new PriorityQueue<>(); 
		
		int num = 0;
		int zerocount = 0;
		int onecount = 0;
		int sum = 0;
		
		// 입력 값이 정수라서 범위로 나누기!!
		for(int i =0; i < N; i++) {
			num = Integer.parseInt(br.readLine());
			
			if(num >= 2) {
				pqplus.add(num);
			}
			else if(num < 0) {
				pqminus.add(num);
			}
			
			else if(num == 0) {
				zerocount++;
			}
			else if(num == 1) {
				onecount++;
			}
		}
		
		int card1 = 0;
		int card2 = 0;
		
		// 양수 큐에서 나온거 로직 돌리기(가장 중요!!)
		// 문제에서 더하는 부분 다시 보기!!
		while(pqplus.size() >= 2) {
			card1 = pqplus.remove();
			card2 = pqplus.remove();
			sum += card1 * card2;
			
		}
		
		if(pqplus.size() == 1) {
			sum += pqplus.remove();
		}
		
		int minus1 = 0;
		int minus2 = 0;
		
		while(pqminus.size() >= 2) {
			minus1 = pqminus.remove();
			minus2 = pqminus.remove();
			sum += minus1 * minus2;
			
		}
		
		if(pqminus.size() == 1) {
			
			if(zerocount == 0) {
				sum += pqminus.remove();
			}
		}
		
		sum += onecount * 1;
		
		sb.append(sum);
		
		System.out.println(sb);
		
		
	}
}

12) 그리디 문제4 : 1931번

230325
Arrays라서 Collection인데 콜렉션에서 정렬하는 방법을 Comparator를 이용하여 자유롭게 정렬할 수 있다.
정렬하는 방법 주의!!

package com.wogjs0911.codetest.greedy;

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

public class TestGreedy1931_1_230323 {
	
	// 수정하기!!
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 1931번
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());	// 11
		
		
		// 시작 시간과 끝 시간에 의해서 각 경우의 수 때문에 2차원 배열을 이용해야 한다. 
		
		int[][] time = new int[N][2];
		
		// 시작 시간과 끝나는 시간을 입력 값 그대로!! 유지하게 하기
		for(int i=0; i<N; i++) {
			StringTokenizer st1 = new StringTokenizer(br.readLine());
			time[i][0] = Integer.parseInt(st1.nextToken());	// 시작 시간 
			time[i][1] = Integer.parseInt(st1.nextToken());	// 끝나는 시간
		}
		
		// 2차원 배열 정렬하는 방법! 여기서 Comparator를 사용하네.. 원래 객체의 값 비교용인데 콜렉션이라서 그것도 객체이다. 
		
//		for(int i=0; i<N; i++) {
//			Arrays.sort(time[i][0]);
//		}
		
		// Comparator 쓰는 방법 주의!!
		Arrays.sort(time, new Comparator<int[]>(){

			@Override
			public int compare(int[] S, int[] E) {
				
				// 시작시간과 끝나는시간이 같으면 시작 시간이 빠른 순서가 우선이 되어 정렬이 되도록 해야 한다!
				// 앞에 값에서 뒤에 값을 빼므로 정방향이라서 오름차순으로 정렬한다. 프로그래밍에서 오름차순이 기본 값이다.
				if(S[1]==E[1]) {
					return S[0]-E[0];
				}
				
				return S[1]-E[1];	// 기본은 끝나는 시간 기준으로 정렬된다.
			}
			
		});
		
		int count = 0;
		
		// 1번째 방법 : 이거 왜 index 안 맞지? 이건 안 된다. '3' 출력
//		for(int i=0; i<N; i++) {
//			if(time[i][0] >= time[0][1]) {
//				time[0][1] = time[i][1];
//				count++;
//			}
//		}
		
		// 2번째 방법 : index 위에 대로하고, i-1 없이 진행. '4' 출력
		int end = -1;
		for(int i=0; i<N; i++) {
			
			// 현재의 시작 시간이 더 큰 경우 count하기
			if(time[i][0] >= end) { 
				end = time[i][1];
				count++;
			}
		}

		
		sb.append(count);
		
		System.out.println(count);
	}
}

13) BFS 문제2 : 2023번

230325

문제 접근 법 :
- 자리수마다 모두 소수인 숫자를 찾는 문제
- 모든 수를 유기적으로 각 자리마다 연결되어있게 탐색을 해야하므로 완전탐색이며 깊이를 이용하지 않아서 BFS를 이용한다.
- 이러한 문제들은 입력값이 작기 때문에 시간 복잡도 N^2이하의 알고리즘이 사용된다.(2중 반복문 가능)

메서드의 메서드의 연속이라서 어려웠다. 다시 반복해보기!!
로직은 그렇게 어렵지 않다.

package com.wogjs0911.codetest.dfsbfs;

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

public class TestBFS2023_1_230325 {
	
	// 이게 가장 핵심 같다!
	static int N;	
	
	public static void main(String[] args) throws IOException {
		// 2023번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		// 내부 함수의 내부 함수 관계라서 어렵다!!
		// 기본적인 1의 자리에서 소수 기준으로 탐색을 시작한다!
		DFS(2,1);
		DFS(3,1);
		DFS(5,1);
		DFS(7,1);
		
	}

	 
	private static void DFS(int a, int b) {
		int result = 0;
		
		// 최종 결론을 도출 해내는 곳!!
		if(b == N) {
			if(isPrime(a)) {
				result = a;
				System.out.println(result);
				return;
			}
		}
		
		for(int i=1; i<10; i++) {
			
			// 초반의 짝수는 버려버림.. 소수에서 애초에 의미가 없다.
			if(i % 2 == 0)
				continue;
			
			// 1의 자리는 시작부터 필터링하여 탐색해서 십의 자리부터 자리수 늘려나가며 로직!
			if((isPrime(a*10 + i) == true)) {
				DFS(a*10 + i, b + 1);
			}
		}
	}
	
	// 소수인지 판단해주는 곳 중요!!
	private static boolean isPrime(int a) {
		
		// 입력 값의 절반까지만 반복하여 판단하는 이유는 소수는 1과 자기 자신만 약수로 가지고 있기 때문이다.
		for(int i = 2; i < a/2; i++) {
			if(a % i == 0)
				return false;
		}
		
		return true;
	}

}

14) DFS 문제2 : 2178번

230325

문제 접근 법 :
- 보통 2차원 배열에서 각각의 수들이 붙어서 완전 탐색을 요하는 경우 DFS를 이용한다.
- 2차원 배열은 각 행마다 깊이의 단계를 판단해야하기 때문에 DFS가 사용한다.
- 이러한 문제들은 입력값이 작기 때문에 시간 복잡도 N^2이하의 알고리즘이 사용된다.(2중 반복문 가능)

파서하는 방법 : “ “(공백)로 나뉘는게 아니라 붙어있는 문자열을 파서하는 방법(중요!!)
- StringTokenizer로는 기본 파서가 안되어서 한 번 더 중간 과정이 필요하다!!**

package com.wogjs0911.codetest.dfsbfs;

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

public class TestDFS2178_1_230325 {
	
	// ArrayList를 이용하기 위해서는 선언하는 부분이며 추가로 2번의 중간 과정(생성, 초기화)을 통해 사용해야 한다.
	// static ArrayList<Integer>[][] A;	
	// 하지만, 노드와 엣지가 필요가 없어서 기본 배열 이용하기! 이렇게 static으로 이용하면, 추가로 2번의 중간 과정이 필요!!(생성과 초기화)
	static int[][] A;

	static boolean visited[][];
	
	// 입력 값 : 다른 메서드에서 사용해서 static으로 선언
	static int N;
	static int M;
	
	// 맵의 위치 컨트롤
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	
	public static void main(String[] args) throws IOException {
		// 2178번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st1.nextToken());
		M = Integer.parseInt(st1.nextToken());
		
		// ArrayList를 사용시, ArrayList를 생성 해주기!!(여기서는 타입이 제거) 하지만, 기본 배열 이용하기!!
		// A = new ArrayList[N][M];	
		// 하지만, 문제따라 기본 배열 이용하여 생성!!
		A = new int[N][M];
		
		// ArrayList 초기화!!
//		for(int j=0; j<N; j++) {
//			for(int i=0; i<M; i++) {
//				 A[j][i] = new ArrayList<Integer>();
//			}
//		}

		// 방문 체크 배열 초기화
		visited = new boolean[N][M];
		
		// 인접 노드를 사용하는 것이라면, ArrayList 타입을 사용하여 add로 데이터를 더해주지만 
		// 이 문제는 기본 배열을 이용한다. 
		// ** 파서하는 방법 : " "(공백)으로 파서하는게 아니라 붙어있는 문자열을 파서하는 방법(중요!!)
		// StringTokenizer로는 기본 파서가 안되어서 한 번 더 중간 과정이 필요하다!!**
		for(int j=0; j<N; j++) {
			StringTokenizer st2 = new StringTokenizer(br.readLine());
			String line = st2.nextToken();
			
			for(int i = 0; i < M; i++) {
				 // A[j][i] = Integer.parseInt(st2.nextToken());		
				 A[j][i] = Integer.parseInt(line.substring(i, i+1));
			}
		}
		
		DFS(0, 0);
		System.out.println(A[N-1][M-1]);
	}

	
	// x,y 좌표 위치도 헤깔림..
	private static void DFS(int x, int y) {
		
		// 진짜 어렵다..
		Queue<int[]> queue = new LinkedList<>();
		
		// offser? 무슨 메서드임? 해당 객체의 값이 있는지 boolean 값 반환(더 찾아보기!!)
		// insert된 값으로 객체를 만들어서 값을 큐에 넣어주는 것.(큐에서 객체로 값을 넣어줄 때, offer 이용!!)
		queue.offer(new int[] {x,y});	// 초기값 설정
		
		visited[y][x] = true;
		
		// 큐가 빌때까지 무한 반복하여 이동해서 완전 탐색
		while(!queue.isEmpty()) {
			int now[] = queue.poll();	// 탐색하는 값인 "x,y"의 묶음 하나씩 배열에 담긴다. 
										// 위의 offer 메서드에서 담긴다.
			
			for(int k=0; k<4; k++) {	// k가 4인 이유는 상하좌우 방향이라서...

				// dx, dy 배열에 상하좌우 값이 있어서 완전 탐색!
				int newx = now[0] + dx[k];	// now 0은 x좌표, now 1는 y좌표를 의미 
				int newy = now[1] + dy[k];
				
				// 유효성 검사 
				if(newx>=0 && newy>=0 && newx<M && newy<N) {
					
					// 좌표 이동 가능한지 판단하여 좌표 이동했으면 값 변화(깊이 변화)
					if(A[newy][newx] != 0 && !visited[newy][newx]) {
						
						visited[newy][newx] = true;				
						A[newy][newx] = A[now[1]][now[0]] + 1; 
						
						queue.add(new int[] {newx, newy});	// 이동한 좌표 값으로 업데이트
					
					}
				}
			}
		}
	}
}

15) 이진탐색 2 : 2343번

230326

문제 접근법 :
- 강의의 순서가 바뀌면 안 된다는 조건과 가능한 블루레이의 크기 중 최소를 구하는 프로그램 마지막으로 블루레이의 크기는 모두 같아야 하기 때문에 이진탐색을 이용한다!
- 입력값이 100,000개 라서 시간 복잡도 NlogN이하 알고리즘을 이용하자!

package com.wogjs0911.codetest.dfsbfs;

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

public class Test2BS2343_2_230325 {
	
	public static void main(String[] args) throws IOException {
		// 2343번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st1 = new StringTokenizer(br.readLine());
		
		int less = Integer.parseInt(st1.nextToken());	// 9
		int blue = Integer.parseInt(st1.nextToken());	// 3
			
		int[] arr = new int[less];
		int end = 0;
		
		StringTokenizer st2 = new StringTokenizer(br.readLine());
		
		for(int i =0; i<less; i++) {
			arr[i] = Integer.parseInt(st2.nextToken());
			end += arr[i];
		}
		
		Arrays.sort(arr);	// 9 ~ 45
		// Arrays.binarySearch(null, 0)	
		// binarySearch는 내부 로직에서 while문을 사용해서 시간초과 가능성이 높다.
		
		int result = 0;
		int start = arr[less-1];
		
		while(end >= start) {
			int mid = (start+end)/2;	// 22
			int sum = 0;
			
			// 여기 로직? 
			for(int i =0; i<less; i++) {
				
				// 모든 기타 레슨의 길이 만큼을 저장할 수 있는지 체킹
				if(sum + arr[i] > mid) {
					result++;
					sum = 0;
				}
				
				// 저장 못한다면 sum에 더하고 다시 for문 실행
				sum = sum + arr[i];
			}
			
			// 바로 위에서 체킹 후 sum이 0이 아니라면 저장할 공간이 한개 더 필요!
			// sum이 '0' 되면 더 이상 저장하지 않는다.
			if(sum != 0) {
				result++;
			}
			
			// 모든 레슨 길이를 저장할 수 없으면 시작값을 중간 값보다 +1(여유가 없어서 저장 공간의 크기를 늘린다.)
			if(result > blue) {
				start = mid + 1;
			}	// 모든 레슨 길이를 저장할 수 있으면 끝값을 중간 값에서 -1(여유가 있어서 저장 공간의 크기를 줄인다.)
			else {
				end = mid - 1;
			}
			
		}
		sb.append(start);
		System.out.println(start);
		
	}

}

16) DP 5번 : 9252번

230403
DP 저장 테이블 다시 확인!

package com.wogjs0911.codetest.dp;

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

public class TestDP9252_1_230403 {

	static long[][] D;
	static char[] A;
	static char[] B;
	
	// 타입이 Character도 있구나..
	static ArrayList<Character> Path;
	
	public static void main(String[] args) throws IOException {
		// 9252번
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		// num1 = br.readLine().length();
		
//		StringTokenizer st1 = new StringTokenizer(br.readLine());
//		StringTokenizer st2 = new StringTokenizer(br.readLine());
		
//		for(int i =0; i<) {
//			st1.nextToken();		
//			st2.nextToken();
//		}
		
		// ** 자바에서 문자열을 바로 배열에 넣는 방법 **
		A = br.readLine().toCharArray();
		B = br.readLine().toCharArray();
		
		// 생성하는 부분 주의!!
		// D[j][i]는 두 문자열을 비교해서 같으면 배열 위치상 왼쪽 위의 위치에 +1 하기
		D = new long[B.length+1][A.length+1];
		
		// 왜 ArrayList를 쓰지?
		// 생성하는 부분 주의!!
		Path = new ArrayList<Character>();
	
		
		for(int i = 1; i<A.length+1; i++) {
			
			for(int j=1; j<B.length+1; j++) {
				
				// D[j][i]는 두 문자열을 비교해서 같으면 배열 위치상 왼쪽 위의 위치에 +1 하기
				if(A[i-1]==B[j-1])
					D[i][j] = D[i-1][j-1] + 1;
				// D[j][i]가 두 문자열을 비교해서 다르면, 왼쪽 위의 위치 중 큰 값 찾기
				else
					D[i][j] = Math.max(D[i-1][j], D[i][j-1]);
			}
		}
	
		System.out.println(D[A.length][B.length]);
		
		getText(A.length, B.length);
		
		// 사이즈 크기마다 출력
		for(int i =Path.size()-1; i>=0; i--) {
			System.out.print(Path.get(i));
		}
	}
	
	// LCS 출력!!
	private static void getText(int row, int column) {
		if(row==0 || column == 0) return;
		
		// 같으면, LCS에 기록하고 왼쪽 위로 이동
		if(A[row-1] == B[column-1]) {
			Path.add(A[row-1]);
			getText(row-1, column-1);
		
			// 다르면, 왼쪽의 값 중 큰 수로 이동
		} else {
			if(D[row-1][column] > D[row][column-1]) {
				getText(row-1, column);
			} else {
				getText(row, column-1);
			}
		}

	}
	
	

}

이전TIL - 15주차 코드

다음TIL - 16주차 코드

1. 기본 자료구조 및 알고리즘 : 230307 ~

1) 배열 : 11720번

1) parseInt() 메소드를 사용하여 Java에서 char 배열을 int로 변환할 수 있습니다.

2) parseInt() 메소드와 valueOf() 메소드를 사용하여 Java에서 char 배열을 int로 변환할 수 있습니다.

2-1) 배열 : 1546_1

2-2) 구간 합 1 : 1546_2번

3-1) 구간 합 1 : 11659_1번

3-2) 구간 합 1 : 11659_2번

4) 구간 합 2 : 11660번

5) 구간 합 3 : 10986번

6) 투포인터 1 : 2018변

7) 투포인터 2 : 1940변**

2. 응용 알고리즘 문제 : 230315 ~

1) 그리디 문제1 : 11047번

2) DFS 문제1 : 11724번

3) BFS 문제1 : 1260번

4) 이진 탐색 1 : 1920번

5) DP 개념**

a. DP의 구현 방식 :

b. 톱-다운 방식으로 구현

c. 바텀-업 방식으로 구현

6) DP 문제 1 : 1463번**

a. bottom-up 문제 풀이

a) d[i] = d[i-1] + 1 풀이 :

b) if(i % 2 == 0) D[i]= Math.min(D[i], D[i/2] + 1); 풀이 :

c) if(i % 3 == 0) D[i]= Math.min(D[i], D[i/3] + 1); 풀이 :

d) 결론 :

e) 코드 :

7) DP 문제 2 : 14501번

8) DP 문제 3 : 2193번

a. 첫 번째 풀이 방법 :

b. 두 번째 풀이 방법 :

c. 주의 할 것

9) DP 문제 4 : 11726번

10) 그리디 문제2 : 1715번

11) 그리디 문제3 : 1744번

12) 그리디 문제4 : 1931번

13) BFS 문제2 : 2023번

14) DFS 문제2 : 2178번

15) 이진탐색 2 : 2343번

16) DP 5번 : 9252번

a) `d[i] = d[i-1] + 1` 풀이 :

b) `if(i % 2 == 0) D[i]= Math.min(D[i], D[i/2] + 1);` 풀이 :

c) `if(i % 3 == 0) D[i]= Math.min(D[i], D[i/3] + 1);` 풀이 :