1. 소개
알고리즘 문제 풀이는 취업 준비에 있어 매우 중요한 요소입니다. 오늘은 많은 개발자들이 마주하는 ‘좋은 수’ 구하기 문제에 대해 깊이 있게 살펴보겠습니다. ‘좋은 수’란 어떤 수를 특정 조건 하에서 구하는 것을 의미하며, 이 문제를 통해 사고력을 키우고 실력을 향상시킬 수 있습니다.
2. 문제 설명
당신은 정수 n을 입력받습니다. n보다 작거나 같은 모든 수 중에서, 각 자릿수의 합이 10 이하인 수를 ‘좋은 수’라고 정의합니다.
예를 들어, 23은 좋은 수이지만 24는 2+4=6으로 좋은 수가 아닙니다. 문제는 주어진 n 이하의 ‘좋은 수’를 모두 구하는 것입니다.
2.1. 입력
정수 n (1 <= n <= 10000)
2.2. 출력
n 이하의 ‘좋은 수’를 출력합니다.
3. 접근 방법
이 문제를 해결하기 위해서는 다음과 같은 접근 방법을 사용할 수 있습니다.
- 1부터 n까지의 수를 반복하여 각 수의 자릿수를 분리합니다.
- 각 자릿수들의 합을 계산합니다.
- 자릿수 합이 10 이하인 경우 ‘좋은 수’로 판단하여 출력합니다.
3.1. 자릿수 합 구하기
자릿수 합을 구하는 방법으로는 수를 10으로 나누어 나머지를 구하는 방식을 사용할 수 있습니다. 예를 들어, 23을 나누면 3(23 % 10)과 2(23 / 10)로 나아갑니다.
이러한 과정을 통해 각 수의 자릿수를 파악하고 합을 계산할 수 있습니다.
4. 코드 구현
이제 위의 접근 방법을 기반으로 C++ 코드를 작성해보겠습니다. 아래는 ‘좋은 수’를 구하는 프로그램의 코드입니다.
#include
using namespace std;
bool isGoodNumber(int number) {
int sum = 0;
while (number > 0) {
sum += number % 10; // 현재 자릿수 더하기
number /= 10; // 다음 자릿수 계산
}
return sum <= 10; // 자릿수 합이 10 이하인지 체크
}
int main() {
int n;
cout << "정수를 입력하세요: ";
cin >> n;
cout << "좋은 수들: ";
for (int i = 1; i <= n; i++) {
if (isGoodNumber(i)) {
cout << i << " "; // 좋은 수 출력
}
}
cout << endl;
return 0;
}
5. 코드 설명
위 코드는 간단한 형태의 프로그램으로, ‘좋은 수’ 판단을 위한 isGoodNumber 함수와 메인 함수 main으로 구성되어 있습니다.
5.1. isGoodNumber 함수
이 함수는 정수를 입력으로 받아, 각 자릿수의 합을 계산한 후 그 결과에 따라 true 또는 false를 반환합니다.
반복문을 사용하여 수의 각 자릿수를 분리하고 합산합니다.
5.2. main 함수
메인 함수에서는 사용자로부터 n을 입력받고, 1부터 n까지의 수를 체크합니다. 각 수에 대해 isGoodNumber를 호출하여 좋은 수인지를 판단합니다.
6. 시간 복잡도
이 알고리즘의 시간 복잡도는 O(d * n)입니다. 여기서 d는 n의 자릿 수입니다.
각 수에 대해 자릿수를 더하는 것은 최대 4회 수행되므로 n이 커져도 실시간으로 대처할 수 있습니다.
7. 최적화
현재 코드는 모든 수를 고려하고 자릿수 합을 계산하므로 비효율적일 수 있습니다.
대신에 자릿수 합을 미리 계산하고 저장하여 중복 계산을 줄일 수 있습니다. 다음은 이를 위한 코드 개선 예시입니다.
#include
#include
using namespace std;
vector precomputeGoodNumbers(int maxNum) {
vector goodNumbers;
for (int i = 1; i <= maxNum; i++) {
if (isGoodNumber(i)) {
goodNumbers.push_back(i); // 좋은 수 저장
}
}
return goodNumbers;
}
int main() {
int n;
cout << "정수를 입력하세요: ";
cin >> n;
vector goodNumbers = precomputeGoodNumbers(n);
cout << "좋은 수들: ";
for (int number : goodNumbers) {
cout << number << " "; // 미리 저장된 좋은 수 출력
}
cout << endl;
return 0;
}
8. 결론
오늘은 ‘좋은 수’ 구하기 문제를 함께 살펴보았습니다. 이 문제는 기본적인 알고리즘 사고를 발전시키고 문제 해결 능력을 향상시키는 좋은 예제입니다.
앞으로도 다양한 문제를 통해 알고리즘 역량을 강화할 수 있도록 노력하시기 바랍니다. Happy coding!