n개의 이진수 문자열을 모두 더하는 방법

이 프로그램에서는 주어진 여러 개의 이진수를 모두 더하는 작업을 수행합니다. 총 n개의 이진수 문자열이 입력으로 주어지며, 이들을 전부 합산하여 하나의 이진수 결과를 출력해야 합니다.

이를 위해 기본적인 이진수 덧셈 논리를 활용하여, 첫 번째 항부터 N번째 항까지 차례대로 하나씩 더해가며 최종 결과를 얻습니다.

입력: "1011", "10", "1001"
출력: 10110

풀이 방법 설명

가장 간단한 방법은 이진수 문자열을 십진수 값으로 변환한 뒤 모두 더하고, 다시 이진수로 변환하는 것입니다. 하지만 여기서는 변환 과정 없이 직접 이진수 덧셈을 수행해 보겠습니다.

두 개의 이진수 문자열을 더하는 헬퍼(helper) 함수를 하나 만들고, n개의 서로 다른 이진수 문자열에 대해 이 함수를 n-1번 반복 호출하면서 누적 덧셈을 진행합니다.

동작 원리

두 이진수 문자열의 끝자리(최하위 비트)부터 시작하여 각 자릿수를 더합니다. 두 비트와 올림수(carry)를 합한 값이 1이면 해당 자리에 '1'을, 0이면 '0'을 기록하고, 합이 2 이상일 경우 올림수를 다음 자리로 넘깁니다. 한쪽 문자열이 먼저 끝나더라도 나머지 문자열과 올림수 처리가 완료될 때까지 반복합니다.

예제 코드 (C++)

#include<iostream>
using namespace std;

// 두 개의 이진수 문자열을 더하는 함수
string add(string b1, string b2) {
    string res = "";
    int s = 0; // 올림수(carry)
    int i = b1.length() - 1, j = b2.length() - 1;
    while (i >= 0 || j >= 0 || s == 1) {
        if(i >= 0) {
            s += b1[i] - '0';
        } else {
            s += 0;
        }
        if(j >= 0) {
            s += b2[j] - '0';
        } else {
            s += 0;
        }
        res = char(s % 2 + '0') + res;
        s /= 2;
        i--; j--;
    }
    return res;
}

// n개의 이진수 문자열을 순차적으로 더하는 함수
string addbinary(string a[], int n) {
    string res = "";
    for (int i = 0; i < n; i++) {
        res = add(res, a[i]);
    }
    return res;
}

int main() {
    string arr[] = { "1011", "10", "1001" };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << addbinary(arr, n) << endl;
}

실행 결과

10110

코드 설명

add 함수: 두 이진수 문자열을 받아 뒤에서부터 한 자리씩 더합니다. 변수 s는 현재 자릿수의 합과 올림수 역할을 동시에 수행하며, s % 2로 현재 자리의 값을 결정하고 s /= 2로 올림수를 계산합니다.

addbinary 함수: 초기값을 빈 문자열로 설정한 후, 배열의 각 이진수를 순서대로 add 함수에 누적하여 더합니다. 빈 문자열과의 덧셈도 정상적으로 처리되므로 별도의 예외 처리가 필요하지 않습니다.

main 함수: 세 개의 이진수 문자열 {"1011", "10", "1001"}을 배열로 선언하고, 배열 크기를 계산하여 addbinary 함수를 호출한 뒤 최종 결과를 출력합니다.

이 알고리즘의 시간 복잡도는 가장 긴 문자열의 길이에 비례하며, 십진수 변환 시 발생할 수 있는 오버플로우 문제를 피할 수 있다는 장점이 있습니다.