안녕하세요! 이번 강좌에서는 코틀린을 이용해 코딩테스트에서 자주 접할 수 있는 알고리즘 문제를 깊이 있게 다뤄보겠습니다. 주제는 ‘제곱이 아닌 수 찾기’입니다. 본 문제의 기본 아이디어는 주어진 수 내에서 제곱수(1, 4, 9, 16 등)들이 아닌 모든 수를 찾아내는 것입니다. 이 문제를 이해하고 해결하기 위해 필요한 알고리즘적 사고와 코틀린 문법을 함께 살펴보겠습니다.
문제 설명
문제는 다음과 같습니다:
제곱이 아닌 수 찾기
1부터 N까지의 자연수 중에서 제곱수가 아닌 수들을 모두 찾는 함수를 작성하시오.입력: 정수 N (1 ≤ N ≤ 1000)
출력: 제곱수가 아닌 수들의 리스트
문제 분석
이 문제를 해결하기 위해서는 다음과 같은 과정이 필요합니다:
- 1부터 N까지의 모든 자연수를 반복문을 통해 탐색
- 각 수가 제곱수인지 확인하는 방법 구상
- 제곱수가 아닌 수들을 리스트에 저장
제곱수는 1, 4, 9, 16, 25, … 의 형태로 나타나며, 이러한 수들은 i의 제곱으로 표시됩니다. 그러므로 i가 1에서 시작하여 √N까지 증가하면서 그 값을 제곱한 결과를 리스트에 저장할 수 있습니다. 그 후, 이 제곱수들을 제외한 나머지 수들을 결과 리스트에 포함시키면 됩니다.
알고리즘 설계
위의 과정을 토대로 아래와 같은 알고리즘을 설계할 수 있습니다:
- 빈 리스트를 생성한다.
- 1부터 N까지 반복문을 돌린다.
- 각 수가 제곱수인지 판별한다.
- 제곱수가 아닐 경우 리스트에 추가한다.
- 결과 리스트를 출력한다.
코틀린 코드 구현
자 이제 이 알고리즘을 코틀린으로 구현해봅시다:
fun findNonPerfectSquares(n: Int): List {
val nonPerfectSquares = mutableListOf()
// 제곱수를 저장하기 위한 세트
val perfectSquares = mutableSetOf()
// 1부터 n의 제곱수 계산
for (i in 1..Math.sqrt(n.toDouble()).toInt()) {
perfectSquares.add(i * i)
}
// 1부터 N까지 탐색
for (i in 1..n) {
// 제곱수가 아닌 경우 리스트에 추가
if (i !in perfectSquares) {
nonPerfectSquares.add(i)
}
}
return nonPerfectSquares
} 위 코드에서 findNonPerfectSquares 함수는 입력으로 주어진 N까지의 자연수 중 제곱수가 아닌 수들을 리스트로 반환합니다. mutableSetOf를 사용하여 제곱수를 효율적으로 관리하고, 탐색의 복잡성을 줄였습니다.
코드 실행 및 결과
이제 작성한 코드를 테스트해보고 결과를 확인해 보겠습니다. 예를 들어, N을 20으로 설정하고 함수를 호출하면 다음과 같은 결과를 얻을 수 있습니다:
fun main() {
val n = 20
val result = findNonPerfectSquares(n)
println("1부터 $n까지의 제곱이 아닌 수들: $result")
}위의 main 함수를 통해 결과를 출력하면 다음과 같습니다:
1부터 20까지의 제곱이 아닌 수들: [2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20]복잡도 분석
이번 문제의 시간복잡도를 살펴보면:
- 제곱수를 계산하는 for문: O(√N)
- N까지의 반복문에서 제곱수 체크: O(N)
따라서 전체 시간복잡도는 O(√N + N) = O(N)입니다.
정리
이번 강좌에서는 제곱이 아닌 수를 찾는 알고리즘 문제를 다뤘습니다. 문제의 구조를 이해하고 이를 코틀린으로 구현하면서 제곱수의 개념과 효율적으로 데이터를 관리하는 방법에 대해서도 배웠습니다. 코딩테스트에서 자주 출제되는 문제가 유형인 만큼 실제 문제를 풀어가는 과정처럼 접근하는 것이 중요합니다. 궁금한 점이나 추가적으로 알고 싶은 내용이 있다면 댓글로 남겨주세요! 앞으로도 유익한 알고리즘 강좌를 기대해 주세요!