![](https://t1.daumcdn.net/keditor/emoticon/friends2/large/053.png)
생각해보니 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 이라고 한다.
시간은 이정도가 나왔다.
혹시나 싶어 소인수분해를 사용한 방법도 확인해봤다.
더 빠르다... 하지만 이 방법에 대해서는 이해를 제대로 못했기 때문에 기억만 해두고
유사한 문제가 또 나온다면 그 때 제대로 보도록 해야겠다.
'스파르타 내배캠' 카테고리의 다른 글
스파르타 내배캠 Unity 3기 - 46 (2) | 2024.03.07 |
---|---|
스파르타 내배캠 Unity 3기 - 45 (0) | 2024.03.05 |
스파르타 내배캠 Unity 3기 43일차 (0) | 2024.02.27 |
스파르타 내배캠 Unity 3기 42일차 (0) | 2024.02.23 |
스파르타 내배캠 Unity 3기 41일차 (0) | 2024.02.23 |