문제 설명
우리는 주어진 정수 N에 대해 1부터 N번째 정수까지의 수 중에서 완전 제곱수가 아닌 수의 개수를 찾으려고 합니다. 완전 제곱수란 어떤 정수를 제곱해서 얻은 수를 의미합니다. 예를 들어, 1, 4, 9, 16, 25 등은 모두 완전 제곱수입니다. 반면에 2, 3, 5, 6, 7, 8, 10 등은 완전 제곱수가 아닙니다.
입력 형식
첫 번째 줄에는 정수 N (1 ≤ N ≤ 106)이 주어집니다.
출력 형식
1부터 N까지의 수 중에서 완전 제곱수가 아닌 수의 개수를 출력합니다.
예제 입력
10
예제 출력
7
문제 해결 과정
이 문제를 해결하기 위해서는 전체 수의 개수에서 완전 제곱수의 개수를 빼면 됩니다. 이를 위해 다음과 같은 절차를 따릅니다.
1단계: 완전 제곱수의 범위 파악
완전 제곱수는 1, 4, 9, 16, … 등의 형태로 생성됩니다. N이 10인 경우, 완전 제곱수는 1(12), 4(22), 9(32)가 됩니다. 이 경우, 완전 제곱수는 총 3개입니다.
2단계: 완전 제곱수의 개수 계산
N에 대해 어떤 정수 k에 대해 k2 <= N을 만족하는 최대의 k를 찾으면 됩니다. 이 k는 √N의 정수 부분으로 계산할 수 있습니다.
3단계: 결과 도출
전체 수의 개수는 N이며, 완전 제곱수의 개수는 k입니다. 따라서 제곱이 아닌 수의 개수는 N - k로 계산할 수 있습니다.
구현 코드 (Swift)
func countNonPerfectSquares(N: Int) -> Int {
// 1부터 N까지의 수에서 완전 제곱수를 찾기 위해 k를 구합니다.
let k = Int(sqrt(Double(N)))
// 완전 제곱수가 아닌 수의 개수를 구합니다.
return N - k
}
// 예시 실행
let N = 10
print(countNonPerfectSquares(N: N)) // 결과: 7
복잡도 분석
이 알고리즘은 O(1)의 시간 복잡도를 가집니다. 주어진 N에 대해서 제곱근을 구하는 연산은 상수 시간에 이루어지므로 매우 효율적입니다. 메모리 사용 또한 상수로 제한되어 있으므로, 이 문제는 대규모 입력에서도 안정적으로 작동합니다.
사후 분석
이 문제를 통해 우리는 완전 제곱수에 대한 개념과 함께 제곱근 계산의 효율성을 이해할 수 있었습니다. 또한, 매우 간단한 계산을 통해 복잡한 문제를 해결하는 방법을 배웠습니다.
마무리
알고리즘 문제를 해결하는 과정에서는 문제를 이해하고, 해결책을 단계별로 세우며, 효율적으로 구현하는 것이 중요합니다. 이러한 과정은 여러 가지 유형의 알고리즘 문제를 다루는 데 큰 도움이 될 것입니다. 다음 강좌에서는 더욱 복잡한 알고리즘 문제를 다뤄 볼 예정입니다. 감사합니다!