배열로 표현되는 숫자란, 숫자의 각 자릿수를 배열의 개별 요소 하나씩에 나누어 저장하는 방식을 말합니다. 배열의 길이는 숫자의 자릿수와 같습니다. 예를 들어 네 자리 숫자라면 배열의 길이는 4가 됩니다. 배열의 모든 요소는 반드시 한 자리 숫자(0~9)여야 하며, 마지막 요소에는 가장 작은 자릿수(일의 자리)가, 첫 번째 요소에는 가장 큰 자릿수(최상위 자릿수)가 저장됩니다.
배열 표현 방식의 예
숫자 351932는 다음과 같이 저장됩니다.
{3, 5, 1, 9, 3, 2}1을 더하는 알고리즘의 동작 원리
배열로 표현된 숫자에 1을 더하려면 다음 절차를 따릅니다.
먼저 배열의 마지막 요소(일의 자리)에 1을 더한 뒤, 올림수(carry)가 발생했는지 확인해야 합니다. 만약 일의 자리 숫자가 9였다면 1을 더하는 순간 올림수가 발생하고, 해당 요소의 값은 0으로 바뀝니다.
올림수가 발생했다면 바로 앞자리, 즉 (n-1) 위치의 요소를 1 증가시키고 다시 올림수 발생 여부를 검사합니다. 이 과정은 올림수가 더 이상 발생하지 않을 때까지 왼쪽 자릿수 방향으로 반복됩니다.
예를 들어 {3, 5, 7, 9}에 1을 더하면 결과는 {3, 5, 8, 0}이 됩니다. 일의 자리 9에 1을 더해 올림수가 발생했고, 그 앞자리의 7이 8로 증가한 것입니다.
만약 모든 자릿수가 9인 경우(예: {9, 9, 9})에는 올림수가 최상위 자릿수까지 전파되므로, 배열 맨 앞에 새로운 자릿수 1을 삽입해야 합니다. 즉 {9, 9, 9}는 {1, 0, 0, 0}이 됩니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void addone(vector<int> &a) {
int n = a.size();
// 일의 자리에 1을 더함
a[n-1] += 1;
int carry = a[n-1] / 10;
a[n-1] = a[n-1] % 10;
// 올림수를 왼쪽 자릿수로 전파
for (int i = n-2; i >= 0; i--) {
if (carry == 1) {
a[i] += 1;
carry = a[i] / 10;
a[i] = a[i] % 10;
}
}
// 모든 자릿수가 9였던 경우, 맨 앞에 1 추가
if (carry == 1)
a.insert(a.begin(), 1);
}
int main() {
vector<int> num{2, 3, 9, 9};
cout << "원래 숫자 : ";
for (int i = 0; i < num.size(); i++)
cout << num[i];
cout << endl;
addone(num);
cout << "1을 더한 값 : ";
for (int i = 0; i < num.size(); i++)
cout << num[i];
return 0;
}실행 결과
원래 숫자 : 2399 1을 더한 값 : 2400
코드 설명
위 코드의 addone 함수는 다음 단계로 동작합니다.
1단계: 마지막 요소에 1을 더하고, 10으로 나눈 몫을 올림수로, 나머지를 해당 자릿수의 새로운 값으로 저장합니다.
2단계: 올림수가 존재하는 동안 왼쪽 자릿수로 이동하며 같은 연산을 반복합니다.
3단계: 루프가 끝난 후에도 올림수가 남아 있다면, 이는 모든 자릿수가 9였다는 의미이므로 insert 함수를 사용해 배열 맨 앞에 1을 추가합니다.
이 알고리즘의 시간 복잡도는 올림수가 전파되는 자릿수에 비례하며, 최악의 경우(모든 자릿수가 9) O(n), 일반적인 경우에는 O(1)에 가깝게 동작합니다. 정수형 변수의 오버플로 한계를 넘는 매우 큰 숫자를 다룰 때 이러한 배열 기반 연산 방식이 유용하게 활용됩니다.