2018-9-22 백준알고리즘 수학

알고리즘 Math

최대공약수(Greeterst Common Divisor)

  • GCD라고 쓴다.
  • 두 수 A와 B의 최대공약수 G는 B와 A의 공통된 약수중에 가장 큰 정수이다.
  • 최대공약수가 1인 서로다른 두 수를 서로소라고한다.
  • GCD(a,b) = GCD(b,r) // r = a%b
// Recursion을 이용해서 GCD구하기
int gcd(int a, int b) {
	if (b == 0)
    	return a;
    return gcd(b, a%b);
}

진법변환

2진수 => 8진수 // 8진수 => 2진수

  • 2진수의 3자리씩 묶어서 변환을 하면 된다.
  • 8진수를 2진수로 바꿀때 주의할점은 8진수 맨 앞자리가 001 이런식으로 나오면 00을 지워야한다.

-2진수

  • 일반적인 진법 변환으로 하면 안된다.
  • 나머지가 음수가 나오면 안된다.
  • 총 2가지로 나누면 양수/-2의 경우와 음수/-2의 경우로 나눌 수 있다.
  • 각각의 경우에서 양수가 2로 나누어 떨어지는 경우와, 음수가 2로 나누어 떨어지는 경우로 나눌 수 있다.
  • 6/2 = 3 … 0
  • 7/2 = 3 … 1
  • -6/2 = -3 … 0

  • -7/2 = -4 … 1

  • A진법을 B진법으로 바꾸려면 : A진법 -> 10진법 -> B진법

소수

  • 소수 : 약수가 1과 자기 자신밖에 없는 수
  • N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

일반적인방법

boolean prime(int n) {
	if (n < 2) {
    	return false;
    }

    for (int i=2; i<=n-1; i++) {
    	if (n%i==0) {
        	return false;
        }
    }
    return true;
}
// 시간복잡도 O(N)

소수 더 빠른방법 : N이 소수가 되려면, 2보다 크거나 같고 N/2보다 작거나 같은 자연수로 나누어 떨어지면 안된다. why? N의 약수 주에서 가장 큰것은 N/2보다 작거나 같기때문

  • N = a * b로 나타낼때, a가 작을수록 b는 크다. 가능한 a중에서 가장 작은 값은 2이기 때문에, b는 N/2를 넘지 않는다.
boolean prime(int n) {
	if (n < 2) {
    	return false;
    }

    for (int i=2; i<=n/2; i++) {
    	if (n%i==0) {
        	return false;
        }
    }
    return true;
}
// 시간복잡도 O(N/2) 그러므로 O(N);

소수 가장 빠른방법 : N이 소수가 되려면, 2보다 크거나 같고, 루트N보다 작거나 같은 자연수로 나누어 떨어지면 안된다.

  • N = a * b(a <= b)에서 a>b라면 두수를 바꿔서 항상 a<=b로 만들수있다. 두 수 a와b의 차이가 가장 작은 경우는 루트N이다.
boolean prime(int n) {
	if (n < 2) {
    	return false;
    }

    for (int i=2; i*i<=n/; i++) {
    	if (n%i==0) {
        	return false;
        }
    }
    return true;
}
// 시간복잡도 O(root(N))
  • 컴퓨터에서 실수는 근사값을 나타내기 때문에, 루트N과 같은 경우는 i*i<=n과 같은 방법이 좋다.

소수 - 에라토스테네스의 체

  • 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다.
  1. 2부터 N까지 모든 수를 써놓는다.
  2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
  3. 그 수는 소수이다.
  4. 이제 그 수의 배수는 모두 지운다.

  • 어떤 수를 기준으로 그 수의 제곱부터 지우면 된다.
  • 예를 들어 5를 기준으로하면 52(25) / 53(35) / 54(210)은 이전에 다 지운다.
int p[100] // 소수 저장
int pn = 0; // 소수 개수
boolean c[101]; // 지워졌으면 true;
int n = 100; // 100까지의 소수
for(int i=2; i<=n; i++) {
	if(c[i] == false) {
    	p[pn++] = i;
        for (int j=i*i; i<=n; j+=i) {
        	c[j]=true
        }
    }
}
// c[i] : true => 지워짐
  • 1부터 N까지 모든 소수를 구하는 것이 목표라서, 구현할 때는 바깥 for문 (i)를 N까지 돌린다.
  • 안쪽 for문(j)는 N의 크기에 따라서, ii 또는 i2로 바꾸는 것이 좋다.
  • i=100만인경우, i*i는 범위를 넘어간다.

소수 - 골드바흐의 추측

  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
  • 위의 문장에 3을 더하면
  • 5보다 큰 모든 홀수는 세 소수의합으로 표현가능
  • 아직 증명되지 않은 문제이지만 10^18이하에서는 참인것이 증명되어있다.
  • 나는 잘 모르겠다…. 이해가…

소인수분해

  • 정수 n을 소수의 곱으로 분해
  • 소수를 구하지 않고도 해결가능, N을 소인수분해 했을 때, 나타날 수 있는 인수중에서 가장 큰 값은 루트N이다.
  • 2부터 루트N까지 for문을 돌리면서 N을 나눌 수 있으면, 나눌 수 없을 때 까지 계속해서 나누면 된다. ``` for (int i=2; i*i<=n; i++) { while(n%i==0) { printf(“%d\n”,i); n /= i; } }

if(n>1) { printf(“%d\n”,i); } ```

팩토리얼

  • 매우 큰 수
  • 우리가 구할 수 있는것은 10!정도

Written on September 22, 2018