[알고리즘] 문자배열을 이용한 큰 수 덧셈 - travelbeeee

안녕하세요, 여행벌입니다.

오늘은 문자배열을 이용해 덧셈 연산을 구현하는 방법에 대해 포스팅하겠습니다.

 

int 형 , long long 형 범위 안에 있는 수들은 '+' 를 이용해 덧셈 연산을 진행해도 문제가 발생하지 않습니다.

하지만, 굉장히 큰 수(ex 212342351384273198237832984 ) 처럼 long long 형의 범위를 벗어난 수들을

평소처럼 '+'를 이용해 덧셈 연산을 진행한다면 오버플로우가 발생하게 됩니다.

 

따라서, 굉장히 큰 수에 대해서는 문자배열을 이용해서 덧셈을 진행해야 합니다.

 

문자배열을 이용하는 덧셈을 진행하기 위해 다음과 같은 STL 을 이용하겠습니다.

C++에서는 문자배열 string을 STL 에서 지원해주기 때문에 조금 더 간편하게 구현할 수 있습니다.

#include<iostream>
#include<string>
#include<algorithm>

[ 핵심알고리즘 ]

1) 문자배열(A,B) 2개를 뒤에서부터 더해가며 새로운 문자배열(result)에 저장한다.

2) 1)을 진행하면서 올림수(sum)를 계속 저장해 간다.

3) 문자배열 A,B를 모두 순회하고 올림수에 저장된 수가 없다면 result를 뒤집어주고 종료한다.

 

문자배열 A, B를 뒤에서부터(일의자리부터) 더해가며 새로운 문자배열 result에 결과를 저장해나가면

문자배열을 이용해 큰 수의 덧셈을 구현할 수 있습니다.

 

[ 예시 ]

A = "12345" 와 B = "666"을 더해보겠습니다.

 

STEP 1]

5와 6을 더하면 11이므로 올림수는 1, result에는 1을 추가한다. → sum = 1 result = "1" 을 저장한다.

 

STEP 2]

4와 6과 sum을 더하면 11이므로 올림수는 1, result에는 1을 추가한다. → sum = 1 result = "11"을 저장한다.

 

STEP 3]

3과 6과 sum을 더하면 10이므로 올림수는 1, result에는 0을 추가한다. → sum = 1 result = "110"을 저장한다.

 

STEP 4]

문자배열 B는 다 순회했으므로, 2와 sum을 더한다. 올림수는 0, result에는 3을 추가한다. → sum = 0 result = "1103"

 

STEP 5]

마찬가지로 1과 sum을 더한다. 올림수는 0, result에는 1을 추가한다. → sum = 0 result = "11031"

 

STEP 6]

문자배열 A, B를 모두 순회했고, 올림수도 0이므로 result를 뒤집으며 종료한다. → result = "13011"

 

[ 코드구현 ]

algorithm에서 지원해주는 reverse 함수를 이용하면 쉽게 문자배열을 뒤집을 수 있습니다.

string string_add(string a, string b) {
	int sum = 0;
	string result;
	while (!a.empty() || !b.empty() || sum) {
		if (!a.empty()) {
			sum += a.back() - '0';
			a.pop_back();
		}
		if (!b.empty()) {
			sum += b.back() - '0';
			b.pop_back();
		}
		result.push_back((sum % 10) + '0');
		sum /= 10;
	}
	reverse(result.begin(), result.end());
	return result;
}