자바스크립트로 이진수 배열 덧셈 알고리즘 구현하기

이진수 덧셈의 기본 원리

이진수 덧셈은 다음 네 가지 기본 규칙을 따릅니다.

0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

이 규칙들을 염두에 두면, 이진수 덧셈은 자릿수 올림(캐리) 원리를 따르는 십진수 덧셈과 매우 유사하다는 것을 알 수 있습니다. 두 비트의 합이 1을 초과하면 현재 자릿수에는 0을 기록하고, 그다음 자릿수로 1을 올려주는 것이 핵심입니다.

문제 정의

두 개의 배열을 인자로 받는 자바스크립트 함수를 작성해야 합니다. 각 배열은 '0' 또는 '1'로만 구성된 이진 문자열 요소를 포함합니다.

함수는 두 배열에서 대응되는 이진 비트끼리 더한 후, 그 결과를 담은 새로운 배열을 반환해야 합니다.

예를 들어 입력 배열이 다음과 같다면,

const arr1 = ['1', '0', '1'];
const arr2 = ['1', '0', '1'];

출력은 다음과 같아야 합니다.

const output = ['1', '0', '1', '0'];

알고리즘 접근 방식

1. 두 배열을 join('')으로 하나의 문자열로 합칩니다.
2. 더 긴 문자열의 길이부터 시작하여 뒤에서 앞으로 순회합니다.
3. 각 자릿수의 두 비트와 캐리 값을 더합니다.
4. 합이 1보다 크면 현재 자릿수는 0, 캐리는 1로 설정합니다.
5. 순회가 끝난 후에도 캐리가 남아 있으면 결과 맨 앞에 추가합니다.
6. 최종 문자열을 split('')으로 배열로 변환하여 반환합니다.

구현 예제

위 접근 방식을 코드로 구현하면 다음과 같습니다.

const arr1 = ['1', '0', '1'];
const arr2 = ['1', '0', '1'];
const addBinary = (arr1 = [], arr2 = []) => {
   const str1 = arr1.join('');
   const str2 = arr2.join('');
   let carry = 0, temp = 0, res = '';
   for(let i = Math.max(str1.length, str2.length) - 1; i >= 0; i--){
      const el1 = +str1[i] || 0;
      const el2 = +str2[i] || 0;
      if(el1 + el2 + carry > 1){
         temp = 0;
         carry = 1;
      }else{
         temp = el1 + el2 + carry;
         carry = 0;
      };
      res = temp + res;
   };
   if(carry){
      res = carry + res;
   };
   return res.split('');
};
console.log(addBinary(arr1, arr2));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

[ '1', '0', '1', '0' ]

'101' + '101' = '1010'이므로, 마지막 자릿수에서 발생한 캐리가 결과 배열의 맨 앞에 추가된 것을 확인할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(n)으로, n은 더 긴 배열의 길이입니다.