나머지 연산
- (A+B) % C = ( (A%C) + (B%C) ) % C
- DP문제에서 경우의 수가 너무 큰 경우에 주로 사용한다.
- BigInteger의 구현보다 n으로 나눈 나머지를 출력하라는 경우가 매우 많다.
- 예시
- (A+B) % C = ( (A%C) + (B%C) ) % C
- A = q1c+r1- B = q2c+r2
- A+B = (q1+q2)c + (r1+r2)
- A%C = r1
- B%C = r2
- (A%C) + (B%C) = (r1 + r2) % C
- 컴퓨터의 정수는 저장할 수 있는 범위가 저장되어 있기 때문에, 답을 M으로 나눈 나머지를 출력하라는 문제가 등장한다.
- (A+B) mod M = ((A mod M) + (B mod M)) mod M
- (AxB) mod M = ((A mod M) x (B mod M)) mod M
- 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 함)
- 뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야한다.
- (A-B) mod M = ((A mod M) - (B mod M) + M) mod M
나머지
- boj.kr/10430
- 조건
- 첫째 줄에 (A+B) % C- 둘째 줄에 (A%C + B%C) % C
- 셋째 줄에 (AxB) % C
- 넷째 줄에 (A%C x B%C) % C
- 그대로 출력하면 정답이 된다.
- 정답보다는 이 네 연산이 같다는 것을 이해하는 것이 더 중요한 문제
최대공약수
- 최대공약수는 줄여서 GCD(Greatest Common Divisor) 라고 쓴다.
- 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.
- 최대 공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법
int g = 1;
for (int i=2; i<=min(a,b); i++) {
if (a % i == 0 && b % i == 0) {
g = i;
}
}- 최대 공약수가 1인 두 수를 서로소(Coprime)라고 한다.
### 유클리드 호제법 (유클리드 알고리즘) - 최대공약수를 구하는 좀 더 빠른 방법 - a를 b로 나눈 나머지를 r이라고 했을 때- GCD(a, b) = GCD(b, r)과 같다.
- r이 0이면 그 때 b가 최대 공약수이다.
- GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8
- GCD 괄호 내부의 값을 (B, A % B)로 계속하여 치환했을 때, A % B가 0이 되면 GCD
- 재귀를 이용해 구현한 유클리드 호제법int gcd(int a, int b) { if (b == 0) { return a; } else { return gcd(b, a%b); } } ``` - 비재귀를 이용해 구현한 유클리드 호제법 - 호출하는 것이 하나밖에 없는 재귀함수는 비재귀로 변경 가능하다. ```java int gcd(int a, int b) { while ( b != 0 ) { int r = a%b; a = b; b = r; } return a; } ```
- 세 수의 최대 공약수는 다음과 같이 구할 수 있다.
- GCD(a, b, c) = GCD(GCD(a, b), c)- 네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다.
최소 공배수
- Least Common Multiple
- 줄여서 LCM이라고 한다.
- 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수
- 최소공배수는 GCD를 응용해서 구할 수 있다.
- 두 수 a, b의 최대공약수를 g라고 했을 때
- 최소공배수 l = g (a/g) (b/g)이다. - 최소공배수의 경우에는 a와 b보다 커질 수 있다.
- 수의 범위를 잘 확인해야 한다. - 구현
```java public static int gcd(int a, int b){ if(a%b == 0) return b; return gcd(b, a%b); } ```
GCD 합
- 수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 문제
- 위의 GCD를 구하는 공식을 이용하여 풀면 된다.
- 구현
import java.io.IOException;```java import java.io.BufferedReader;
import java.io.InputStreamReader; public class Main {
}public static int gcd(int a, int b){ if(a%b == 0) return b; return gcd(b, a%b); } public static void main (String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); StringBuffer sb = new StringBuffer(); for(int i=0; i<t; i++) { String[] ns = br.readLine().split(" "); int n = Integer.parseInt(ns[0]); long sum = 0; for(int j=1; j<n; j++) { for(int k=j+1; k<=n; k++) { sum += gcd(Integer.parseInt(ns[j]), Integer.parseInt(ns[k])); } } sb.append(sum + "\n"); } System.out.print(sb.toString()); }```
진법 변환
- 10진법 수 N을 B진법으로 바꾸려면 N이 0이 될 때까지 나머지를 계속해서 구하면 된다.
- 예시
- 11을 3진법으로 바꾸기
- 11/3 = 3 ... 2
- 3/3 = 1 ... 0
- 1/3 = 0 ... 1
- 11은 3진법으로 102이다. (아래에서부터 위로)
진법 변환2
-
boj.kr/11005
-
위의 진법 변환을 이용해서 구현하면 된다.
-
구현
```java import java.io.BufferedReader;import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;public class Main {
public static void changeNS(int num, int b){ Stack st = new Stack(); while(num != 0){ int mod = num % b; if(mod >= 10) st.push((char)('A' + (mod - 10))); else st.push(mod); num = num / b; } while(!st.empty()){ System.out.print(st.pop()); } } public static void main (String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] ns = br.readLine().split(" "); int num = Integer.parseInt(ns[0]); int b = Integer.parseInt(ns[1]); changeNS(num, b); }}
```
진법 역변환
-
B진법 수 N을 10진수로 바꾸려면 B^k을 곱하면서 더해나가면 된다.
-
3진법 수 102 = (1 3^2) + (0 3^1) + (2 * 3^0) = 11
```java import java.io.BufferedReader;import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;public class Main {
public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] bn = br.readLine().split(" "); String b = bn[0]; Stack st = new Stack(); for(int i=0; i<b.length(); i++){ if(b.charAt(i) >= 48 && b.charAt(i) <= 57) st.push(((int) b.charAt(i) - 48 )); else st.push(((int) b.charAt(i) - 55 )); } long sum = 0; long mul = 1; while(!st.empty()) { sum += (int) st.pop() * mul; mul *= Integer.parseInt(bn[1]); } System.out.println(sum); }}
진법 변환
-
A진법을 B진법으로 바꾸면 된다.
-
구현
```javaimport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {
public static StringBuilder sb = new StringBuilder(); public static void baseToB(int sum, int b){ if(sum >= b){ baseToB(sum / b, b); sb.append((sum % b) + " "); } else{ sb.append(sum + " "); return; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] ns = br.readLine().split(" "); int a = Integer.parseInt(ns[0]); int b = Integer.parseInt(ns[1]); String m = br.readLine(); ns = br.readLine().split(" "); int sum = 0; int mul = 1; for(int i=ns.length-1; i>=0; i--){ sum += ( Integer.parseInt(ns[i]) * mul ); mul *= a; } baseToB(sum, b); System.out.print(sb.toString()); }}
```
풀스택 웹개발자로 일하고 있는 Jake Seo입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다. 프론트엔드: Javascript, React 백엔드: Spring Framework에 관심이 있습니다.