[프로그래머스] 이진수 더하기

https://school.programmers.co.kr/learn/courses/30/lessons/120885

프로그래머스

  많은 언어들이 N진수 문자열 <-> 10진수 숫자 변환 기능을 지원하므로 문제를 푸는 것 자체는 어렵지 않다. 예를 들어 자바스크립트에서 지원하는 기능을 이용하면 다음과 같이 풀 수 있다.

function solution(bin1, bin2) {
    return (parseInt(bin1,2) + parseInt(bin2,2)).toString(2);
}

 다만 위 코드는 딱히 로직이랄게 없으므로, 이진수를 구현하는 능력이 있는지를 판단할 수는 없다. 그래서 만약 이진수 연산기를 위 함수들 없이 구현하라고 하면 어떻게 하는게 좋을까 생각하면서 코드를 작성해봤다. 

---

작성된 코드

 현재 코드에서는 십진수 변환 없이 0, 1 및 increment를 비교하며 결과 이진 문자열을 출력한다.

function solution2(bin1, bin2) {
    //#01. 문자열 길이 보정
    const diff = bin1.length - bin2.length;
    if(diff > 0) { //문자열 길이 보정
        bin2 = '0'.repeat(diff) + bin2;
    } else {
        bin1 = '0'.repeat(-diff) + bin1;
    }

    let idx = bin1.length - 1; # 현재 연산 중인 인덱스 값
    let inc = false; // 올림 값 있는지 여부
    const result = [];
    //#02 연산
    while (idx >= 0) {
        if (bin1[idx] & bin2[idx]) { // 11인 경우
            result.push(inc ? '1' : '0');
            inc = true;
        } else if (bin1[idx] | bin2[idx]) { // 10인 경우
            if (inc) {
                result.push('0');
            } else {
                result.push('1');
                inc = false;
            }
        } else { //00
            if (inc) {
                result.push('1');
                inc = false;
            } else {
                result.push('0');
            }
        }
        idx--;
    }
    //#03 마지막 올림 평가
    if (inc) {
        result.push('1');
    }
    //#04 문자열 합치기
    return result.reverse().join('');
}

 각 단계에 따라 설명한다.

문자열 길이 보정 단계

더 짧은 문자열에 대해 빈 공간에 '0' 문자를 채운다.

 문자열 길이 보정 단계에서는 두 문자열의 길이 차만큼 짧은 문자열에 '0' 을 채운다. 이 과정이 없더라도 구현이 가능하긴 한데, 코드와 로직이 좀 더 복잡해져서 그냥 두 문자열의 길이를 동일하게 만들었다.

연산 단계

연산 단계에서는 while문을 통해 두 문자열을 뒤에서부터 비교한다. 규칙은 아래와 같다. inc는 이전 계산에서 올림이 있었음을 의미한다. 예를 들어 01 + 11의 첫번째 자리에서는 1 + 1 이 있으므로 1을 올린다. 이 경우 inc가 활성화된다.

bin1[idx]	bin2[idx]	inc	result[idx]	next inc	설명
1	1	true	1	1	캐리 1, 현재 값 1을 얻는다.
1	1	false	0	1	-
1	0	true	0	1	inc와 기존의 1을 더해 캐리가 발생한다.
1	0	false	1	0	현재 결과만 증가한다.
0	0	true	1	0	기존의 캐리가 현재 자리에 반영된다.
0	0	false	0	0	-

 컴퓨터 구조 수업 시간에 언젠가 들었던 것 같은 동작 방식을 이용한다. 기존의 캐리 값과 현재 값들을 고려하여 다음 결과를 설정하는 로직으로 구현했다.

오버플로우 평가 및 문자열 반환

 idx = 0, 즉 가장 높은 자리에서 오버플로우가 발생하면 해당 값을 반영해야 한다. 이를 위해 if문을 둬서 처리했다. 결과는 내림차순으로 표현되어 있으므로 reverse() 함수로 뒤집어서 오름차순으로 나타내고 join('') 함수를 써서 문자열로 묶었다.

테스트 결과

사실 위에서 묘사한 동작은 full adder의 동작에 해당한다. full adder은 컴퓨터 내부에서 덧셈 연산을 수행하는 회로에 들어가는 장치로 진리표가 존재한다. 아래 코드는 해당 장치가 가진 진리표를 기반으로 작성되었다.

function solution2(bin1, bin2) {
    const diff = bin1.length - bin2.length;

    if(diff > 0) { //문자열 길이 보정
        bin2 = '0'.repeat(diff) + bin2;
    } else {
        bin1 = '0'.repeat(-diff) + bin1;
    }

    let idx = bin1.length - 1;
    let inc = false;

    const result = [];
    while (idx >= 0) {
        result.push((bin1[idx] ^ bin2[idx] ^ inc));
        inc = (bin1[idx]&bin2[idx])|((bin1[idx]^bin2[idx])&inc);
        idx--;
    }
    
    if (inc) {
        result.push('1');
    }
    return result.reverse().join('');
}

full adder에서 현재 위치의 값 S와 캐리 C는 다음과 같은 논리식으로 표현될 수 있다.

• x, y:연산 대상이 되는 두 값
• z: 이전 단계에서의 캐리 
• S = x ⊕ y ⊕ z
• C = xy + (x ⊕ y)z
  

 내 생각이지만, 이 문제가 full adder을 알고 있는지 물어본 것은 아닐거라고 생각한다. 컴퓨터 구성 또는 구조 영역은 비전공자가 접할 일이 별로 없는 분야라,  맨 처음 제시했던 parseInt을 사용하는 간단한 방식이 의도에 맞는 것 같다. 하지만 오랜만에 공부했던 영역을 복습하는 시간을 가져서 좋았다.