📍 등급 기록
- 1주차 : 2023.07.17 월
- 2주차 : 23.07 24 월
- 3주차 : 23.08.28 월
📍 5. 문자열
📕 꼬마 정민
문제
꼬마 정민이는 이제 A + B 정도는 쉽게 계산할 수 있다. 이제 A + B + C를 계산할 차례이다!코드
import java.util.*;
import java.io.*;
public class baek5_1{
public static void main(String[] args) {
Scanner sc = new Scanner (System.in);
long A = sc.nextLong();
long B = sc.nextLong();
long C = sc.nextLong();
sc.close();
System.out.println(A + B + C);
}
}📕 알파벳 찾기
문제
알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek5_11 {
public static void main(String[] args) {
Scanner in = new Scanner (System.in);
int[] arr = new int[26];
for (int i=0; i < 26; i++)
arr[i] = -1;
String s = in.nextLine();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (arr[c - 'a'] == -1)
arr[c - 'a'] = i;
}
for (int i = 0; i < 26; i++)
System.out.print(arr[i] + " ");
in.close();
}
}📕 문자열 반복
문제
문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는 QR Code "alphanumeric" 문자만 들어있다.
QR Code "alphanumeric" 문자는 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\$%*+-./: 이다.코드
import java.util.*;
public class baek5_12 {
public static void main(String[] args) {
Scanner in = new Scanner (System.in);
int T = in.nextInt();
for (int n = 0; n < T; n++) {
int R = in.nextInt();
String S = in.next();
for (int i = 0; i < S.length(); i++) {
for (int j = 0; j < R; j++) {
System.out.print(S.charAt(i));
}
}
System.out.println();
}
in.close();
}
}📕 단어의 개수
문제
영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.코드
// 런타임 에러 발생
import java.util.*;
public class baek5_13 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int cnt = 0;
String str= in.nextLine();
str = str.trim();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
cnt++;
}
}
if (str.charAt(0) != ' ' && str.charAt(str.length() - 1) != ' ')
System.out.println(++cnt);
if (str.charAt(0) == ' ' && str.charAt(str.length() - 1) == ' ')
System.out.println(--cnt);
in.close();
}
}// 수정
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
StringTokenizer st = new StringTokenizer(str, " ");
System.out.println(st.countTokens());
in.close();
}
}
📕 상수
문제
상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734와 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할 것이다.
두 수가 주어졌을 때, 상수의 대답을 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek5_14 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
a = (a % 10) * 100 + ((a % 100) / 10) * 10 + (a / 100);
b = (b % 10) * 100 + ((b % 100) / 10) * 10 + (b / 100);
System.out.println(a > b ? a : b);
in.close();
}
}📕 다이얼
문제
전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다.
숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다.
상근이의 할머니는 전화 번호를 각 숫자에 해당하는 문자로 외운다. 즉, 어떤 단어를 걸 때, 각 알파벳에 해당하는 숫자를 걸면 된다. 예를 들어, UNUCIC는 868242와 같다.
할머니가 외운 단어가 주어졌을 때, 이 전화를 걸기 위해서 필요한 최소 시간을 구하는 프로그램을 작성하시오.코드
// 다이얼
import java.util.*;
public class baek5_15 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int cnt = 0;
String str = in.nextLine();
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (c == 'A' || c == 'B' || c == 'C')
cnt += 3;
else if (c == 'D' || c == 'E' || c == 'F')
cnt += 4;
else if (c == 'G' || c == 'H' || c == 'I')
cnt += 5;
else if (c == 'J' || c == 'K' || c == 'L')
cnt += 6;
else if (c == 'M' || c == 'N' || c == 'O')
cnt += 7;
else if (c == 'P' || c == 'Q' || c == 'R' || c == 'S')
cnt += 8;
else if (c == 'T' || c == 'U' || c == 'V')
cnt += 9;
else if (c == 'W' || c == 'X' || c == 'Y' || c == 'Z')
cnt += 10;
}
System.out.println(cnt);
in.close();
}
}📕 그대로 출력하기
문제
입력 받은 대로 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek5_16 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextLine()) {
String str = in.nextLine();
System.out.println(str);
}
// < 런타임 에러 발생 >
// for (int i = 0; i < 100; i++) {
// String str = in.nextLine();
// System.out.println(str);
// }
in.close();
}
}📍 6. 심화1
📕 별 찍기 - 7
문제
예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
ex) 입력 : 5
*
***
*****
*******
*********
*******
*****
***
*코드
import java.util.*;
public class baek6_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
for (int i = 1; i < n; i++) {
for (int j = 0; j < n - i; j++) {
System.out.print(" ");
}
for (int j = 0; j < 2 * i - 1; j++) {
System.out.print("*");
}
System.out.println();
}
for (int i = n; i > 0; i--) {
for (int j = 0; j < n - i; j++) {
System.out.print(" ");
}
for (int j = 0; j < 2 * i - 1; j++) {
System.out.print("*");
}
System.out.println();
}
in.close();
}
}
📕 팰린드롬인지 확인하기
문제
알파벳 소문자로만 이루어진 단어가 주어진다. 이때, 이 단어가 팰린드롬인지 아닌지 확인하는 프로그램을 작성하시오.
팰린드롬이란 앞으로 읽을 때와 거꾸로 읽을 때 똑같은 단어를 말한다.
level, noon은 팰린드롬이고, baekjoon, online, judge는 팰린드롬이 아니다.코드
import java.util.*;
public class baek6_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
int result = 1;
for(int i = 0; i < (str.length() / 2); i++) {
char c1 = str.charAt(i);
char c2 = str.charAt(str.length() - i - 1);
if (c1 != c2) {
result = 0;
break ;
}
}
System.out.println(result);
in.close();
}
}📕 단어 공부
문제
알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.코드
import java.util.*;
public class baek6_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] alpha = new int[26];
String str = in.next().toUpperCase();
for(int i = 0; i < str.length(); i++) {
alpha[str.charAt(i) - 'A'] += 1;
}
int max = 0;
char result = '?';
for (int i = 0; i < 26; i++) {
if (alpha[i] > max) {
max = alpha[i];
result = (char)(i + 'A');
}
else if (alpha[i] == max) {
result = '?';
}
}
System.out.println(result);
in.close();
}
}📕 크로아티아 알파벳
문제
예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다.
예를 들어, ljes=njak은 크로아티아 알파벳 6개(lj, e, š, nj, a, k)로 이루어져 있다. 단어가 주어졌을 때, 몇 개의 크로아티아 알파벳으로 이루어져 있는지 출력한다.
dž는 무조건 하나의 알파벳으로 쓰이고, d와 ž가 분리된 것으로 보지 않는다. lj와 nj도 마찬가지이다. 위 목록에 없는 알파벳은 한 글자씩 센다.
코드
import java.util.*;
// import java.io.*;
public class baek6_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String str = in.nextLine();
String[] arr = {"c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="};
for (int i = 0; i < arr.length; i++) {
if (str.contains(arr[i]))
str = str.replace(arr[i], "0");
}
System.out.println(str.length());
in.close();
}
}
📕 그룹 단어 체커
문제
그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.
단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek6_5 {
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
int n = in.nextInt();
int count = 0;
for (int i = 0; i < n; i++) {
if (check() == true) {
count++;
}
}
System.out.println(count);
}
public static boolean check() {
String str = in.next();
boolean[] arr = new boolean[26];
char prev = 0;
for (int j = 0; j < str.length(); j++) {
int index = str.charAt(j) - 'a';
if (prev != str.charAt(j)) {
if (arr[index] == false) {
arr[index] = true;
prev = str.charAt(j);
}
else if (arr[index] == true) {
return (false);
}
}
}
return (true);
}
}📕 너의 평점은
문제
컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 치훈이의 전공평점을 계산해주는 프로그램을 작성해보자.
전공평점은 전공과목별 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값이다.
A+ 4.5
A0 4.0
B+ 3.5
B0 3.0
C+ 2.5
C0 2.0
D+ 1.5
D0 1.0
F 0.0
P/F 과목의 경우 등급이 P또는 F로 표시되는데, 등급이 P인 과목은 계산에서 제외해야 한다.코드
import java.util.*;
public class baek6_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
double sum_a = 0;
double result = 0;
for (int i = 0; i < 20; i++) {
String str = in.next();
double a = in.nextDouble();
String b = in.next();
sum_a += a;
if (b.equals("A+")) {
result += a * 4.5;
} else if (b.equals("A0")) {
result += a * 4.0;
} else if (b.equals("B+")) {
result += a * 3.5;
} else if (b.equals("B0")) {
result += a * 3.0;
} else if (b.equals("C+")) {
result += a * 2.5;
} else if (b.equals("C0")) {
result += a * 2.0;
} else if (b.equals("D+")) {
result += a * 1.5;
} else if (b.equals("D0")) {
result += a * 1.0;
} else if (b.equals("P")) {
sum_a -= a;
}
}
System.out.printf("%.6f", result / sum_a);
in.close();
}
}📍 7. 2차원 배열
📕 행렬 덧셈
문제
N*M크기의 두 행렬 A와 B가 주어졌을 때, 두 행렬을 더하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek7_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[][] A = new int[N][M];
int[][] B = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
A[i][j] = in.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
B[i][j] = in.nextInt();
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
A[i][j] += B[i][j];
System.out.print(A[i][j] + " ");
}
System.out.println();
}
in.close();
}
}
📕 최댓값
문제
9×9 격자판에 쓰여진 81개의 자연수 또는 0이 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 행 몇 열에 위치한 수인지 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek7_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] arr = new int[9][9];
int max = 0;
int max_i = 0;
int max_j = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
arr[i][j] = in.nextInt();
}
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (arr[i][j] > max) {
max = arr[i][j];
max_i = i;
max_j = j;
}
}
}
System.out.println(max);
System.out.print((max_i + 1) + " " + (max_j + 1));
in.close();
}
}📕 세로읽기
문제
장난감에 있는 글자들은 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’부터 ‘9’이다. 영석이는 칠판에 글자들을 수평으로 일렬로 붙여서 단어를 만든다. 다시 그 아래쪽에 글자들을 붙여서 또 다른 단어를 만든다. 이런 식으로 다섯 개의 단어를 만든다. 아래 그림 1은 영석이가 칠판에 붙여 만든 단어들의 예이다.
A A B C D D
a f z z
0 9 1 2 1
a 8 E W g 6
P 5 h 3 k x
한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. 또한 만들어진 다섯 개의 단어들의 글자 개수는 서로 다를 수 있다.
심심해진 영석이는 칠판에 만들어진 다섯 개의 단어를 세로로 읽으려 한다. 세로로 읽을 때, 각 단어의 첫 번째 글자들을 위에서 아래로 세로로 읽는다. 다음에 두 번째 글자들을 세로로 읽는다. 이런 식으로 왼쪽에서 오른쪽으로 한 자리씩 이동 하면서 동일한 자리의 글자들을 세로로 읽어 나간다. 위의 그림 1의 다섯 번째 자리를 보면 두 번째 줄의 다섯 번째 자리의 글자는 없다. 이런 경우처럼 세로로 읽을 때 해당 자리의 글자가 없으면, 읽지 않고 그 다음 글자를 계속 읽는다. 그림 1의 다섯 번째 자리를 세로로 읽으면 D1gk로 읽는다.
그림 1에서 영석이가 세로로 읽은 순서대로 글자들을 공백 없이 출력하면 다음과 같다:
Aa0aPAf985Bz1EhCz2W3D1gkD6x
칠판에 붙여진 단어들이 주어질 때, 영석이가 세로로 읽은 순서대로 글자들을 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek7_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[][] arr = new char[5][15];
for (int i = 0; i < 5; i++) {
String str = in.nextLine();
for (int j = 0; j < str.length(); j++) {
arr[i][j] = str.charAt(j);
}
}
for (int j = 0; j < 15; j++) {
for (int i = 0; i < 5; i++) {
// 추가 구문
if (arr[i][j] == ' ' || arr[i][j] == '\0')
continue;
System.out.print(arr[i][j]);
}
}
in.close();
}
}
📕 색종이
문제
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek7_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int count = 0;
int[][] arr = new int[100][100];
for (int i = 0; i < N; i++) {
int x = in.nextInt();
int y = in.nextInt();
for (int a = x; a < x + 10; a++) {
for (int b = y; b < y + 10; b++) {
arr[a][b] = 1;
}
}
}
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++) {
if (arr[i][j] == 1)
count++;
}
}
System.out.println(count);
in.close();
}
}
📍8. 일반 수학1
📕 진법 변환
문제
B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.
10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.
A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35코드
import java.util.*;
public class baek8_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String N = in.next();
int B = in.nextInt();
int result = 0;
int base = 1;
for (int i = N.length() - 1; i >= 0; i--) {
char c = N.charAt(i);
if ('A' <= c && c <= 'Z') {
result += (c - 'A' + 10) * base;
} else {
result += (c - '0') * base;
}
base *= B;
}
System.out.println(result);
in.close();
}
}📕 진법 변환 2
문제
10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오.
10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.
A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35코드
import java.util.*;
public class baek8_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int B = in.nextInt();
char[] result = new char[36];
int i = 0;
if (N == 0) {
result[i++] = (char)('0');
}
while (N > 0)
{
if (N % B < 10) {
result[i++] = (char)(N % B + '0');
} else {
result[i++] = (char)(N % B + 'A' - 10);
}
N /= B;
}
for (int j = i - 1; j >= 0; j--) {
System.out.print(result[j]);
}
in.close();
}
}
📕 세탁소 사장 동혁
문제
리암은 거스름돈을 주는 것을 자꾸 실수한다. 심지어 $0.5달러를 줘야하는 경우에 거스름돈으로 $5달러를 주는것이다!
거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, $0.25)의 개수, 다임(Dime, $0.10)의 개수, 니켈(Nickel, $0.05)의 개수, 페니(Penny, $0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 $5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, $1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.코드
import java.util.*;
public class baek8_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int C = in.nextInt();
int q = 0; // quater ($0.25)
int d = 0; // dime ($0.10)
int n = 0; // nickel ($0.05)
int p = 0; // penny ($0.01)
if (C >= 25) {
q = C / 25;
C %= 25;
}
if (C >= 10) {
d = C / 10;
C %= 10;
}
if (C >= 5) {
n = C / 5;
C %= 5;
}
if (C >= 1) {
p = C;
C %= 1;
}
System.out.println(q + " " + d + " " + n + " " + p);
}
in.close();
}
}📕 중앙 이동 알고리즘
문제
외계 지형은 중앙 이동 알고리즘을 이용해서 만들려고 한다. 알고리즘을 시작하면서 상근이는 정사각형을 이루는 점 4개를 고른다. 그 후에는 다음과 같은 과정을 거쳐서 지형을 만든다.
정사각형의 각 변의 중앙에 점을 하나 추가한다.
정사각형의 중심에 점을 하나 추가한다.
초기 상태에서 위와 같은 과정을 한 번 거치면 총 4개의 정사각형이 새로 생긴다. 이와 같은 과정을 상근이가 만족할 때 까지 계속한다.
아래 그림은 과정을 총 2번 거쳤을 때까지의 모습이다.
상근이는 어떤 점은 한 개 보다 많은 정사각형에 포함될 수 있다는 사실을 알았다. 메모리 소모량을 줄이기 위해서 중복하는 점을 한 번만 저장하려고 한다.
과정을 N번 거친 후 점 몇 개를 저장해야 하는지 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek8_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt(); // ((p - 1) + p^2)
int p = 2;
for (int i = 1; i <= N; i++) {
p = (p - 1) + p;
}
System.out.println(p * p);
in.close();
}
}📕 벌집
문제
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.코드
import java.util.*;
public class baek8_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = 1;
int room = 2;
// 1 : 1
// 2 : 2 ~ 7 (+ 6)
// 3 : 8 ~ 19 (+ 12)
// 4 : 20 ~ 37 (+ 18)
// 5 : 38 ~ 61 (+ 24)
if (N != 1) {
while (room <= N) {
room += 6 * result;
result++;
}
}
System.out.println(result);
in.close();
}
}📕 분수찾기
문제
코드
// 분수찾기
import java.util.*;
public class baek8_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int X = in.nextInt();
int sum = 0;
int cross = 1;
while (true) {
if (X <= sum + cross) {
if (cross % 2 == 1) {
System.out.print((cross - (X - sum - 1)) + "/" + (X - sum));
break;
} else {
System.out.print((X - sum) + "/" + (cross - (X - sum - 1)));
break;
}
} else {
sum += cross;
cross++;
}
}
in.close();
}
}📕 달팽이는 올라가고 싶다
문제
땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.
달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.
달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek8_7 {
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 V = Integer.parseInt(st.nextToken());
int count = (V - B) / (A - B);
if ((V - B) % (A - B) != 0)
count++;
System.out.println(count);
// < 시간 초과 >
// Scanner in = new Scanner(System.in);
// int A = in.nextInt();
// int B = in.nextInt();
// int V = in.nextInt();
// int height = 0;
// int count = 1;
// while (height <= V) {
// if (height + A >= V)
// break;
// height += A - B;
// count++;
// }
// System.out.println(count);
// in.close();
}
}📍 9. 약수, 배수와 소수
📕 배수와 약수
문제
4 × 3 = 12이다.
이 식을 통해 다음과 같은 사실을 알 수 있다.
3은 12의 약수이고, 12는 3의 배수이다.
4도 12의 약수이고, 12는 4의 배수이다.
두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오.
첫 번째 숫자가 두 번째 숫자의 약수이다.
첫 번째 숫자가 두 번째 숫자의 배수이다.
첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다.코드
import java.util.*;
import javax.lang.model.util.ElementScanner14;
public class baek9_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true)
{
int A = in.nextInt();
int B = in.nextInt();
if (A == 0 && B == 0)
break;
if (B % A == 0)
System.out.println("factor");
else if (A % B == 0)
System.out.println("multiple");
else
System.out.println("neither");
}
in.close();
}
}📕 약수 구하기
문제
어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다.
6을 예로 들면
6 ÷ 1 = 6 … 0
6 ÷ 2 = 3 … 0
6 ÷ 3 = 2 … 0
6 ÷ 4 = 1 … 2
6 ÷ 5 = 1 … 1
6 ÷ 6 = 1 … 0
그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.
두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek9_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int K = in.nextInt();
int[] factor = new int[N];
int j = 0;
for (int i = 1; i <= N; i++) {
if (N % i == 0)
factor[j++] = i;
}
if (K > j)
System.out.println(0);
else
System.out.println(factor[K - 1]);
in.close();
}
}
📕 약수들의 합
문제
어떤 숫자 n이 자신을 제외한 모든 약수들의 합과 같으면, 그 수를 완전수라고 한다.
예를 들어 6은 6 = 1 + 2 + 3 으로 완전수이다.
n이 완전수인지 아닌지 판단해주는 프로그램을 작성하라.코드
import java.util.*;
public class baek9_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(true) {
int N = in.nextInt();
if (N == -1)
break;
int[] factor = new int[N];
int j = 0;
int sum = 0;
for (int i = 1; i <= N; i++) {
if (N % i == 0 && N != i) {
factor[j++] = i;
sum += i;
}
}
if (sum == N) {
System.out.print(N + " = 1");
for(int i = 2; i <= N; i++) {
if (factor[i - 1] != 0) {
System.out.print(" + " + factor[i - 1]);
}
}
System.out.println();
}
else {
System.out.println(N + " is NOT perfect.");
}
}
in.close();
}
}📕 소수 찾기
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek9_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int count = 0;
for (int i = 0; i < N; i++) {
int num = in.nextInt();
for (int j = 2; j <= num; j++) {
if (j == num)
count++;
if (num % j == 0)
break;
}
}
System.out.println(count);
in.close();
}
}
📕 소수
문제
자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.코드
import java.util.*;
public class baek9_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int M = in.nextInt();
int N = in.nextInt();
int sum = 0;
int min = N;
for (int i = M; i <= N; i++) {
for (int j = 2; j <= i; j++) {
if (j == i) {
sum += j;
if (j < min)
min = j;
}
if (i % j == 0)
break;
}
}
if (sum == 0)
System.out.println(-1);
else {
System.out.println(sum);
System.out.println(min);
}
in.close();
}
}📕 소인수분해
문제
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek9_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
while(true) {
if (N <= 1)
break;
for (int i = 2; i <= N; i++) {
if (N % i == 0) {
N /= i;
System.out.println(i);
break;
}
}
}
in.close();
}
}📍 10. 기하: 직사각형과 삼각형
📕 직사각형
문제
정수 A, B 가 주어진다. 세로 길이가 A cm, 가로 길이가 B cm 인 아래와 같은 직사각형의 넓이를 cm2 단위로 구하시오.
코드
import java.util.*;
public class baek10_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int A = in.nextInt();
int B = in.nextInt();
System.out.println(A * B);
in.close();
}
}📕 직사각형에서 탈출
문제
한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek10_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x = in.nextInt();
int y = in.nextInt();
int w = in.nextInt();
int h = in.nextInt();
int min_x = w - x;
int min_y = h - y;
if (min_x > x)
min_x = x;
if (min_y > y)
min_y = y;
System.out.println(min_x > min_y ? min_y : min_x);
in.close();
}
}📕 네 번째 점
문제
세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.코드
import java.util.*;
public class baek10_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x[] = new int[3];
int y[] = new int[3];
int xx = 0;
int yy = 0;
for (int i = 0; i < 3; i++) {
x[i] = in.nextInt();
y[i] = in.nextInt();
}
if (x[0] == x[1])
xx = x[2];
else if (x[0] == x[2])
xx = x[1];
else if (x[1] == x[2])
xx = x[0];
if (y[0] == y[1])
yy = y[2];
else if (y[0] == y[2])
yy = y[1];
else if (y[1] == y[2])
yy = y[0];
System.out.println(xx + " " + yy);
in.close();
}
}📕 수학은 체육과목 입니다
문제
"한 변의 길이가 1인 정사각형을 아래 그림과 같이 겹치지 않게 빈틈없이 계속 붙여 나간다. 가장 아랫부분의 정사각형이 n개가 되었을 때, 실선으로 이루어진 도형의 둘레의 길이를 구하시오."
가장 아랫부분의 정사각형 개수가 주어지면 그에 해당하는 답을 출력하는 프로그램을 만들어 형석이를 도와주자!
코드
import java.util.*;
public class baek10_4 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong(); // 입력 1 < n < 10^9
System.out.println(n * 4); // 둘레 4n
in.close();
}
}📕 대지
문제
임씨의 이름이 새겨진 옥구슬의 위치 N 개가 주어질 때에, 임씨에게 돌아갈 대지의 넓이를 계산하는 프로그램을 작성하시오. 단, 옥구슬의 위치는 2 차원 정수 좌표로 주어지고 옥구슬은 같은 위치에 여러 개가 발견될 수도 있으며, x 축의 양의방향을 동쪽, y 축의 양의방향을 북쪽이라고 가정한다.
예를 들어 위와 같이 (2, 1), (3, 2), (5, 2), (3, 4) 네 점에서 옥구슬을 발견하였다면, 임씨에게 돌아갈 대지는 (2, 1), (5, 1), (2, 4), (5, 4)를 네 꼭짓점으로 하는 직사각형이며, 넓이는 (5 - 2) × (4 - 1) = 9 가 된다. 
코드
import java.util.*;
public class baek10_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int min_x = 10000, max_x = -10000;
int min_y = 10000, max_y = -10000;
for (int i = 0; i < N; i++) {
int x = in.nextInt();
int y = in.nextInt();
if (x > max_x)
max_x = x;
if (x < min_x)
min_x = x;
if (y > max_y)
max_y = y;
if (y < min_y)
min_y = y;
}
System.out.println((max_x - min_x) * (max_y - min_y));
in.close();
}
}📕 삼각형 외우기
문제
삼각형의 세 각을 입력받은 다음,
- 세 각의 크기가 모두 60이면, Equilateral
- 세 각의 합이 180이고, 두 각이 같은 경우에는 Isosceles
- 세 각의 합이 180이고, 같은 각이 없는 경우에는 Scalene
- 세 각의 합이 180이 아닌 경우에는 Error
를 출력하는 프로그램을 작성하시오.코드
import java.util.*;
import javax.lang.model.util.ElementScanner14;
public class baek10_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
if ((a + b + c) == 180) {
if (a == b && b == c)
System.out.print("Equilateral");
else if (a == b || b == c || c == a)
System.out.print("Isosceles");
else
System.out.print("Scalene");
}
else
System.out.print("Error");
in.close();
}
}📕 삼각형과 세 변
문제
삼각형의 세 변의 길이가 주어질 때 변의 길이에 따라 다음과 같이 정의한다.
- Equilateral : 세 변의 길이가 모두 같은 경우
- Isosceles : 두 변의 길이만 같은 경우
- Scalene : 세 변의 길이가 모두 다른 경우
단 주어진 세 변의 길이가 삼각형의 조건을 만족하지 못하는 경우에는 "Invalid" 를 출력한다. 예를 들어 6, 3, 2가 이 경우에 해당한다. 가장 긴 변의 길이보다 나머지 두 변의 길이의 합이 길지 않으면 삼각형의 조건을 만족하지 못한다.
세 변의 길이가 주어질 때 위 정의에 따른 결과를 출력하시오.코드
import java.util.*;
public class baek10_7 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (true) {
int[] arr = new int [3];
arr[0] = in.nextInt();
arr[1] = in.nextInt();
arr[2] = in.nextInt();
if (arr[0] == 0 && arr[1] == 0 && arr[2] == 0)
break;
Arrays.sort(arr);
if (arr[2] >= arr[0] + arr[1])
System.out.println("Invalid");
else if (arr[0] == arr[1] && arr[1] == arr[2])
System.out.println("Equilateral");
else if (arr[0] == arr[1] || arr[0] == arr[2] || arr[1] == arr[2])
System.out.println("Isosceles");
else
System.out.println("Scalene");
}
in.close();
}
}📕 세 막대
문제
영선이는 세 막대를 이용해서 아래 조건을 만족하는 삼각형을 만들려고 한다.
- 각 막대의 길이는 양의 정수이다
- 세 막대를 이용해서 넓이가 양수인 삼각형을 만들 수 있어야 한다.
- 삼각형의 둘레를 최대로 해야 한다.
a, b, c가 주어졌을 때, 만들 수 있는 가장 큰 둘레를 구하는 프로그램을 작성하시오. 코드
import java.util.*;
public class baek10_8 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] arr = new int[3];
arr[0] = in.nextInt();
arr[1] = in.nextInt();
arr[2] = in.nextInt();
Arrays.sort(arr);
if (arr[0] + arr[1] > arr[2])
System.out.println(arr[0] + arr[1] + arr[2]);
else {
arr[2] = arr[0] + arr[1] - 1;
System.out.println(arr[0] + arr[1] + arr[2]);
}
in.close();
}
}📍 11. 시간 복잡도
📕 알고리즘 수업 - 알고리즘의 수행 시간 1
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 1
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
i = ⌊n / 2⌋;
return A[i]; # 코드1
}코드
import java.util.*;
public class baek11_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 단일 연산의 경우 : O(1)의 시간 복잡도
System.out.println('1');
System.out.println('0');
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 2
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 2
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n
sum <- sum + A[i]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
// for문 있을 경우 : O(n)의 시간 복잡도
System.out.println(n);
System.out.println(1);
in.close();
}
}
📕 알고리즘 수업 - 알고리즘의 수행 시간 3
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 3
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n
for j <- 1 to n
sum <- sum + A[i] × A[j]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
// for문 2개 있을 경우 : O(n^2)의 시간 복잡도
System.out.println(n * n);
System.out.println(2);
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 4
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 4
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 1
for j <- i + 1 to n
sum <- sum + A[i] × A[j]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
// 1부터 n-1 까지, i+1qnxj n까지 반복
System.out.println(n * (n - 1) / 2);
System.out.println(2);
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 5
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 5
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n
for j <- 1 to n
for k <- 1 to n
sum <- sum + A[i] × A[j] × A[k]; # 코드1
return sum;
}코드
import java.util.*;
public class baek11_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
// for문 3개 있을 경우 : O(n^3)의 시간 복잡도
System.out.println(n * n * n);
System.out.println(3);
in.close();
}
}📕 알고리즘 수업 - 알고리즘의 수행 시간 6
BAEKJOON 알고리즘 수업 - 알고리즘의 수행 시간 6
문제
입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.
MenOfPassion 알고리즘은 다음과 같다.MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 2
for j <- i + 1 to n - 1
for k <- j + 1 to n
sum <- sum + A[i] × A[j] × A[k]; # 코드1
return sum;
}
코드
import java.util.*;
public class baek11_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Long n = in.nextLong();
System.out.println(n * (n - 1) * (n - 2) / 6);
System.out.println(3);
in.close();
}
}📕 알고리즘 수업 - 점근적 표기 1
문제
알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.
O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}
이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.
함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.코드
import java.util.*;
public class baek11_7 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a1 = in.nextInt();
int a0 = in.nextInt();
int c = in.nextInt();
int n0 = in.nextInt();
if (a1 * n0 + a0 <= c * n0 && c >= a1)
System.out.println(1);
else
System.out.println(0);
in.close();
}
}📍 12. 브루트 포스
📕 블랙잭
문제
제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 새로운 블랙잭 규칙을 만들어 게임하려고 한다.
블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.코드
import java.util.*;
public class baek12_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
int[] arr = new int[N];
int sum = 0;
int max = 0;
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N - 1; j++) {
for (int k = j + 1; k < N; k++) {
sum = arr[i] + arr[j] + arr[k];
if (sum <= M && max < sum)
max = sum;
}
}
}
System.out.println(max);
in.close();
}
}📕 분해합
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.코드
import java.util.*;
public class baek12_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = 0;
for (int i = 0; i < N; i++) {
int number = i;
int sum = 0;
while (number != 0) {
sum += number % 10;
number /= 10;
}
if (sum + i == N) {
result = i;
break;
}
}
System.out.println(result);
in.close();
}
}📕 수학은 비대면강의입니다
문제
문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다.
다음 연립방정식에서 x와 y의 값을 계산하시오.
빈 칸에 수들을 입력하는 식이다. 각 칸에는 -999 이상 999 이하의 정수만 입력할 수 있다. 
코드
import java.util.*;
public class baek12_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
int c = in.nextInt();
int d = in.nextInt();
int e = in.nextInt();
int f = in.nextInt();
int x = 0;
int y = 0;
for (int i = -999; i <= 999; i++) {
for (int j = -999; j <= 999; j++) {
if ((a * i + b * j == c) && (d * i + e * j == f)) {
x = i;
y = j;
break;
}
}
}
// < 런타임 에러(/by zero) >
// int y = ((c * d) - (f * a)) / ((b * d) - (e * a));
// int x = (c - (b * y)) / a;
System.out.println(x + " " + y);
in.close();
}
}📕 체스판 다시 칠하기
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek12_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int M = in.nextInt();
in.nextLine();
boolean[][] board = new boolean[N][M];
for (int y = 0; y < N; y++) {
String str = in.nextLine();
for (int x = 0; x < M; x++) {
if (str.charAt(x) == 'W')
board[y][x] = true;
else
board[y][x] = false;
}
}
int count = 64;
for (int y = 0; y <= N - 8; y++) {
for (int x = 0; x <= M - 8; x++) {
count = Math.min(count, getCount(x, y, board));
}
}
System.out.println(count);
in.close();
}
public static boolean[][] initBoard(String c) {
boolean[][] board = new boolean[8][8];
boolean white = true;
if (c.equals("W")) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
board[i][j] = white;
white = !white;
}
white = !white;
}
return (board);
}
else {
for (int i = 0; i < 8; i++) {
white = !white;
for (int j = 0; j < 8; j++) {
board[i][j] = white;
white = !white;
}
}
return (board);
}
}
public static int getCount(int x, int y, boolean[][] board) {
int count_W = 0;
int count_B = 0;
boolean[][] board_W = initBoard("W");
boolean[][] board_B = initBoard("B");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (board_W[i][j] != board[y + i][x + j])
count_W++;
if (board_B[i][j] != board[y + i][x + j])
count_B++;
}
}
return Math.min(count_W, count_B);
}
}📕 영화감독 숌
문제
종말의 수란 어떤 수에 6이 적어도 3개 이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 수는 666이고, 그 다음으로 큰 수는 1666, 2666, 3666, .... 이다. 따라서, 숌은 첫 번째 영화의 제목은 "세상의 종말 666", 두 번째 영화의 제목은 "세상의 종말 1666"와 같이 이름을 지을 것이다. 일반화해서 생각하면, N번째 영화의 제목은 세상의 종말 (N번째로 작은 종말의 수) 와 같다.
숌이 만든 N번째 영화의 제목에 들어간 수를 출력하는 프로그램을 작성하시오. 숌은 이 시리즈를 항상 차례대로 만들고, 다른 영화는 만들지 않는다.코드
import java.util.*;
public class baek12_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int count = 1;
int num = 666;
while (count != N) {
num++;
if (String.valueOf(num).contains("666")) {
count++;
}
}
System.out.println(num);
in.close();
}
}
📕 설탕 배달
문제
상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek12_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int result = -1;
in.close();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (3 * i + 5 * j == N) {
result = i + j;
System.out.println(result);
return ;
}
}
}
System.out.println(result);
}
}📍 13. 정렬
📕 수 정렬하기
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
for (int i = 0; i < N; i++) {
System.out.println(arr[i]);
}
in.close();
}
}📕 대표값2
문제
어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + 30) / 5 = 170 / 5 = 34가 된다.
평균 이외의 또 다른 대표값으로 중앙값이라는 것이 있다. 중앙값은 주어진 수를 크기 순서대로 늘어 놓았을 때 가장 중앙에 놓인 값이다. 예를 들어 10, 40, 30, 60, 30의 경우, 크기 순서대로 늘어 놓으면
10 30 30 40 60
이 되고 따라서 중앙값은 30이 된다.
다섯 개의 자연수가 주어질 때 이들의 평균과 중앙값을 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[] arr = new int[5];
int sum = 0;
for (int i = 0; i < 5; i++) {
arr[i] = in.nextInt();
sum += arr[i];
}
Arrays.sort(arr);
System.out.println((int)(sum / 5));
System.out.println(arr[2]);
in.close();
}
}📕 커트라인
문제
슬기로운 코딩생활에
$N$명의 학생들이 응시했다.
이들 중 점수가 가장 높은
$k$명은 상을 받을 것이다. 이 때, 상을 받는 커트라인이 몇 점인지 구하라.
커트라인이란 상을 받는 사람들 중 점수가 가장 가장 낮은 사람의 점수를 말한다.코드
import java.util.*;
public class baek13_3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int k = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = in.nextInt();
}
// 버블 정렬 (Arrays.sort(arr))
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
System.out.println(arr[N - k]);
in.close();
}
}📕 수 정렬하기 2
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_4 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int N = in.nextInt();
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < N; i++) {
list.add(in.nextInt());
}
Collections.sort(list);
for (int value : list) {
sb.append(value).append('\n');
}
System.out.println(sb);
// < 시간 초과 > - dual_pivot_Quicksort 사용 (시간복잡도 : O(nlogn), 최악 : O(n2))
// Arrays.sort(arr);
// < 시간 초과 > - bubble sort (시간복잡도 : O(n2))
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N - 1; j++) {
// if (arr[j] > arr[j + 1]) {
// int tmp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = tmp;
// }
// }
// }
in.close();
}
}📕 수 정렬하기 3
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek13_5 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for (int num : arr) {
sb.append(num).append('\n');
}
System.out.println(sb);
// < 메모리 초과 >
// StringBuilder sb = new StringBuilder();
// int N = in.nextInt();
// ArrayList<Integer> list = new ArrayList<> ();
// for(int i = 0; i < N; i++) {
// list.add(in.nextInt());
// }
// Collections.sort(list);
// for (int value : list) {
// sb.append(value).append('\n');
// }
// System.out.println(sb);
// <시간 초과 >
// Arrays.sort(arr);
// < 시간 초과 >
// for (int i = 0; i < N; i++) {
// for (int j = 0; j < N - 1; j++) {
// if (arr[j] > arr[j + 1]) {
// int tmp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = tmp;
// }
// }
// }
}
}📕 소트인사이드
문제
배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.코드
import java.util.*;
public class baek13_6 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] arr = in.next().toCharArray();
Arrays.sort(arr);
for(int i = arr.length - 1; i >= 0; i--) {
System.out.print(arr[i]);
}
// < 성공 >
// int N = in.nextInt();
// int[] arr = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
// int i = 0;
// int base = 10;
// while (N != 0) {
// arr[i++] = N % base;
// N /= base;
// }
// Arrays.sort(arr);
// for (int j = 9; j >= 0; j--) {
// if (arr[j] >= 0)
// System.out.print(arr[j]);
// }
in.close();
}
}📕 좌표 정렬하기
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_7 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
Arrays.sort(arr, (e1, e2) -> { // 람다식 사용
if (e1[0] == e2[0]) {
return e1[1] - e2[1];
} else {
return e1[0] - e2[0];
}
});
for (int i = 0; i < N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
in.close();
}
}📕 좌표 정렬하기 2
문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_8 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
Arrays.sort(arr, (e1, e2) -> {
if (e1[1] == e2[1]) {
return (e1[0] - e2[0]);
} else {
return (e1[1] - e2[1]);
}
});
for (int i = 0; i < N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
in.close();
}
}📕 단어 정렬
문제
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
1) 길이가 짧은 것부터
2) 길이가 같으면 사전 순으로
단, 중복된 단어는 하나만 남기고 제거해야 한다.코드
import java.util.*;
public class baek13_9 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
String[] arr = new String[N];
// 입력받기
for (int i = 0; i < N; i++) {
arr[i] = in.next();
}
// 순서대로 정렬 (길이 -> 사전)
Arrays.sort(arr, new Comparator<String>() {
public int compare(String s1, String s2) {
if (s1.length() == s2.length()) {
return s1.compareTo(s2);
} else {
return s1.length() - s2.length();
}
}
});
// 중복 제거 및 출력
System.out.println(arr[0]);
for (int i = 1; i < N; i++) {
if (!arr[i].equals(arr[i - 1]))
System.out.println(arr[i]);
}
in.close();
}
}📕 나이순 정렬
문제
온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek13_10 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
String[][] arr = new String[N][2];
for (int i = 0; i < N; i++) {
arr[i][0] = in.next();
arr[i][1] = in.next();
}
Arrays.sort(arr, new Comparator<String[]>() {
public int compare(String[] s1, String[] s2) {
return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
}
});
for (int i = 0; i < N; i++) {
System.out.println(arr[i][0] + " " + arr[i][1]);
}
in.close();
}
}📕 좌표 압축
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.코드
import java.util.*;
public class baek13_11 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
int[] sort = new int[N];
HashMap<Integer, Integer> RankMap = new HashMap<Integer, Integer>();
for (int i = 0; i < N; i++) {
sort[i] = arr[i] = in.nextInt();
}
Arrays.sort(sort);
int rank = 0;
for (int value : sort) {
if (!RankMap.containsKey(value)) {
RankMap.put(value, rank);
rank++;
}
}
StringBuilder sb = new StringBuilder();
for (int key : arr) {
int n = RankMap.get(key);
sb.append(n).append(' ');
}
System.out.println(sb);
// < 시간 초과 >
// int N = in.nextInt();
// int[] arr = new int[N];
// int[] sort = new int[N];
// int count = 0;
// for (int i = 0; i < N; i++) {
// arr[i] = in.nextInt();
// if (isChar(sort, arr[i], count) != 1) {
// sort[count++] = arr[i];
// }
// }
// int[] cut = new int[count];
// cut = Arrays.copyOfRange(sort, 0, count);
// Arrays.sort(cut);
// for (int i = 0; i < N; i++) {
// int n = arr[i];
// System.out.print(isChar(cut, n, count) + " ");
// }
in.close();
}
// public static int isChar(int[] sort, int n, int count) {
// for (int i = 0; i < count; i++) {
// if (sort[i] == n) {
// return (i);
// }
// }
// return (0);
// }
}📘 Map (맵)
- 선언 : HashMap<Element, Element> map = new HashMap<>();
- Element : 데이터 타입 지정
- 개념
- 특정 순서에 따라 key와 value 조합으로 형성된 자료구조
- key(중복x)로 value(중복O) 얻음
- Map 인터페이스로 자료형에는
HashMap,LinkedHashMap,TreeMap존재put(key, value): key-value 넣기get(key): key에 해당하는 value 가져오기containsKey(key): 키의 유무 확인remove(key): 값 삭제 (삭제한 값 리턴)size(): 맵에 저장된 데이터 개수 확인
📘 Set (집합)
- 선언 : HashSet<Element> set = new HashSet<>();
- Element : 데이터 타입 지정
- 개념
- 집합과 관련된 것 처리하는 자료형 (인덱싱을 통해 값 얻음)
- 데이터 중복X, 순서X
- Set 인터페이스로 자료형에는
HashSet,TreeSet,LinkedHashSet존재add(): 값 추가remove(): 값 제거
📘 HashTable (해시테이블)
- 선언 :
- Element : 데이터 타입 지정
- 개념
- key와 value를 1:1로 연관지어 저장하는 자료구조
- 내부적으로 배열 사용하여 데이터 저장
- 특정 값 탐색시 index(key)로 접근하여 시간복잡도 O(1)(빠른 검색속도)
📍 14. 집합과 맵
📕 숫자 카드
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek14_1 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count_N = Integer.parseInt(br.readLine());
int[] N = new int[count_N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < count_N; i++) {
N[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(N);
int count_M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < count_M; i++) {
int search = Integer.parseInt(st.nextToken());
System.out.print(binary_search(N, count_N, search) + " ");
}
}
public static int binary_search(int[] N, int count, int search) {
int first = 0;
int last = count - 1;
int mid = 0;
while (first <= last) {
mid = (first + last) / 2;
if (N[mid] == search)
return (1);
if (N[mid] < search) {
first = mid + 1;
} else {
last = mid - 1;
}
}
return (0);
}
}
📕 문자열 집합
문제
총 N개의 문자열로 이루어진 집합 S가 주어진다.
입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek14_2 {
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 M = Integer.parseInt(st.nextToken());
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < N; i++) {
map.put(br.readLine(), 0);
}
int count = 0;
for (int i = 0; i < M; i++) {
if (map.containsKey((br.readLine())))
count++;
}
System.out.println(count);
}
}
📕 회사에 있는 사람
문제
각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.
상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.코드
import java.io.*;
import java.util.*;
public class baek14_3 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Map<String, String> map = new HashMap<>();
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String key = st.nextToken();
String value = st.nextToken();
if (map.containsKey(key))
map.remove(key);
else
map.put(key, value);
}
ArrayList<String> list = new ArrayList<String>(map.keySet());
Collections.sort(list, Collections.reverseOrder());
for (var value : list)
System.out.println(value + " ");
}
}
📕 나는야 포켓몬 마스터 이다솜
문제
포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 코드
import java.util.*;
import java.io.*;
public class baek14_4 {
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 M = Integer.parseInt(st.nextToken());
Map<String, Integer> smap = new HashMap<>();
Map<Integer, String> imap = new HashMap<>();
for (int i = 1; i <= N; i++) {
String name = br.readLine();
smap.put(name, i);
imap.put(i, name);
}
for (int i = 1; i <= M; i++) {
String str = br.readLine();
if (isNum(str)) {
System.out.println(imap.get(Integer.parseInt(str)));
} else {
System.out.println(smap.get(str));
}
}
}
public static boolean isNum(String str) {
for (int i = 0; i < str.length(); i++) {
if (!Character.isDigit(str.charAt(i)))
return false;
}
return true;
}
}
📕 숫자 카드 2
문제
숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.코드
import java.util.*;
import java.io.*;
public class baek14_5 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
HashMap<Integer, Integer> map = new HashMap<>();
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
int m = Integer.parseInt(st.nextToken());
if (map.get(m) == null)
map.put(m, 1);
else
map.put(m, map.get(m) + 1);
}
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int n = Integer.parseInt(st.nextToken());
if (map.get(n) == null)
sb.append(0).append(" ");
else
sb.append(map.get(n)).append(" ");
}
System.out.println(sb);
}
}
📕 듣보잡
문제
김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.
듣보잡의 수와 그 명단을 사전순으로 출력한다.코드
import java.util.*;
import java.io.*;
public class baek14_6 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
HashMap<String, Integer> map = new HashMap<>();
List<String> list = new ArrayList<>(); // 사전순 정렬 목적
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
map.put(br.readLine(), 1);
}
for (int i = 0; i < M; i++) {
String input = br.readLine();
map.put(input, map.getOrDefault(input, 0) + 1);
if (map.get(input) == 2)
list.add(input);
}
Collections.sort(list);
sb.append(list.size()).append("\n");
for (String s : list)
sb.append(s).append("\n");
System.out.println(sb);
}
}📕 대칭 차집합
문제
자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다.
예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다.코드
import java.util.*;
import java.io.*;
public class baek14_7 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Set<Integer> set_A = new HashSet<>();
Set<Integer> set_B = new HashSet<>();
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < A; i++) {
int n = Integer.parseInt(st.nextToken());
set_A.add(n);
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < B; i++) {
int n = Integer.parseInt(st.nextToken());
set_B.add(n);
}
int result = 0;
for (int num : set_A) {
if (!set_B.contains(num))
result++;
}
for (int num : set_B) {
if (!set_A.contains(num))
result++;
}
System.out.println(result);
}
}
📕 서로 다른 부분 문자열의 개수
문제
문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.
부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.
예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.코드
import java.util.*;
import java.io.*;
public class baek14_8 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Set<String> set = new HashSet<String>();
String s = br.readLine();
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
set.add(s.substring(i, j));
}
}
System.out.println(set.size());
}
}
📍 15. 약수, 배수와 소수2
📕 최소공배수
문제
두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.
두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.코드
import java.util.*;
public class baek15_1 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for (int i = 0; i < N; i++) {
int a = in.nextInt();
int b = in.nextInt();
int r = gcd(a, b);
System.out.println(a * b / r);
}
// < 시간 초과 >
// for (int i = 0; i < N; i++) {
// int A = in.nextInt();
// int B = in.nextInt();
// for (int j = 2; j <= A * B; j++) {
// if ((j % A == 0) && (j % B == 0)) {
// System.out.println(j);
// break;
// }
// }
// }
in.close();
}
public static int gcd (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return (a);
}
}
📕 최소공배수
문제
정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.
예:
10은 5의 배수이다 (5*2 = 10)
10은 10의 배수이다(10*1 = 10)
6은 1의 배수이다(1*6 = 6)
20은 1, 2, 4,5,10,20의 배수이다.
다른 예:
2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
10과 20의 최소공배수는 20이다.
5와 3의 최소공배수는 15이다.
당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.코드
import java.util.*;
public class baek15_2 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
long a = in.nextLong();
long b = in.nextLong();
long r = gcd(a, b);
System.out.println(a * b / r);
in.close();
}
public static long gcd(long a, long b) {
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return (a);
}
}
📕 분수 합
문제
분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.
두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.코드
import java.util.*;
public class baek15_3 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int a1 = in.nextInt();
int a2 = in.nextInt();
int b1 = in.nextInt();
int b2 = in.nextInt();
int gcf = gcd(a2, b2); // 최대공약수
int lcm = a2 * b2 / gcf; // 최소공배수
int a = (lcm / a2) * a1 + (lcm / b2) * b1;
int b = lcm;
while (gcd(a, b) != 1) {
gcf = gcd(a, b);
b /= gcf;
a /= gcf;
}
System.out.println(a + " " + b);
in.close();
}
public static int gcd (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return (a);
}
}📕 가로수
문제
직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.
편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.
예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.
심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.코드
import java.util.*;
public class baek15_4 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] arr = new int[N];
for (int i = 0; i < N ; i++) {
arr[i] = in.nextInt();
}
Arrays.sort(arr);
int gcf = 0;
for (int i = 0; i < N - 1; i++) {
int distance = arr[i + 1] - arr[i];
gcf = gcd(distance, gcf);
}
System.out.println(((arr[N - 1] - arr[0]) / gcf) + 1 - N);
in.close();
}
public static int gcd (int a, int b) {
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return (a);
}
}📕 다음 소수
문제
정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.코드
import java.math.BigInteger;
import java.util.*;
public class baek15_5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
for (int i = 0; i < N; i++) {
long n = in.nextLong();
// isProbalbePrime()과 nextProbalbePrime()은 BigInteger만 지원
BigInteger b = new BigInteger(String.valueOf(n));
if (b.isProbablePrime(10)) {
System.out.println(n);
} else {
System.out.println(b.nextProbablePrime());
}
}
// < 시간 초과 >
// for (int i = 0; i < N; i++) {
// long n = in.nextLong();
// if (isPrime(n) == 0) {
// System.out.println(n);
// } else {
// System.out.println(getPrime(n));
// }
// }
in.close();
}
// public static long isPrime(long n) {
// long sqrt = (long)Math.sqrt(n);
// for (int i = 2; i <= sqrt; i++) {
// if (n % i == 0)
// return (1);
// }
// return (0);
// }
// public static long getPrime(long n) {
// while (isPrime(n) != 0) {
// n++;
// }
// return(n);
// }
}📕 소수 구하기
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.코드
import java.math.BigInteger;
import java.util.*;
public class baek15_6 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
int b = in.nextInt();
for (int i = a; i <= b; i++) {
BigInteger big = new BigInteger(String.valueOf(i));
if (big.isProbablePrime(10)) { // 인자값 : 확실성 정도
System.out.println(big);
}
}
in.close();
}
}📕 베르트랑 공준
문제
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.
이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.
예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)
자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 코드
import java.util.*;
public class baek15_7 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int N = 123456;
boolean[] arr = new boolean[2 * N + 1];
for (int i = 2; i <= 2 * N; i++) {
arr[i] = true;
}
for(int i = 2; i <= Math.sqrt(2 * N); i++) {
for (int j = i + i; j <= 2 * N; j += i) {
arr[j] = false;
}
}
while (true) {
int n = in.nextInt();
if (n == 0)
break;
int count = 0;
for (int i = n + 1; i <= 2 * n; i++) {
if (arr[i]) {
count++;
}
}
System.out.println(count);
}
// < 시간 초과 >
// while (true) {
// int n = in.nextInt();
// if (n == 0)
// break;
// int count = 0;
// for (int i = n + 1; i <= 2 * n; i++) {
// BigInteger b = new BigInteger(String.valueOf(i));
// if (b.isProbablePrime(10)) {
// count++;
// }
// }
// System.out.println(count);
// }
in.close();
}
}📕 골드바흐 파티션
문제
골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.코드
import java.util.*;
public class baek15_8 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
boolean[] arr = new boolean[1000000 + 1];
arr[0] = arr[1] = true;
for (int i = 2; i * i <= 1000000; i++) {
if (!arr[i]) {
for (int j = i + i; j <= 1000000; j += i) {
arr[j] = true;
}
}
}
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int n = in.nextInt();
int count = 0;
for (int j = 2; j <= n / 2; j++) {
if (!arr[j] && !arr[n - j]) {
count++;
}
}
System.out.println(count);
}
in.close();
}
}📕 창문 닫기
문제
서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.
예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,
1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)
결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.코드
import java.util.*;
public class baek15_9 {
public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int n =in.nextInt();
int count = 0;
// 약수가 홀수 인 것 찾기
// 제곱수만 약수가 홀수
for (int i = 1; i * i <= n; i++) {
count++;
}
System.out.println(count);
// < 메모리 초과 >
// long N = in.nextLong();
// boolean[] arr = new boolean[N + 1];
// for (int i = 1; i <= N; i++) {
// for (int j = i; j <= N; j += i) {
// if (arr[j])
// arr[j] = false;
// else
// arr[j] = true;
// }
// }
// int count = 0;
// for (int i = 1; i <= N; i++) {
// if (arr[i])
// count++;
// }
// System.out.println(count);
in.close();
}
}📖출처📖
Notion으로 이동 (https://24tngus.notion.site/3a6883f0f47041fe8045ef330a147da3?v=973a0b5ec78a4462bac8010e3b4cd5c0&pvs=4)