이번 장에서는 흥미로운 문제 하나를 살펴보겠습니다. 하나의 숫자가 주어졌을 때 이 숫자를 1만큼 증가시키는 것은 겉보기에 아주 간단한 작업입니다. 하지만 여기서는 숫자를 배열 형태로 다룬다는 점이 핵심입니다. 숫자의 각 자릿수가 배열의 개별 요소로 저장되며, 예를 들어 숫자가 512라면 {5, 1, 2}와 같이 저장됩니다. 또한 반복문 대신 재귀(recursion) 방식을 사용하여 이 숫자를 1 증가시켜야 합니다. 그럼 알고리즘을 통해 구체적인 동작 과정을 살펴보겠습니다.
알고리즘
increment(arr, n, index)
index의 초기 기본값은 0입니다.
begin if index < n, then if arr[index] < 9, then arr[index] := arr[index] + 1 else arr[index] := 0 increment(arr, n, index + 1) end if if index = n, then arr[n] := 1 n := n + 1 end if end
동작 원리: 가장 낮은 자릿수부터 확인하여 해당 자릿수가 9보다 작으면 단순히 1을 더합니다. 만약 자릿수가 9라면 그 자릿수를 0으로 바꾸고, 바로 앞쪽 자릿수에 대해 재귀 호출을 수행합니다. 이는 실제 손으로 계산할 때 발생하는 올림(carry) 처리와 정확히 같은 논리입니다. 만약 모든 자릿수가 9였다면(예: 999) 재귀 호출이 배열의 끝(index == n)에 도달하게 되며, 이때 맨 앞에 새로운 자릿수 1을 추가하고 배열의 길이 n을 1 늘려줍니다.
예제
#include <iostream>
#include <cmath>
#define MAX 20
using namespace std;
void increment(int num_arr[], int &n, int index = 0){
if(index < n){
if(num_arr[index] < 9){ //자릿수가 9보다 작으면 1을 더함
num_arr[index]++;
}else{ //자릿수가 9이면 0으로 바꾸고 재귀 호출로 올림 처리
num_arr[index] = 0;
increment(num_arr, n, index+1);
}
}
if(index == n){
num_arr[n] = 1; //새로운 올림 자릿수 추가
n++; //배열 길이 증가
}
}
void dispNumber(int num_arr[], int n){
for(int i = n-1; i>= 0; i--){
cout << num_arr[i];
}
cout << endl;
}
int numToArr(int num_arr[], int number){
int i = 0;
int n = log10(number) + 1;
for(i = 0; i< n; i++){
num_arr[i] = number % 10;
number /= 10;
}
return n;
}
int main() {
int number = 1782698599;
int num_arr[MAX];
int n = numToArr(num_arr, number);
cout << "Initial Number: "; dispNumber(num_arr, n);
increment(num_arr, n);
cout << "Final Number: "; dispNumber(num_arr, n);
}
출력 결과
Initial Number: 1782698599 Final Number: 1782698600
위 예제에서 초기 숫자 1782698599는 마지막 두 자릿수가 연속된 9이므로, 1을 더하는 과정에서 올림이 두 번 발생하여 최종적으로 1782698600이 출력됩니다. 이처럼 재귀 호출을 활용하면 복잡한 올림 로직도 간결하게 처리할 수 있습니다.