캐리를 전파하지 않고 두 수를 더하는 방법

이번 글에서는 두 개의 n자리 숫자를 더하되, 자릿수 올림(캐리)을 다음 자릿수로 전파하지 않는 흥미로운 문제를 살펴보겠습니다. 일반적인 덧셈과 어떻게 다른지 예시를 통해 먼저 이해해 보겠습니다.

문제 이해하기

예를 들어 7583과 9642를 더한다고 가정해 보겠습니다. 각 자릿수끼리만 독립적으로 더하면 다음과 같습니다.

일의 자리: 3 + 2 = 5
십의 자리: 8 + 4 = 12
백의 자리: 5 + 6 = 11
천의 자리: 7 + 9 = 16

따라서 최종 결과는 1611125가 됩니다. 일반적인 덧셈이라면 12나 11처럼 두 자릿수가 되는 경우 캐리를 넘겨주어야 하지만, 이 문제에서는 각 자릿수의 합이 그대로 결과에 이어 붙여집니다.

핵심 아이디어

여기에는 한 가지 트릭이 숨어 있습니다. 바로 숫자를 오른쪽에서 왼쪽으로 스캔해야 한다는 점입니다. 즉, 3+2=5와 같은 일의 자리 계산이 가장 먼저 수행되지만, 실제 결과에서는 가장 끝에 배치되어야 합니다. 이러한 역순 처리를 위해 스택(Stack)을 사용하여 중간 결과를 저장합니다.

알고리즘

noPropagateCarry(a, b)

a와 b의 길이 중 더 큰 값을 size로 지정합니다.
size번 반복하면서 a와 b의 마지막 자릿수를 각각 구합니다.
두 자릿수의 합을 스택에 push합니다.
a와 b를 10으로 나누어 다음 자릿수로 이동합니다.
모든 자릿수를 처리한 후, 스택에서 요소를 하나씩 pop하며 출력합니다.

begin
   size = max of length of a and length of b
   for i in range i to size, do
      al := last digit of a
      bl := last digit of b
      push (al + bl) into stack
      a := a / 10
      b := b /10
   done
   pop and print the elements from stack
end

C++ 구현 예제

#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
int length(int n){
   return log10(n) + 1;
}
void noPropagateCarry(int a, int b){
   int size = max(length(a), length(b));
   stack<int> stk;
   for(int i = 0; i <size; i++){
      int al = a % 10; //a의 마지막 자릿수
      int bl = b % 10; //b의 마지막 자릿수
      stk.push(al + bl);
      a = a / 10; b = b/10;
   }
   while(!stk.empty()){
      cout << stk.top();
      stk.pop();
   }
}
main() {
   int a = 7583, b = 9642;
   cout << "Result: ";
   noPropagateCarry(a, b);
}

실행 결과

Result: 1611125

복잡도 분석

시간 복잡도: O(n) — 각 자릿수를 한 번씩만 처리합니다. (n은 두 수 중 긴 자릿수)
공간 복잡도: O(n) — 중간 결과를 저장하기 위한 스택 공간이 필요합니다.

이처럼 스택의 LIFO(Last-In-First-Out) 특성을 활용하면, 오른쪽부터 계산된 자릿수 합들이 자연스럽게 왼쪽에서 오른쪽 순서로 출력됩니다. 캐리 전파 없이 자릿수별 덧셈 결과를 얻어야 하는 다양한 응용 상황에서 유용하게 활용할 수 있는 기법입니다.