코드업 기초 문제풀이 100제에 이어서, BaekJoon 사이트의 문제입니다.
Covenant의 코딩테스트 대비를 위한 백준 문제 추천 :https://covenant.tistory.com/224
위의 링크에 있는 Part 순서대로 풀겠습니다! 시작🔥
Dark 모드에서는 코드가 살짝 깨져서 보이는 거 같네요! light 모드로 변경하면 안깨집니다.
코딩테스트 언어는 Java 입니다.
준비운동 PART1. 튼튼한 기본기
👉 약수구하기 : https://www.acmicpc.net/problem/2501
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int k = sc.nextInt();
int arr[] = new int[num + 1];
for (int i = 1; i <= num; i++) {
if (num % i == 0) {
arr[i] = i;
}
}
System.out.println(arr[k]);
sc.close();
}
}
👉 이진수 : https://www.acmicpc.net/problem/3460
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
String arr[] = new String[num];
for (int i = 0; i < num; i++) {
int t = sc.nextInt();
Integer.toBinaryString(t); // 10진수 2진수 변환
StringBuffer sb = new StringBuffer(Integer.toBinaryString(t));
arr[i] = sb.reverse().toString();
}
for (String bin : arr) {
for (int i = 0; i < bin.length(); i++) {
if (bin.charAt(i) == '1') {
System.out.printf("%d ", i);
}
}
System.out.println();
}
sc.close();
}
}
👉 최소,최대 : https://www.acmicpc.net/problem/10818
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int arr[] = new int[num];
for (int i = 0; i < num; i++) {
arr[i] = sc.nextInt();
}
Arrays.sort(arr);
System.out.printf("%d %d", arr[0], arr[num - 1]);
sc.close();
}
}
👉 지능형 기차 2 : https://www.acmicpc.net/problem/2460
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int sum = 0;
int max = 0;
for (int i = 0; i < 10; i++) {
int out = sc.nextInt();
int in = sc.nextInt();
sum += (in - out);
if (max < sum)
max = sum;
}
System.out.println(max);
sc.close();
}
}
👉 피보나치 수 5 : https://www.acmicpc.net/problem/10870
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
System.out.print(fibo(num));
sc.close();
}
static int fibo(int Num) {
if (Num == 0)
return 0;
if (Num == 1)
return 1;
return fibo(Num - 1) + fibo(Num - 2);
}
}
👉 일곱 난쟁이 - 브루트 포스 : https://www.acmicpc.net/problem/2309
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] who = new int[9];
int sum = 0;
int fake1 = 0, fake2 = 0;
for (int i = 0; i < 9; i++) {
who[i] = sc.nextInt();
sum += who[i];
}
sc.close();
Arrays.sort(who);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (sum - who[j] - who[i] == 100) {
fake1 = who[j];
fake2 = who[i];
}
}
}
for (int a : who) {
if (a == fake1 || a == fake2)
continue;
else
System.out.println(a);
}
}
}
👉 최대공약수와 최소공배수 : https://www.acmicpc.net/problem/2609
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 유클리드 호제법? 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면
// (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
// 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여
// 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num1 = sc.nextInt();
int num2 = sc.nextInt();
sc.close();
System.out.println(GCD(num1, num2));
System.out.println(LCM(num1, num2));
}
static int GCD(int num1, int num2) { // 최대공약수(Greatest Common Divisor)
if (num1 % num2 == 0) {
return num2;
}
return GCD(num2, num1 % num2);
}
static int LCM(int num1, int num2) { // 최소공배수 (Least Common Multiple)
return num1 * num2 / GCD(num1, num2);
}
}
👉 N번째 큰수 : https://www.acmicpc.net/problem/2693
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[10];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 10; j++) {
arr[j] = sc.nextInt();
if (j == 9) {
Arrays.sort(arr);
System.out.println(arr[7]);
}
}
}
sc.close();
}
}
👉 소수 찾기 : https://www.acmicpc.net/problem/1978
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int count = 0;
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
if (PrimeNumber(num) != false)
count++;
}
sc.close();
System.out.println(count);
}
static boolean PrimeNumber(int num) {
if (num < 2) {
return false; // 1은 소수가 될 수 없음.
}
for (int i = 2; i < num; i++) {
if (num % i == 0) {
return false; // 소수는 1과 자기자신만을 약수로 가짐
}
}
return true;
}
}
👉 쉽게 푸는 문제 : https://www.acmicpc.net/problem/1292
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int start = sc.nextInt();
int end = sc.nextInt();
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < i; j++) {
arr.add(i); // 배열 만들기 (i값을 j만큼 넣기)
}
}
sc.close();
int sum = 0;
for (int i = start - 1; i < end; i++) {
sum += arr.get(i);
}
System.out.println(sum);
}
}
👉 소수 : https://www.acmicpc.net/problem/2581
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int sum = 0;
int min = 100000;
for (int i = m; i <= n; i++) {
if (PrimeNumber(i) == true) {
sum += i;
if (i < min)
min = i;
}
}
if (sum == 0) {
System.out.println(-1);
} else {
System.out.println(sum);
System.out.println(min);
}
sc.close();
}
static boolean PrimeNumber(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i < num; i++) {
if (num % i == 0)
return false;
}
return true;
}
}
준비운동 PART2. 약점 체크
❌ 재귀탐색: 연산자 끼워넣기 : https://www.acmicpc.net/problem/14888
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Main {
static int n;
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
static int[] arr;
static int[] operator = new int[4]; // 순서대로 +, -, *, /
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt(); // 숫자 배열 입력받기
}
for (int i = 0; i < operator.length; i++) {
operator[i] = sc.nextInt(); // 연산자 갯수 입력받기
}
dfs(1, arr[0]);
System.out.println(max);
System.out.println(min);
sc.close();
}
static void dfs(int depth, int val) {
if (depth == n) { // 연산자 다 썼을때
max = Math.max(max, val);
min = Math.min(min, val);
return;
}
for (int i = 0; i < operator.length; i++) {
if (operator[i] >= 1) {
operator[i]--; // 연산자 갯수가 1 이상이면 감소시켜라.
if (i == 0) {
dfs(depth + 1, val + arr[depth]);
} else if (i == 1) {
dfs(depth + 1, val - arr[depth]);
} else if (i == 2) {
dfs(depth + 1, val * arr[depth]);
} else if (i == 3) {
dfs(depth + 1, val / arr[depth]);
}
operator[i]++; // 재귀함수 끝나면 복구
}
}
}
}
👉 스택의 응용 : 괄호의 값 : https://www.acmicpc.net/problem/2504
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
char[] arr = new char[s.length()];
for (int i = 0; i < s.length(); i++) {
arr[i] = s.charAt(i); // 입력 값 배열에 넣기
}
Stack<String> stack = new Stack();
try {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == '(') {
stack.push("(");
}
if (arr[i] == '[') {
stack.push("[");
}
if (arr[i] == ')') {
String top = stack.peek();
if (top == "(") {
stack.pop();
stack.push("2");
} else {
int result = 0;
while (top != "(") {
result += Integer.parseInt(top);
stack.pop();
top = stack.peek();
}
stack.pop(); //"("
result *= 2;
stack.push(Integer.toString(result));
}
}
if (arr[i] == ']') {
String top = stack.peek();
if (top == "[") {
stack.pop();
stack.push("3");
} else {
int result = 0;
while (top != "[") {
result += Integer.parseInt(top); // 숫자는 더한다.
stack.pop(); // top
top = stack.peek();// 새로운 top
}
stack.pop();// '['
result *= 3;
stack.push(Integer.toString(result));
}
}
}
int result = 0; // 숫자만 남았을때
while (!stack.empty()) {
result += Integer.parseInt(stack.pop());
}
System.out.println(result);
} catch (Exception e) {
System.out.println(0);
}
sc.close();
}
}
👉 시뮬레이션 기본: 빗물 : https://www.acmicpc.net/problem/14719
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
int[] block = new int[w];
int[] max_water = new int[w];
int[] water = new int[w];
// 벽 높이 저장하기
for (int i = 0; i < w; i++) {
int n = sc.nextInt();
block[i] = n;
}
int max = 0;
// 물이 들어갈 수 있는 최대 높이 - 벽의 높이(왼-오)
for (int i = 0; i < w; i++) {
if (max < block[i])
max = block[i];
max_water[i] = max;
water[i] = max;
// System.out.printf("%d ", max_water[i]);
}
max = 0;
// 물이 들어갈 수 있는 최대 높이 - 벽의 높이(오-왼)
for (int i = w - 1; i >= 0; i--) {
if (max < block[i])
max = block[i];
max_water[i] = max; // 오른쪽 벽높이 기준으로 재정렬
if (water[i] > max_water[i]) {
water[i] = max_water[i]; // 최대 물 높이보다 높으면 하강
}
}
// 최대높이 - 벽높이
int sum = 0;
for (int i = 0; i < w; i++) {
sum += (water[i] - block[i]);
}
System.out.println(sum);
sc.close();
}
}
❌ 완전탐색의 유연한 생각: 가르침 : https://www.acmicpc.net/problem/1062
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h = sc.nextInt();
int w = sc.nextInt();
int[] block = new int[w];
int[] max_water = new int[w];
int[] water = new int[w];
// 벽 높이 저장하기
for (int i = 0; i < w; i++) {
int n = sc.nextInt();
block[i] = n;
}
int max = 0;
// 물이 들어갈 수 있는 최대 높이 - 벽의 높이(왼-오)
for (int i = 0; i < w; i++) {
if (max < block[i])
max = block[i];
max_water[i] = max;
water[i] = max;
// System.out.printf("%d ", max_water[i]);
}
max = 0;
// 물이 들어갈 수 있는 최대 높이 - 벽의 높이(오-왼)
for (int i = w - 1; i >= 0; i--) {
if (max < block[i])
max = block[i];
max_water[i] = max; // 오른쪽 벽높이 기준으로 재정렬
if (water[i] > max_water[i]) {
water[i] = max_water[i]; // 최대 물 높이보다 높으면 하강
}
}
// 최대높이 - 벽높이
int sum = 0;
for (int i = 0; i < w; i++) {
sum += (water[i] - block[i]);
}
System.out.println(sum);
sc.close();
}
}