Algorithm Study #4 (Mathematics)

jakeseo_me·2019년 2월 25일
1

java algorithm study

목록 보기
11/18

나머지 연산

  • (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)까지 모든 정수로 나누어 보는 방법
  • 최대 공약수가 1인 두 수를 서로소(Coprime)라고 한다.
    • 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
      - 재귀를 이용해 구현한 유클리드 호제법
  • 세 수의 최대 공약수는 다음과 같이 구할 수 있다.
    - 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보다 커질 수 있다.
    - 수의 범위를 잘 확인해야 한다.
  • 구현

GCD 합

  • 수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 문제
  • 위의 GCD를 구하는 공식을 이용하여 풀면 된다.
  • 구현 import java.io.IOException;
    import java.io.InputStreamReader; public class Main { }

진법 변환

  • 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.IOException;
    import java.io.InputStreamReader;
    import java.util.Stack;

    public class Main {

    }

진법 역변환

  • B진법 수 N을 10진수로 바꾸려면 B^k을 곱하면서 더해나가면 된다.

  • 3진법 수 102 = (1 3^2) + (0 3^1) + (2 * 3^0) = 11

    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Stack;

    public class Main {

    }

진법 변환

  • A진법을 B진법으로 바꾸면 된다.

  • 구현

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;

    public class Main {

    }

profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.

0개의 댓글