알고리즘 공부/강의 - 1. 기본 산수

알고리즘을 공부하면서 알고리즘의 종류가 매우 많다는 것을 알게 되었다. 하지만 백준 알고리즘 사이트(www.acmicpc.net/), 또는 코드 플러스 같은 강의 사이트를 보면 문제의 종류가 정해져 있다는 것을 알 수 있다.

 

이번에는 기본적인 산수문제를 어떻게 하면 깔끔(?)하거나 빠르게 풀 수 있는지를 알아보자.

 

알고리즘을 공부하면 가장 먼저 보는 문제의 종류가 있다. 백준 알고리즘 사이트에서는 수학으로 분류된 문제이다.

(www.acmicpc.net/problemset?sort=ac_desc&algo=124)

처음에는 간단한 계산 문제처럼 보이지만 나중에는 좀 생각하고 풀어야하는 문제들이 많은데 그중에서도 좀 어려운 유형을 분류해보았다.

 

1.  기본 산수

1부터 n까지 더한 값, 곱한값, 팩토리얼, 등등 기본적인 산수를 물어보거나 약수의 개수, 소수 등 특징적인 숫자를 묻는 문제이다. 이런 문제들은 유형을 외워서 생각하는 시간도 아깝게 풀어버리면 편하다.

 

예를 들면 팩토리얼은 재귀함수 형태로 만들면 쉽게 구할 수 있다. 마치 처음 c언어 시작하면 #include<stdio.h> 쓰는 것처럼 외우면 자연스럽게 나온다.

ex)

int factorial(int x)

{

    if(x==1)

        return 1;

    if(x>1)

       return x*factorial(x-1);  //x*(x-1)*(x-2)*...*1이 된다.

}

하지만 팩토리얼 문제 중에 팩토리얼의 약수, ~의 갯수 등을 구하는 문제가 나오면 팩토리얼의 특성을 구해서 풀어야 한다. 왜냐하면 팩토리얼은 기본적으로 숫자가 커지기 때문에 50!같은 경우는 unsigned int에 들어가지도 않는다. 그런데 숫자의 범위가 1000까지라고 한다면 아마 코테 시간동안 1000!을 돌리지도 못할 것 같다. 이런 경우는 1*2*...*n이라는 특성을 가지고 for문을 돌려 풀어야 한다.

ex) 

for(int i=2;i<n;i++)    //2부터 시작

{

    tmp=i;   // i가 바뀌면 안되므로 tmp에 저장

    while(1)

    {

        if(tmp%5==0)

        {

            cnt++;

 

        }

 

        tmp = tmp/5;

        if(tmp<=1)

             break;

    }

    

}

이런 식으로 팩토리얼의 약수 중 5의 갯수를 구한다든가 할 수 있다.

 

 

 

 

약수의 갯수는 그냥 구하기는 쉽지만 빠르게 구하는 방법이 하나 있다. 바로 약수는 2개씩 짝지어진다는 점이다.

예를 들면 6의 약수는 2와 3이 있는데 2는 무조건 3이랑 짝지어진다는 점이다. 즉 하나의 약수는 다른 하나와 짝지어진다. 그런데 2의 제곱은 4로 6보다 작으므로 6은 2가 아닌, 2와 짝지어지는 다른 하나의 약수가 더 있다는 사실을 알 수 있다.

그러면 9는 어떨까? 9는 1과 3과 9가 약수인데, 3의 제곱이 9가 되므로 3은 짝이 3으로 중복이 되므로 약수가 1개이다.

이 사실을 바탕으로 코드를 작성할 수 있다.

ex)

for(int i=1;i*i<=n;i++) // i제곱이 n보다 작거나 같은 경우만 돌아감.

{

    if(n%i==0) // i가 약수일 때.

    {

        cnt++;

        if(i*i<n) // i가 중복이 안되고 하나의 쌍을 가질 때.

           cnt++; // 한 번 더 카운트 

    }

}   

이렇게 하면 cnt가 약수의 개수가 된다. 1과 자기 자신 포함. 이렇게 코드를 작성하면 i가 1부터 n이 아닌 1부터 n/2만 탐색을 하므로 절반의 시간 이득이 생긴다.

 

이렇게 기본 산수문제는 문제를 많이 풀다보면 생기는 몇 가지를 외워서 빠르게 풀면 시간 단축을 할 수 있다. 

 

 

※틀린 부분은 댓글로 올려주시면 수정하겠습니다. ^^