C++ 알고리즘 알아두면 좋을 공식

가우스 공식

• 가우스 공식 자체는 알고 있지만, 뭔가에 홀린듯 for문을 돌려버리게 된다.

#include <string>
#include <vector>

using namespace std;

long long solution(int a, int b) {
    
    int bigNum = a > b ? a : b;
    int smallNum = a < b ? a : b;
    long long answer = 0;
    for(int i = smallNum; i <= bigNum; i++)
    {
        answer += i;
    }
    
    return answer;
}

• 두 정수 사이에 있는 모든 정수들을 다 더하는 공식

#include <string>
#include <vector>

using namespace std;

long long solution(int a, int b) {
    long long bigNum = a > b ? a : b;
    long long smallNum = a < b ? a : b;
    
    // 가우스 공식 적용
    long long answer = (bigNum - smallNum + 1) * (smallNum + bigNum) / 2;
    
    return answer;
}

• 이렇게 변경하면 성능으로도 가독성 면에서도 올라간다.

유클리드 호제법

• 최대 공약수를 구하는 공식

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

    return a;
}

• a와 b를 나눈 나머지 r을 계속 순환하여 최대공약수를 구하는 법이고,

int lcm(int a, int b) {
    return (a * b) / gcd(a, b); // LCM 공식 사용
}

• 바로 어렵지 않게 최소 공배수를 구할 수 있다.