modern cpp challenge 책의 문제들을 푸는 과정을 작성해놓으려 한다.
1. 문제
2. 풀이(1)
2.1. I/O
2.2. 연산
2.3. 코드
3. 코드 수정
3.1. I/O 타입
3.2. 연산 방법
3.3. 구현
3.4. 결론
4. 결론
1. 문제
암스트롱 수 출력 프로그램 구현하기
모든 세 자리 암스트롱 수를 출력하라.
2. 풀이(1)
필요한 코드 구조는 아래와 같다.
암스트롱 수 구하는 부분 + 답 출력하는 부분
암스트롱 수 구하는 부분과 출력 부분을 따로 설정하기로 했다.
출력 부분이 간단하지만, 출력하는 상황에서 다른 기능이 추가되어 처리할 수도 있기 때문에 따로 해당 부분을 분리하여 작성한다.
2.1. I/O
암스트롱 수는 어떤 n자리 양의 정수에서 각 자리 숫자를 n번 거듭제곱하여 더한 값이 자신이 되는 수이다. 예시로 153은 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153으로 암스트롱 수이다.
그러므로 세 자리인 양의 정수로 값이 정해져 있고, 최대값 999의 경우 각 숫자들의 합이 3 * (9 ^ 3) = 2187이다. 그러므로 주어진 연산 안에서 계산하고, 양의 정수라는 것을 명시하기 위해 데이터 타입은 unsigned int를 사용할 것이다.
2.2. 연산
우선 1~9까지 세제곱한 값을 담은 배열을 만든다. 그리고 수를 분해하고, 분해한 값을 배열에 대칭해 값들을 더한 후 원래 수와 대칭해서 구하는 방식이다.
세 자릿수를 분해하는 법은 2가지가 있다. 첫 번째는 문자열로 처리한 뒤 해당 문자열을 각각 분리하고, unsigned int로 바꾼 후 계산하는 것이고 두 번째는 해당 수의 나머지를 구해 계산하는 방법이 있다. 문자열로 처리하는 방법은 나머지 연산보다 연산량이 많고 느리기 때문에 나머지 연산을 사용하기로 했다.
2.3. 코드
처음에 작성한 코드는 아래와 같다.
#include <iostream>
void set_cubic_array(unsigned int cubic_array[]) {
for(unsigned int i = 1; i < 10; i++) {
cubic_array[i] = i * i * i;
}
}
void print_narcissistic_number(unsigned int n) {
std::cout << n << '\n';
}
void compute_narcissistic_number(unsigned int start, unsigned int end) {
unsigned int cubic_array[10];
set_cubic_array(cubic_array);
for(unsigned int i = start; i < end; i++) {
unsigned int n = i;
unsigned int sum = 0;
while(n > 0) {
unsigned int digit = n % 10;
sum += cubic_array[digit];
n /= 10;
}
if(sum == i)
print_narcissistic_number(i);
}
}
int main() {
unsigned int start = 100;
unsigned int end = 1000;
compute_narcissistic_number(start, end);
}출력 부분을 함수 콜백때문에 반복문 안에서 처리할까 했지만 기능을 따로 분리해서 작성하는 게 낫다고 생각해서 따로 나눴다.
각 함수별로 기능을 따로 나누고, 시작과 끝 변수를 처리해서 해당 함수에 넣어서 처리했다.
시간복잡도는 O(1)이다.
3. 코드 수정
핵심 로직의 시간복잡도가 아닌 디테일을 수정하려고 한다.
3.1. I/O
크게 수정하지 않았다.
3.2. 연산 방법
핵심 로직은 크게 수정하지 않았다.
3.3. 구현
나는 세 자리수 기준으로 계산했는데, 세 자리 수는 각 자릿수 세제곱의 합이 999보다 커서 위와 같이 계산해도 되었지만, 네 자리수의 경우는 최대값 9999의 자릿수 네제곱 합이 26244로 해당 범위를 넘어서는 수는 확인할 필요가 없다. 자릿수가 일반화될 경우에는 위와 같이 처리하는 것이 효율적이다.
또한 cubic_array를 만드는 과정에서도 자릿수를 입력받는 경우가 아니면 미리 캐싱해서 넣어놓는 것이 더 효율적일 수 있다. pow함수를 쓸 수 있지만, 캐싱해서 미리 저장해놓는 것이 가장 효율적이라 생각된다.
constexpr std::array<unsigned, 10> CUBE = {
0, 1, 8, 27, 64, 125, 216, 343, 729
};
3.4. 결론
전체 코드는 크게 수성하지 않았다. 현재 배우는 입장이란 관점에서 코드의 확장성과 기능 분리에 초점을 두는 게 좋을 것 같다는 생각이 들었기 때문이다.
4. 후기
시간복잡도도 상수고 연산이 상대적으로 간단한 문제 같은 경우는 구현을 어떻게 해야 할 지 고민되는 부분이 있다. 코드를 확장성 있게 짤 것인지 아니면 캐싱해놓고 최대한 최적화를 하도록 처리할지. 이게 현재 문제에서 어디에 우선순위를 둘 건지가 중요한 것 같은데 그것은 또 같이 짜는 사람들이 있을 경우 집단 내 지향하는 방향에 따라 달라질 것 같다. 현재 이렇게 혼자 하는 경우도 빠른 최적화를 위해서는 간단히 써야겠지만 현재 나는 코드를 다시 짜보며 배우고 있으니 차근차근 기능 확장의 개념에서 바라보면서 코딩하는 게 좋을 것 같다. 물론 각 방법별로 걸리는 시간이 빠른지 느린지에 대해서도 알아보면서 말이다.