류호석님의 알고리즘 github 강의커리큘럼과 최백준님의 코딩테스트 준비 기초 커리큘럼을 따라 작성한 문서입니다!
중간중간 참고한 블로그/강의는 해당 자료 아래에 출처를 남기도록 하겠습니다!
풀이는 java를 사용하여 작성했습니다.
다시 풀 문제는 빨강색
자주 다시 읽어보기★
★백준 4375 : 1
새로 알게된것 : 테스트 케이스의 갯수가 정해지지 않았을 때
hasNext() 메서드를 사용한다.
hasNext()는 다음에 가져올 값이 있는지 없는지를 boolean 타입으로 반환한다.
▼처음에 쓴 코드
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int cnt;
static double sum;
public static void main(String[] args) {
while(scanner.hasNext()) {
int n=scanner.nextInt();
System.out.println(solve(n));
}
}
public static int solve(int n) {
double i=1;
cnt=0;
sum=0;
while(sum%n!=0||sum==0) {
sum=(sum%n)+1*i;
i=i*10;
cnt++;
}
return cnt;
}
}1로 이루어진 값을 하나하나씩 만들어서 나머지가 0이 아닐때까지 while문을 돌리는 코드를 짰다.
시간초과가 떴다.
▼다시 짠 코드
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int cnt;
static double sum;
public static void main(String[] args) {
while(scanner.hasNext()) {
int n=scanner.nextInt();
System.out.println(solve(n));
}
}
public static int solve(int n) {
cnt=0;
sum=1;
while(sum%n!=0) {
sum=(sum*10)+1;
sum=sum%n;
cnt++;
}
return cnt+1;
}
}아무리 생각해도 모르겠어서 검색을 해봤는데 다들 나머지 연산을 한 결과를 10*i+1 (1로만 이루어진 숫자 만들기 공식)에 넣어서 코드를 작성하셨다.
아무리 봐도 이해가 안가서 여기 저기 찾아봤는데
(A+B) mod M = ((A mod M) + (B mod M)) mod M
(AxB) mod M = ((A mod M) x (B mod M)) mod M
(A-B) mod M = ((A mod M) - (B mod M) + M) mod M
이런 나머지연산의 공식을 적어 놓은 곳이 많았다...
처음엔 첫번째 식을 사용해서 111=(100+11)로 놓고 [(100+11)%7=(100%7)+(11%7)]%7 이런식으로 푸는건가 라고 생각했는데 그럼 100->1000->10000으로 늘어나니까 시간초과가 뜰것같다.
계속 헷갈리다가 모든 자리수가 1로 이루어져 있으므로 111에서 백의자리와 십의자리의 나머지 계산을 한 것이 11을 나머지 계산한것에 *10+1한것과 같다는 것을 이해했다.
너무 이해하는데 오래걸려서 아주 큰일이다 ㅠㅅㅠ ..
★백준 17427 : 약수의 합 2
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int cnt;
static int sum=0;
public static void main(String[] args) {
n=scanner.nextInt();
solve();
}
public static int solve() { //1~n까지의 각각의 약수를 더한 값
//i의 약수를 구해서 다 더하기
for(int i=1;i<n+1;i++) {
int m=(int) Math.floor(Math.sqrt(i));
for(int j=1;j<=m;j++) {
int k=0;
if(i%j==0) {
k=i/j;
if(k==j) {
sum+=k;}
else {sum=sum+j+k;}
}
}
System.out.println(i+"의 sum은"+sum+"입니다");
}
System.out.println(sum);
return 0;
}
}첫번째는 당연히 약수를 다 구해서 더하면 시간초과가 날것같아서 나름 제곱근까지만 for문을 돌리는 방법을 사용해보았는데 역시나 시간초과 ㅠㅠ
두번째로 이렇게 해도 시간초과가 난다면 해당 f(x)수열에 규칙성이 있지 않을까 하고 일단 다 적어보았다. 뭔가 일정수가 더해지는 수열은 아니였다.
너무 규칙이 궁금해서 찾아봤더니
n/i 수만큼 i가 존재한다는 것을 알게 되었다.ㅠㅠ
아니 다들 이게 뚝딱 머릿속에서 나오는건지 아님 한두시간 고민해보고 나오는건지 신기하다.
나만 돌머린가ㅠ
만약 n이 9일경우
f(1) = 1
f(2) = 1 + 2
f(3) = 1 + 3
f(4) = 1 + 2 + 4
f(5) = 1+ 5
f(6) = 1 + 2 + 3 + 6
f(7) = 1 + 7
f(8) = 1 + 2 + 4 + 8
f(9) = 1 + 3 + 9
확인해보면 1은 9개, 2는 4개, 3은 3개, 4는 2개, 5는 1개, 6은 1개, 7은 1개, 8은 1개, 9는 1개가 나오는 것을 알 수 있다.
즉, 9/1 = 9, 9/2 = 4, 9/3 = 3, 9/4 = 2, ... , 9/9 = 1임을 알 수 있다.
그래서 코드는 한줄로 줄어들고 시간초과를 면할 수 있었다.
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n;
static int cnt;
static long sum=0;
public static void main(String[] args) {
n=scanner.nextInt();
for(int i=1;i<=n;i++) {
sum=sum+((n/i)*i);
}
System.out.print(sum);
}
}코드를 짜서 주어진 테스트 케이스는 다 통과했는데 계속 틀렸습니다가 뜨는것,,,
왜그런지 봤더니 입력이 백만 까지 있을 수 있어서 int 범위를 넘길 수도 있는가 보다
백준 2609 : 최대공약수와 최소공배수
일단 지금 내가 생각한 방법을 사용하면 시간초과가 날것같다.
알아야할 사전지식 : 유클리드 호제법
gcd를 최대 공약수를 구하는 함수라고 하고 r을 a/b의 나머지라고 할 때 gcd(a,b)=gcd(b,r)과 같다고 한다. (0<=r<b) (a>=b)
그래서 gcd를 for문이나 재귀문을 써서 반복하다보면 r이 0이된다. 그러면 최대 공약수가 완성되는 것
참고블로그
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int a,b;
static int cnt;
static int k;//최대 공약수
public static void main(String[] args) {
a=scanner.nextInt();
b=scanner.nextInt();
gcd(a,b);
System.out.println(k);
System.out.print(a*b/k);
}
public static void gcd(int a, int b) {
if(b==0) {
k=a;
return;
}
int r=a%b;
gcd(b,r);
}
}백준 1929 : 소수 구하기
사전지식 : 에라토스테네스의 체
2 부터 n의 제곱근수까지 해당 수의 배수를 지워나가는 알고리즘이다.
참고블로그
import java.util.*;
public class Main {
public static Scanner scanner=new Scanner(System.in);
static int n,m;
static int arr[];
public static void main(String[] args) {
n=scanner.nextInt();
m=scanner.nextInt();
arr=new int[m+1];
solve(arr);
for(int i=n;i<m+1;i++) {
if(arr[i]==0) {
System.out.println(i);
}
}
}
public static void solve(int arr[]) {
arr[0]=arr[1]=1;
for(int i=2;i*i<=m;i++) {
if(arr[i]==1) {
continue;
}
for(int j=i*i;j<arr.length;j=j+i) { //i의 배수를 구해야함
arr[j]=1;
}
}
}
}