스파르타 내배캠 Unity 3기 - 44

생각해보니 n일차가 아니잖아?

 

 

 

글을 쓸 때 마다 n일차 라고 제목을 쓰는데 단 하루도 빠짐없이 쓴게 아니라서...

이걸 n일차라고 하는게 잘못 됐다는걸 이제서야 인지했다;;

 

 

---

기사단원의 무기 - 알고리즘 (C#)

 

이제 슬슬 알고리즘에 정성을 들여야 할 때가 다가오는 것 같다.

 

이제껏 알고리즘 문제 관련해서 글을 쓴 적이 아마 없던 것 같으니

쓸게 없다면 알고리즘을 완전 이해 하도록 TIL을 써야겠다.

 

 

 

문제의 요지는 

 

기사단원 각 숫자의 약수의 개수를 구하고,

약수의 개수가 limit 보다 낮으면 n kg

약수의 개수가 limit 보다 높으면 limit kg 의 철의 무게를 가진다.

 

단순하게 생각하면 약수의 개수를 일단 구하면 되니 가장 접근하기 쉬운 방법으로 구했다.

 

// 함수 이름은 의미없다.
public static int solution1123(int number, int limit, int power)
        {
            int answer = 0;

            int[] powers = new int[number];            

            for (int i = 1; i <= number; i++)
            {
                int index = 1;
                while(index <= i)
                {
                    if (i % index == 0)
                        powers[i - 1]++;

                    index++;
                }                

                if (powers[i - 1] > limit)
                    powers[i - 1] = power;

                answer += powers[i - 1];
            }            

            return answer;
        }

 

일단 기사단원의 수 만큼 해당 숫자의 약수를 구해야 하니 for문은 반드시 들어가야 한다고 생각했고,

 

약수를 구해야하니 while문을 돌며 i 번째 단원의 수를 index 로 나눠 떨어지는 index를 약수로 구할 수 있어

 

        int index = 1;
        while(index <= i)
        {
            if (i % index == 0)
                powers[i - 1]++;

            index++;
        }

 

해당 코드를 작성했다.

 

결과적으로 틀리진 않았지만, 시간 초과가 나버렸다.

 

 

그렇다면 약수를 구하는 부분에서 문제가 있었다는건데...

 

솔직히 아무리 생각해도 어떻게해야 효율적으로 접근 가능한지 도저히 몰랐다.

아무래도 이 문제는 수학적 공식을 아느냐에 대한 문제가 아닐까 하는 생각이 들었다.

 

그럼 가장 효율적으로 약수를 구하는 방법은 무엇이었을까?

 

결국 인터넷 서칭을 여럿 했고 다양한 답을 얻었다.

 

공통적으로 제곱근, 소인수분해등의 키워드였고 그 중 내가 가장 잘 이해한 것을 사용했다.

 

 

int count = 0;

            for(int i = 1; i * i <= num; i++)
            {
                if (i * i == num)
                    count++;
                else if (num % i == 0)
                    count += 2;
            }

 

먼저 for 문을 돌며 약수의 시작인 1부터 i * i <= num 까지 (즉 num의 제곱근 이하 범위에서만 돈다) 차례로 돌며

 

만약 i * i == num 이면 n의 제곱근 이므로 count를 하나 더한다.

그게 아니라 만약 num % i == 0 이라면, 즉 num이 i 로 나눠 떨어지는 몫이 d 라고할 때 num / d 역시 약수이므로

count += 2 를 해준다.

 

이 방식은 모든 수를 하나씩 돌며 확인하는게 아니라 제곱근을 중간에 두고 반만 확인하는 방식이 된다.

시간복잡도는 O√n 이라고 한다.

 

 

시간은 이정도가 나왔다.

혹시나 싶어 소인수분해를 사용한 방법도 확인해봤다.

 

더 빠르다... 하지만 이 방법에 대해서는 이해를 제대로 못했기 때문에 기억만 해두고

유사한 문제가 또 나온다면 그 때 제대로 보도록 해야겠다.