C++로 두 개의 이진수 문자열 더하기 – 자리올림 처리와 구현 방법

문제 소개

두 개의 이진수 문자열이 주어졌을 때, 두 문자열을 더한 결과를 구하고 그 결과를 이진수 문자열 형태로 반환하는 것이 이번 문제의 목표입니다.

이진수(binary number)란 0과 1 두 숫자만으로 표현되는 수를 말합니다. 두 개의 이진수를 더할 때는 십진수 덧셈과 달리 아래와 같은 이진수 덧셈 규칙을 반드시 고려해야 합니다.

0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 0, 자리올림(carry) 1 발생

입력 및 출력 예시

입력 1

str1 = {"11"}, str2 = {"1"}

출력 1

"100"

입력 2

str1 = {"110"}, str2 = {"1"}

출력 2

"111"

문제 해결 접근 방법

두 문자열을 마지막 자리(오른쪽 끝)부터 차례대로 탐색합니다.
각 자리의 두 이진수 값을 서로 더합니다.
두 개의 1이 만나면 해당 자리를 0으로 만들고 자리올림 1을 다음 자리로 넘깁니다.
모든 자리를 처리한 후 최종 결과를 반환합니다.

알고리즘

시작
Step 1 → 두 문자열을 더하는 함수 선언
   string add(string a, string b)
      result = "" 로 초기화
      temp(자리올림 저장 변수) = 0 으로 초기화
      size_a = a.size() - 1
      size_b = b.size() - 1
      while (size_a >= 0 || size_b >= 0 || temp == 1)
         temp += ((size_a >= 0) ? a[size_a] - '0' : 0)
         temp += ((size_b >= 0) ? b[size_b] - '0' : 0)
         result = char(temp % 2 + '0') + result
         temp /= 2
         size_a--, size_b--
      while 종료
      return result
Step 2 → main() 함수 내부
   문자열 a = "10101", b = "11100" 선언
   add(a, b) 호출
종료

핵심 로직 설명

이 알고리즘의 핵심은 두 비트의 합과 자리올림을 하나의 변수 temp로 관리하는 것입니다. 각 자리에서 두 비트와 이전 자리올림 값을 모두 더한 뒤, temp % 2를 현재 자리의 값으로 사용하고 temp / 2를 다음 자리올림으로 활용합니다. 이렇게 하면 복잡한 조건 분기 없이도 자리올림을 자연스럽게 처리할 수 있습니다.

C++ 구현 코드

#include<bits/stdc++.h>
using namespace std;
// 두 문자열을 더하는 함수
string add(string a, string b){
   string result = "";
   int temp = 0;
   int size_a = a.size() - 1;
   int size_b = b.size() - 1;
   while (size_a >= 0 || size_b >= 0 || temp == 1){
      temp += ((size_a >= 0)? a[size_a] - '0': 0);
      temp += ((size_b >= 0)? b[size_b] - '0': 0);
      result = char(temp % 2 + '0') + result;
      temp /= 2;
      size_a--; size_b--;
   }
   return result;
}
int main(){
   string a = "10101", b="11100";
   cout<<"sum of strings are : "<<add(a, b);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

sum of strings are : 110001

시간 복잡도

두 문자열 중 긴 쪽의 길이를 n이라 할 때, 모든 자리를 한 번씩 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 결과 문자열을 저장하는 데 O(n)이 필요합니다.