알고리즘 기초 - 수학(개념)

백준 문제 풀면서 마주친 기초 수학 개념

코드 정리한게 있는데 이걸 보는걸 추천한다. -> 백준 풀이 알고리즘 템플린-수학

최대 공약수(GCD), 최소 공배수(LCM)

“공”약수, “공”배수 로써 “공통된 약수, 배수”를 의미하므로 두 수에서 공통된 최대약수, 공통된 최소배수 값을 구하는 것이다.

• 최대공약수 : 두 수의 몫이 서로소(더이상 공통수로 나눌 수 없을때)가 나올때까지 나눠서 나눈 수 들의 곱
• 최소공배수 : 위의 최대공약수에서 서로소(최종 몫) 까지 다 곱한 값
• 서로소 : 최대공약수가 1인 두 자연수
  • 예 : 서로소인 3과 2의 경우 공약수는 1만 있으므로 최대공약수는 1
    • 3은 약수 1,3을 가짐
    • 2는 약수 1,2를 가짐
• 참고
  • 나누는 것은 나눠지는 가장 작은 소수부터 나눠야 한다.
  • 공약수, 공배수 에서 1은 무조건 기본으로 있다는걸 기억
  • 동일한 수들을 입력받은 경우 최대공약수, 최소공배수는 당연히 입력받은 수가 되는것은 자명

두개의 수(물론 여러개의 수도 다룰 줄 알아야 함)를 입력받아서 GCD, LCM을 구하는 문제에서 필요했던 개념이다.

중요!! 유클리드 호제법

그냥 나눠지는 가장 작은 소수로 나눠가면서 약수들을 구하는게 제일 평범한 방법이지만 속도가 느리다.
이때 빠르게 구할 수 있는 또다른 방법이 “유클리드 호제법”이다.

• 호제법 : 두 수가 서로 상대방의 수를 나누어서 원하는 수를 얻는 방법
  • 유클리드 호제법 : 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면(단, a> b), a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다.
    • (a, b) = (b, r)
    • EX) 10 20 : (10, 20) = (20, 10) = (10, 0) = 10
• 참고로 여러 수에서의 최대공약수도 간단히 구할 수 있다.
  • 먼저, gcd(a,b)를 유클리드 호제법 함수라고 가정하자!
  • 4개의 수가 a,b,c,d라면 gcd(gcd(gcd(a,b),c),d) 이런 느낌으로 재귀나 for문으로 구하면 된다.

소수

소수란 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수(2번째 방식 권장)

• EX) 2 3 5 7 11 13 17 19 23 29 …

방법1) 약수를 구해서 1과 자기자신을 가지는지 구하기

• 소인수분해처럼 직접 나눠서 약수들을 구해서 판별하는 방식(속도 느림)

방법2) 에라토스테네스의 체 -> 다음 정리 참고

중요!! 에라토스테네스의 체 방식

• 초기 배열(prime[]) 값은 false로 초기화
  • false면 소수 , true면 소수 아닌것을 의미
• 소수 특성상1과 자기자신 외에는 나누어 떨어지는 수가 없어야 한다.
  • 즉, 당연히 자신보다 작은 수들의 배수값과 동일한게 있으면 안된다.
• 에라토스테네스의 체 원리가 이런 특성을 이용한것이다.
  • 초기는 전부 소수로 보기 때문에 현재 수가 아직 걸러지지 않았다면 소수이고, 그게 아니면 현재 수의 배수들을 제거해나가는 방식이다.
  • 예로 에라토스테네스의 체 알고리즘 흐름을 보자면
    • int p=2 부터 시작하므로 p*p=2*2=4로써 4부터 2의 배수들을 쭉 prime 배열에서 걸러낸다.
      • 참고: 1은 소수X 이므로 p=2부터 시작
      • 또한, 4부터 2의 배수들의 의미는 i += 2 를 의미 (i=4)
    • 그 결과는 처음 prime[2]는 소수로써 안걸러지고, prime[4, 6, 8…] 배수들은 소수가 아닌것으로 걸러지는 형태이다.
    • p=3 의 경우 위과정과 완전 동일하다.
    • p=4 의 경우?? prime[4]는 애초에 p=2때 걸러졌기 때문에 바로 다음 p++로 넘어간다.
    • 이런형태로 흘러간다. (아래 코드 참고!!)

p = 2;
while (p * p <= N) {
    if (prime[p] == false) {
        for (i = p * p; i < N + 1; i += p) {
            prime[i] = true;
        }
    }
    p++;
}

소인수분해

• 소인수 : 주어진 자연수의 약수 중에서 소수인 것을 의미

• 소인수분해 : 자연수를 소인수들의 곱으로 표현하는 것

  • 나누는 것은 나눠지는 가장 작은 소수로부터 나눠야 한다.
  • 즉, 60 = 2 x 2 x 3 x 5 로 소인수 분해가 된다.

N팩토리얼의 값에서 일의자리 수 부터 0의 개수를 구하되 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제에서 사용했다.

• 10! = 3628800 에서 0의 개수는 2개
• 이를 소인수분해의 개념으로 구함
  • 뒤에 0이 나오는 경우는 x*10 로써 10이 곱해진 경우로 따로 볼 수 있는건 자명하다.
    • 10의 소인수분해 : 2x5=10
    • 따라서 2, 5의 개수를 세서 10이 곱해진 횟수를 구해서 0의 개수를 추측한다.
  • 자세한 내용은 팩토리얼 0의 개수 풀이 게시글 참고
  • 물론 이것 말고도 응용 문제는 다양하다.

중요!! 약수에 존재하는 특정 수의 개수

팩토리얼 0의 개수 문제에서 필요한 수학적 개념이다. (두번째 방식을 익혀둘 것)

• 첫번째 방식은(가장 간단)
  • 예로 5의 개수를 구할땐? 약수 구할때처럼 그냥 5로 나누어 떨어지면 1개(즉, 나머지=0)
  • 그 값에 또 5로 나누어 떨어지면 1개 추가, 이를 반복…
  • 안 나누어 떨어질 때까지(즉, 나머지!=0) 합하면 이때 5의 총 개수가 됨.
• 두번째 방식은(더 빠름)
  • 예로 10! 의 경우? 10!=1*2*3*4*5*6*7*8*9*10 이다.
  • 5로 해당 10 을 나누어주면?? 1~10 곱 사이의 5가 나온 개수가 출력된다 => 이 특징을 이용!
    • 5의 개수 : 10/5=2, 10/5^2 = 0 => 총 2개
    • 2의 개수 : 10/2=5, 10/2^2 = 2, 10/2^3 = 1, 10/2^4 = 0 => 총 8개
  • 참고로 위에서 2나 5의 제곱 수도 고려하고 있는데, 이 원리를 설명하겠다.
    • 예로 25!을 생각해보자. 마지막 25는 25=5*5로써 5가 한개 더 있다.
    • 따라서 5로 25를 나눠주면?? 1~25 곱 사이의 5가 나온 개수가 총 출력되지만
    • 25(=5*5) 의 경우엔 5가 2개이지만 이때 1개만 카운트 된다
      => 즉, 1개 카운트가 부족함
    • 이때 25를 25(=5*5) 로 또 나누어주면 1~25 사이의 25가 나온 개수가 출력되어서 => 위에서 부족한 카운트 1개가 보충 될 수 있다.
    • 해당 원리를 이용한다면?
      • EX) 5의 개수 : 25/5 = 5, 25/25 = 1 => 총 6개

조합

조합의 공식 : nCr = n!/[(n-r)!r!]

• 물론 이 조합을 DP로 구하던 방식도 있음!! (생각보다 간단)

A진법 to B진법(=A진수 to B진수)의 변환과 관계

필자는 이것을 A진법 -> 10진법 -> B진법 의 변화로 해결하고 있다.

• A진법 -> 10진법
  • 예로 2진법이라면??
    • 먼저, 10진수 값이 10 이였다면 이를 2진법으로 표현 했을때는 1010이다.
      • 1010 의 일의 자리 수를 10진수로 표현하면 0*2^0 = 0 이다.
      • 1010 의 십의 자리 수를 10진수로 표현하면 1*2^1 = 2 이다.
      • 1010 의 백의 자리 수를 10진수로 표현하면 0*2^2 = 0 이다.
      • 1010 의 천의 자리 수를 10진수로 표현하면 1*2^3 = 8 이다.
    • 마지막으로 1010 을 10진수로 표현한다면??
      • 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3 = 0 + 2 + 0 + 8 = 10
• 10진법 -> B진법
  • 10진수를 B진법으로 계속 나누어서 나머지 값을 거꾸로 출력하는 방식이다.
  • 그림으로 참고(추천 URL) : 10진수 A,B 진법 관계

‘Base Conversion’ 풀이 게시글 참고