문제 설명
“좋은 수”란 주어진 수 N의 모든 약수 중에서 홀수인 약수를 의미합니다. 여러분의
목표는 주어진 수 N이 있을 때, N의 모든 홀수 약수를 찾아내는 것입니다.
예를 들어, N이 12라면, 이 수의 약수는 1, 2, 3, 4, 6, 12이며,
그 중 홀수 약수는 1과 3입니다. 이 문제에서 주어진 수의 홀수 약수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
입력 형식
입력은 정수 N(1 ≤ N ≤ 10^6)입니다.
출력 형식
N의 홀수 약수를 오름차순으로 한 줄에 출력합니다.
홀수 약수가 없는 경우 “홀수 약수가 없습니다.” 라고 출력합니다.
예시 입력 및 출력
입력:
12
출력:
1 3
입력:
7
출력:
1 7
문제 풀이
단계 1: 문제 이해하기
문제를 해결하기 위해서는 먼저 주어진 수 N의 약수를 정확히 정의할 필요가 있습니다.
약수는 어떤 수를 나누었을 때 나머지가 0이 되는 수를 의미합니다.
예를 들어 N이 12일 때, 약수는 12를 나눌 수 있는 모든 수입니다.
단계 2: 약수를 찾는 방법
N의 모든 약수를 찾기 위해서는 1부터 N까지 반복하면서, N을 현재의 수로 나누어
나머지가 0인지 확인하면 됩니다.
방법:
– 1부터 N까지의 모든 정수를 반복합니다.
– 현재의 수 i로 N을 나누었을 때 나머지가 0이라면 i는 N의 약수입니다.
– 추가로, i가 홀수인지도 체크해야 하므로, 홀수일 경우에만 리스트에 저장합니다.
단계 3: 홀수 약수 저장 및 출력
홀수 약수를 저장하는 리스트를 만든 후, 이 리스트를 오름차순으로 정렬하고 출력합니다.
만약 리스트가 비어있다면 “홀수 약수가 없습니다.”라는 메시지를 출력하도록 합니다.
단계 4: C# 코드 구현
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
List oddDivisors = new List();
for (int i = 1; i <= N; i++)
{
if (N % i == 0 && i % 2 != 0)
{
oddDivisors.Add(i);
}
}
if (oddDivisors.Count == 0)
{
Console.WriteLine("홀수 약수가 없습니다.");
}
else
{
oddDivisors.Sort();
Console.WriteLine(string.Join(" ", oddDivisors));
}
}
}
코드 설명
1. 입력 받기
<code>int N = int.Parse(Console.ReadLine());</code>
부분은 사용자로부터 정수 N을 입력받는 부분입니다. Console.ReadLine() 메서드는
사용자가 입력한 값을 문자열로 읽어온 후, int.Parse() 메서드를 통해 정수로 변환합니다.
2. 홀수 약수 찾기
<code>for (int i = 1; i <= N; i++)</code>부터 시작하여, 1부터 N까지
반복문을 실행합니다. 그리고 <code>if (N % i == 0 && i % 2 != 0)</code> 구문을 통해
N이 i로 나누어떨어지면서, i가 홀수인지 체크합니다. 두 조건을 만족하면, i를
홀수 약수 리스트에 추가합니다.
3. 결과 출력
마지막으로 홀수 약수 리스트의 길이를 체크하여, 약수가 없으면 “홀수 약수가 없습니다.”라고
출력하고, 약수가 있을 경우 오름차순으로 정렬한 후 리스트를 공백으로 구분하여 출력합니다.
여기서 <code>string.Join(” “, oddDivisors)</code> 구문은 리스트의 값을 문자열로
변환하여 출력합니다.
성능 분석
위 알고리즘의 시간 복잡도는 O(N)입니다. 이는 N이 최대 10^6이므로, 느리게 느껴질 수 있습니다.
그러나 주어진 입력값의 범위를 고려했을 때, 일반적으로는 충분히 빠르게 계산되는 편입니다.
추가적으로 성능을 개선하기 위한 방법으로는 약수를 찾는 범위를 N의 제곱근으로 줄이는 것이 있습니다.
이렇게 하면 시간 복잡도를 O(√N)으로 감소시킬 수 있습니다.
더 나아가기: N의 홀수 약수 구하기 최적화
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
List oddDivisors = new List();
for (int i = 1; i * i <= N; i++)
{
if (N % i == 0)
{
if (i % 2 != 0)
{
oddDivisors.Add(i);
}
int pairedDivisor = N / i;
if (pairedDivisor != i && pairedDivisor % 2 != 0)
{
oddDivisors.Add(pairedDivisor);
}
}
}
if (oddDivisors.Count == 0)
{
Console.WriteLine("홀수 약수가 없습니다.");
}
else
{
oddDivisors.Sort();
Console.WriteLine(string.Join(" ", oddDivisors));
}
}
}
이 코드에서는 1부터 N의 제곱근까지 반복하면서 각 i에 대해 i와 N/i 쌍의 약수를
동시에 검사하게 됩니다. 이렇게 하면 효율성을 높일 수 있습니다.
마무리
본 글에서는 C#을 이용하여 주어진 정수 N의 홀수 약수를 찾는
알고리즘 문제를 풀어보았습니다. 문제 풀이 과정은 단계별로 세분화하여 설명하였고,
최적화를 통한 코드 개선 방법도 제시하였습니다. 이러한 과정은 코딩 테스트나 알고리즘
스킬을 향상시키는 데에 도움이 될 것입니다.