[Algorithm] 외워서 사용하자

🤖 Algorithm

---

외워서 사용할 알고리즘

🟦 최대공약수, 최소공배수 - 호제법

2개의 자연수 a, b가 존재할 때 a, b의 최대 공약수를 구하는 방법

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

2개의 자연수 a, b가 존재할 때 a, b의 최소 공배수를 구하는 방법

int lcm(int a, int b)
{
	return (a / gcd(a,b)) * (b / gcd(a,b)); 
}

🟦 소수 구하기 - 에라테네스의 체

n의 소수를 구할 때에는 sqrt(n)까지만 보면 된다.
이렇게 해도 시간초과가 나는 경우가 있으므로 에라테네스의 체를 활용한다.

	vector<int> isPrime;
 	isPrime.resize(N+1,1);

    isPrime[0]=0;
    isPrime[1]=0;

    // 에라토스테네스의 체
    // 소수 판별은 제곱근까지만 보면 됨
	for (int i = 2; i<=sqrt(N); i++)
	{
        // 소수가 아님으로 판정된 수면 continue
		if(!isPrime[i])
        {
            continue;
        }
        // 현재 값만큼 뛰면서 체크
        for(int j=i+i;j<=N;j+=i)
        {
            isPrime[j]=false;
        }
        
	}

    for(int i=2;i<=N;i++)
    {
        if(isPrime[i])
        {
            primeNums.push_back(i);
        }
    }

🟦 그래프 - 유니온 파인드

유니온 - 집합을 합침
파인드 - a가 속한 집합 A의 대표 노드를 반환
=> 두 노드가 연결되어있는지 판단 하는데 사용 + 사이클 여부 판단

초기에 idx와 value가 같은 배열을 선언

find를 하며 각 노드를 연결

// 배열 초기화
vector<int> nodes(N+1);
for(int i=1; i<=N;i++)
{
	nodes[i]=i;
}

// 파인드
int find(int num)
{
	if(num==nodes[num])
    {
    	return num;
    }
    
    else
    {	
    	// value값을 idx로 하여 다시 대표 노드를 찾음 + 경로 압축
    	return nodes[num] = find(nodes[num]);
    }
}

// 유니온
void union(int a, int b)
{
	if(find(a)>find(b))
    {
    	nums[find(a)]=nums[find(b)];
    }
    
    else
    {
    	nums[find(b)]=nums[find(a)];
    }
}

find(a) == find(b) => 사이클 존재
둘은 연결되어 있음

🟦 플로이드 워셜

노드 개수가 100 단위일 때만 가능 (3중 루프)

1-->7 최단 경로가 1-2-4-7 이라면
1-->4 최단 경로는 1-2-4 일 것

이 원리로 DP를 만듦

인접 행렬사용

idx i==j -> 0, 나머지는 무한대로 초기화

for(int k=1;k<=N;k++)
{	
	for(int i=1;i<=N;i++)
    {	
    	for(int j=1;j<=N;j++)
   		{
        	if(distance[i][j]>distance[i][k]+distance[k][j])
            	distance[i][j]=distance[i][k]+distance[k][j];
        }
    }
}

🟦 long long 범위를 넘어서는 경우

string으로 변환하여 덧셈을 수행하자

string add(string n1, string n2)
{
    string res="";

    int sum=0;

    while(!n1.empty()||!n2.empty()||sum)
    {
        if(!n1.empty())
        {
            sum+=n1.back()-'0';
            n1.pop_back();
        }
        if(!n2.empty())
        {
            sum+=n2.back()-'0';
            n2.pop_back();
        }
        res.push_back((sum%10)+'0');
        sum/=10;
    }
    reverse(res.begin(),res.end());
    return res;
}