나머지 연산

  • (A+B) % C = ( (A%C) + (B%C) ) % C
  • DP문제에서 경우의 수가 너무 큰 경우에 주로 사용한다.
  • BigInteger의 구현보다 n으로 나눈 나머지를 출력하라는 경우가 매우 많다.
  • 예시
    • (A+B) % C = ( (A%C) + (B%C) ) % C
    • A = q<sub>1</sub>c+r<sub>1</sub>
    • B = q<sub>2</sub>c+r<sub>2</sub>
    • A+B = (q<sub>1</sub>+q<sub>2</sub>)c + (r<sub>1</sub>+r<sub>2</sub>)
    • A%C = r<sub>1</sub>
    • B%C = r<sub>2</sub>
    • (A%C) + (B%C) = (r<sub>1</sub> + r<sub>2</sub>) % 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); 
      }
      }
    • 비재귀를 이용해 구현한 유클리드 호제법
      • 호출하는 것이 하나밖에 없는 재귀함수는 비재귀로 변경 가능하다.
        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보다 커질 수 있다.
    • 수의 범위를 잘 확인해야 한다.
  • 구현
        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.BufferedReader;
      import java.io.IOException;
      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

  • 위의 진법 변환을 이용해서 구현하면 된다.

  • 구현

      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

      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진법으로 바꾸면 된다.

  • 구현

      import 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());
          }
      }