[백준]수학1

<<이론 >> 

1. 나머지 연산 

• 답을 M으로 나눈 나머지를 출력하라는 문제 시 유의 할 것
• 분배법칙 성립 

     1. (A + B) mod M = ( (A mod M) + (B mod M) mod M)

     2. (A * B) mod M = ( A mod M) * (B mod M) mod M)

     3. (A - B) mod M = (( A mod M) - (B mod M) + M) mod M) //뺄셈의 경우 주의

     4. 나눗셈은 성립 X

 

2. 최대 공약수

• 최대공약수는 GCD라고 함
  
  
• 가장 쉬운 방법: 2부터 min(A,B)까지 모든 정수로 나누어 보는 방법

for(int i=2; i<=min(a,b); i++) { 
	if( a %i ==0 && b %i == 0) 
    	g = i;
 }

 

 

 

• 유클리드 호제법: GCD(a,b) = GCD(b, a%b) (a %b = 0 이면 b가 최대공약수)

       ex.) GCD(24,16) = GCD(16,8) = GCD(8, 0) = 8 (24와 16의 최대 공약수는 8)

//재귀
int gcd(int a, int b) { 
	if( b==0) return a;
	else return gcd(b,a%b);
}


//while문
int gcd(int a, int b) {
	while( b != 0) {
		int r = a %b;
        a= b;
        b = r;
   }
	return a;
}

 

3.최소 공배수

• 최소 공배수는  LCM이라고 함
  
• GCD를 응용해서 구할 수 있음
  
• LCM = G*(a/G) *(b/G) = (a*b)/G(근데 이렇게 하면 범위를 넘어갈 수 있으므로 전자의 방식을 사용할 것)

4. 진법 변환

• 10진법 수 N을 B진법 수로 바꾸는 법: N을 B로 나누면서 0될때까지 나머지 계속 구하기
• ex) 10진법 수 11을 3진법으로 바꾸기: (11/3 = 3 ... 2) => (3/3 = 1 ...0) => (1/3 = 0 ...1)  따라서 답은 102

5. 소수

• 약수가 1과 자신 밖에 없는 수
  
  2, 3, 5, 7, 11, 13, 17, 19 ,23, 29 ,31, 37, 41, 43, 47, 53..
  
  
• N이 소수일 조건

   1) N-1이하 자연수로 나누어 떨어지면 X

   2) N/2이하 자연수로 나누어 떨어지면 X

   3) 루트 N이하 자연수로 나누어 떨어지면 X(젤 빠름) 

 

-조심할 것: i는 2이상!!!! 2부터!!!!!!1

 

6. 에라토스테네스의 체( 10억 범위 N의 소수를 빨리 찾는 법)

 

* 1~N까지 범위 안에 들어가는 모든 소수를 구하라

      1) 2~N까지 수를 써놓는다.

      2) 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다

      3) 그 수는 소수이다.

      4) 이제 그 수의 배수를 모두 지운다

 

 EX)100까지 수 중 소수를 구하라

      1) 2의 배수 -> 3의 배수 -> 5의 배수 -> 7의 배수 순으로 지운다

      2) ‘지우려는 수’의 제곱수 기준 이전 수 는 이미 삭제됨( 5의 배수를 지우려 할때, 5*2, 5*3은 이미 지워져있다. 7의 배수를 지우려 할 때, 7*2,7*3,7*4,7*5,7*6은 지워져있다)

      3) 11의 배수는 이미 지워져 있다(2,3,5,7로 인해서), 11*11은 121로 100을 넘어가기 때문에 더 이상 수행할 필요가 없다.

j=i*i가 아니라 i+i임!!!!!!

                                      => j의 범위는 2*i부터 시작함

* 코드 설명

1. 변수

    1) 소수 배열, 즉 해당 배열에 소수들을 하나씩 저장할 것임

    2) 소수 배열의 index (소수의 개수)

    3) 해당 소수값 방문 여부(지워짐 여부), true면 지워짐

    4) N(가장 큰 수)

 

2. 알고리즘

    1) i =2~N사이, 만일 i가 지워지지 않았다면 i는 소수임

    2) 소수배열에 i를 추가

    3) 2i부터 N까지 사이값 중 i의 배수 제거(true로 함)

 

7. 소인수분해

• N을 소수의 곱으로 분해하는 것
• N을 소인수분해 시, 나올 수 있는 가장 큰 인자는 루트N 

=> 즉, i값을 2~루트 N 사이로 for문 돌려서 N을 나눌 수 있으면, 나눌 수 없을 때까지 계속 나눔

 

8. 팩토리얼(팩토리얼 0의 개수)

예제 : N!의 뒤의 연속된 0이 몇개인지 알아내는 문제(10의 배수가 몇 번 나왔는지 묻는 문제)

• 2의 제곱수와 5의 제곱 수를 구하면 됨
• 2는 상대적으로 많으니까 5의 배수를 기준으로 찾기!!!
• 5로 계속 나누면서 횟수를 구하기

비슷한 문제: nCm의 0의 개수를 구하라

• nCm = n! / m!(n!-m!)
• 단, 나눗셈이 있어 2의 개수가 없을 수 있으므로 2와 5의 개수 같이구하기

<< 문제 >>

 

1. 최대 공약수와 최소 공배수

1) 문제

    :두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하시오

2) 입력

    :10000이하 자연수끼리의 최대 및 최소 공약수 출력

3) 헷갈린 점

• GCD 구할 때 r = A % B 임 ( A / B 로 썼음ㅠ.ㅠ )
• 여러 배열 중 두 개 골라서 최대 공약수 구할 때 => for문 두개 돌리면 두개의 쌍 만들 수 있음!(어렵게 생각하지 말 것)

2. 진법 변환2

1) 문제

    : 10진법 수 N을 B진법으로 바꿔 출력하라( 10진법 넘어가는 경우 알파벳 문자를 사용한다.)

2) 입력

    : N과 B가 주어짐.(2<=B<=36), 출력: B진법 수

3) 알고리즘

        1. string s(정답 저장할 공간) 정의 

        2.  N /= B해서 N =0 나올때까지 N % B값 s에 저장

        3. N % B 를 구한 후 char 형으로 변환 

             1)  (char)(r + ‘0’) // 숫자를 char형으로 바꿈

              2) (char)(r - 10 + ‘A’) // 10이면 A, 11이면 B... 맞게 char형으로 바꿈

         4. reverse(s.begin(),s.end()); //알고리즘 헤더 

 

3. 2진수 8진수

1) 문제

   : 2진수 -> 8진수로 바꿔라

2) 알고리즘

   1. String으로 입력 받은 2진수 입력값의 길이를 조사한다.

   2. 길이가 3으로 나누어 떨어지지 않는 경우, "0" 또는 "00"을 추가시켜준다.

   3. 3자리씩 끊어 가면서 int 변환한 후 8진수 값으로 변환한다.

 

3) 새로 안 것

1. char -> int : (int) (s[i] -’0)

2. int -> char: (char)( sum + ‘0);

3. int -> char(알파벳): (char)(sum -10 + ‘A’); 

4. -2진수

1) 문제

   :N -> (-2진수)로 바꿔라

2) 핵심

   1. 똑같이 2로 나누면 된다. 단, 나눈 후 몫에 -1을 곱함 & 나머지가 -1일 때 예외처리(몫 -2)

          ex) (-6)/2 = 3*-1 ...0 , (-7)/2 = 4*-1 … 1

 

   2. 처음 while 종료 조건을 N/2==0으로 했는데, 나머지가 -1일때 while문 내에서 몫이 바뀌므로

    N%2를 구해서 나머지가 -1일 때 예외처리 수행 후, if(N/2==0) break;를 수행 해야 함!!

5. Base Conversion

1) 문제

  :A진법 수 -> B 진법 수로 변환 출력

2) 핵심

  :10진수로 바꾸는 법 (num값을 갱신할 때마다 기존 num값 * A 하는 것 잊지 말기)

//A : 10진법으로 바꾸기 전 진법 , S : A진법으로 표현된 값, num:10진법으로 바꿀 값
for(int i=0;i<s.size();i++) {
	if( ‘0’<= s[i] && s[i] <= ‘9') 
		num = num * A + (s[i] - ‘0’); //0~9사이 값은 그 자체로 int형으로 변환
	else
    	num = num * A + (s[i] - ‘A’ + 10); // 10 이상을 의미하는 알파벳을 10진법으로 바꿈
}

6. 골드바흐의 추측

1)문제

  : 4이상의 짝수인 N을 두 소수의 합 형식으로 출력하라

2) 입력 & 출력

: 여러 테스트 케이스(입력이 0이면 종료), N = a + b 형식으로 출력(b-a가 가장 큰 값)

3)알고리즘

    1. 맨 처음 2~1000000 사이의 소수들을 벡터에 저장

    2. 입력 받을 때마다 해당 소수들 검색

 

4) 핵심

  1. 소수가 담긴 배열 내에서 특정 값이 있는지 찾을 때, 

     - 내 구현 법: 소수 배열 내에서 find로 찾음

     - 다른 방법: 지운 값인지를 저장하는 isDel[MAX] 배열에 해당 값이 false인지 체크(이게 더 빠름)

 

  2. 소수 아닌 수 지울 때 j = i*i가 아니라 2i부터 지움