JAVA
1. 분수의 덧셈
소인수, 소수
소인수: 약수 중 소수인 약수
소수(prime number): 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 (즉, 약수의 개수가 2개인 수)
int cnt = 0;
if ((a%b)==0) {
cnt++;
}
if (cnt == 0) {
a 는 소수임.
}
약수: 어떤 수를 나누어 떨어지게 하는 수
a가 b의 약수 == (b = ak)
= a가 b를 나눈다. (k = a / b)
( 0의 약수 == 모든 정수 )
= ( 모든 정수 == 0의 배수)
a % b == 0 이면 b는 a의 약수
공약수: 두 수, 혹은 그 이상의 여러 수의 공통인 약수
약분: 분수의 분자와 분모를 그의 공약수로 나눠서 간단하게 함.
서로소: 1을 제외하고 두 수의 공통인수(공약수)가 없음.
gcd(a, b) = 1
기약분수: 분자와 분모가 서로소 상태여서 더 이상 약분을 할 수 없는 분수
-- 두 수의 최대공약수로 나누기
최대공약수(gcd: Great Common Divisor): 공약수 중 가장 큰 공약수
3과 12의 최대공약수 = gcd(3, 12) = 3
(1) 서로의 약수를 나열해서 공통된 약수를 뽑고 그 중 가장 큰 약수를 선택.
(2) 유클리드 호제법 (유클리드 알고리즘)
A > B, A ≠ B 일 때,
gcd(A, B) = gcd(B, r) = gcd(r, r1) ... = gcd(g, 0) = g
A = B * q + r ( q = A를 B로 나눈 몫, r = 나머지 )
(ex. 13 = 3 * 4 + 1 )
0 ≤ r < B < A (나머지가 B보다 클 리 없음)
gcd(A, B) = g 일 때, A = ga, B = gb
(단, gcd(a, b) = 1, 즉, a와 b는 서로소여야 함)
(A 와 B의 최대공약수가 g이면, A 와 B 모두 서로소(a, b)와 최대공약수(g)가 곱해진 값이다.)
A = B * q + r
ga = gb * q + r
r = ga - gbq
r = g ( a - bq )
편의상 ( a - bq ) 을 R 이라 할 때,
r / g = R 이라는 값을 가지므로, r은 g로 나눠질 수 있다고 볼 수 있다.
아까 B = gb 라고 했고, r = gR 이면,
B와 r은 g를 공약수로 지닌다는 걸 알 수 있다.
g가 B와 r의 최대공약수가 되려면, b와 R이 서로소여야 한다.
즉, gcd(b, R) = 1 이어야 함. 그리고 맞음. (증명방법은 영상 참고) https://youtu.be/Obs-HC5j5bI
즉!! B와 r의 최대공약수는 g 이다!!!!
★ 결론 ★
gcd(A, B) = gcd(B, r)
r은 A를 B로 나눈 나머지.
(ex)
gcd(12345, 123)
= gcd(123, 45)
= gcd(45, 33)
= gcd(33, 12)
= gcd(12, 9)
= gcd(9, 3)
= gcd(3, 0) = 3
[출처]
https://namu.wiki/w/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95
1차 시도
-- 실행률 86.5%
class Solution {
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int[] answer = new int[2];
boolean val = numer1 > 0 && denom1 > 0 && numer2 > 0 && denom2 > 0 && numer1 < 1000 && denom1 < 1000 && numer2 < 1000 && denom2 < 1000;
if (val) {
// 분수 덧셈
int denom = denom1 * denom2;
numer1 *= denom2;
numer2 *= denom1;
int numer = numer1 + numer2;
for(int i = 2; i < 100; i++){
// 분모와 분자가 나눠질 때, 그 수로 나눈 값을 배열에 넣기
if (numer % i == 0 && denom % i == 0){
numer /= i;
denom /= i;
}
answer[0] = numer;
answer[1] = denom;
}
return answer;
}
}
2차 시도
-- 실행중단... 속도 더 느려지고 15개 중 2개 성공함
-- 이중 for 문이라서 그런듯 ㅠ
class Solution {
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int[] answer = new int[2];
boolean val = numer1 > 0 && denom1 > 0 && numer2 > 0 && denom2 > 0 && numer1 < 1000 && denom1 < 1000 && numer2 < 1000 && denom2 < 1000;
if (val) {
int denom = denom1 * denom2;
numer1 *= denom2;
numer2 *= denom1;
int numer = numer1 + numer2;
// 최대공약수 찾기
int max = 0;
for(int n = 1; n < numer; n++){
for(int d = 1; d < denom; d++){
if (numer % n == 0 && denom % d == 0 && n == d){
max = Math.max(max, n);
}
}
}
answer[0] = numer/max;
answer[1] = denom/max;
}
return answer;
}
}
최종
- 자주 쓰는 복잡한 코드...는 메소드로 빼기.
- 사람들이 정의해놓은 코드 복붙하는 데에 양심의 가책 느끼지 않기 ㅠ
class Solution {
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int[] answer = new int[2];
boolean val = numer1 > 0 && denom1 > 0 && numer2 > 0 && denom2 > 0 && numer1 < 1000 && denom1 < 1000 && numer2 < 1000 && denom2 < 1000;
if (val) {
int d = denom1 * denom2; // 분모
int n = (numer1 * denom2) + (numer2 * denom1); // 분자
int g = gcd(n, d);
answer[0] = n/g;
answer[1] = d/g;
}
return answer;
}
// 최대공약수 구하는 유클리드호제법
public int gcd(int a, int b){
if (b == 0) return a;
return gcd(b, a % b);
// 리턴값으로 자기자신을 호출해서 조건(b==0)을 만족하기 전까지 루프 돎.
}
}SQL
1. 동물 수 구하기
2. 중복 제거하기
- distinct 컬럼명 -- 해당 컬럼의 중복 제거 (= group by)
select distinct 컬럼명 from 테이블명; -- 중복제거
select 컬럼명 from 테이블명 group by 컬럼명; -- 중복제거 + 정렬
- where 컬럼명 is not null -- null 키워드 거르기
3. 최솟값 구하기
- group by 문제 풀다가 포기하고 쉬운 문제로 넘어옴. 화이팅하자!
