[BOJ #1252] 이진수 덧셈

BOJ #1252, 이진수 덧셈 문제입니다.

 

정답률은 28.3%로 상당히 낮습니다. 저 또한 문제의 세부 조건을 발견하지 못해 잠깐 헤맸습니다. 우선 이 문제는 크게 두 가지 방법이 있습니다. 첫 번째로 입력받은 이진수를 십진수로 변환하여 더하고, 다시 이진수로 변환하여 출력하는 방법이 있습니다. 두 번째로는 변환 없이 이진수 덧셈 자체를 구현하는 것이 되겠습니다.

 

첫 번째 방법은 어떻게 보면 더 효율적이고 더 빠른 방법일 수는 있겠으나, 문제의 의도는 아닐 것이라고 생각됩니다. 그리고 두 번째 방법으로 만들어보는 것이 실력적으로 더 큰 도움이 될 것입니다.

 

알고리즘은 동일하나, 이번 문제의 특성 상 C보단 Python으로 푸는 게 편리합니다. 저는 연습을 위해 일부러 C로 풀었지만 여기선 Python을 사용하도록 하겠습니다.

 

1. 이진수를 배열 형태로 만들기

이진수 덧셈을 구현하기 위해서는 두 이진수의 각 자릿수별 연산이 필수적이겠죠. 입력받은 이진수 문자열을 각각 a와 b라고 하면, int(a[index])로 다루면 됩니다. 그러나 매번 이 연산을 하는 것은 비효율적이기 때문에 이것을 반복 수행하여 a와 b를 a_list와 b_list로 만들겠습니다. 코드는 다음과 같습니다.

def bin_to_list(bin_str):
    res_list = []
    for i in range(len(bin_str)):
        res_list.append(int(bin_str[i]))

    return res_list


a, b = input('').split()
a_list = bin_to_list(a)
b_list = bin_to_list(b)

그러나 이 코드에는 문제가 있습니다. 바로 문제의 세부조건 때문입니다. 문제에 따르면, 각 이진수는 0으로 시작할 수도 있습니다. 즉, 0000001과 같은 입력이 가능하다는 것이죠. 위 코드를 사용해서 문제를 풀면, 실제 자릿수는 같으나 배열의 인덱스 상 자릿수는 달라지는 경우가 발생합니다. 앞부분의 0은 전혀 의미없는 숫자이므로, 그들을 버리고 배열화해야 합니다. bin_to_list 함수를 다음과 같이 개선하겠습니다.

def bin_to_list(bin_str):
    one_flag = False
    res_list = []
    for i in range(len(bin_str)):
        if bin_str[i] == '1':
            one_flag = True
        if one_flag:
            res_list.append(int(bin_str[i]))

    if not one_flag:
        return [0]

    res_list.reverse()
    return res_list

이렇게 하면 앞부분의 의미 없는 0을 쳐낼 수 있습니다. 1이 등장할 때까지 기다렸다가 1이 등장하면 flag를 True로 바꾸고 그때부터 append하기 시작하는 것이죠. 다만 0000000과 같이 입력된 경우는 별도로 처리를 해주어야 합니다. 저는 10번줄의 if문을 통해 처리를 했고 이 부분이 없으면 오류가 발생할 겁니다.

 

그리고 return 이전 .reverse() 메소드를 사용했는데, 크게 두 가지 이유가 있습니다. 첫 번째로는 자리올림을 편하게 하기 위해서입니다. 예를 들어 11 + 11 == 110인데, 마지막에 새로운 자리가 생긴 경우 .append()로 간단히 해결할 수 있게 됩니다. 물론 Python에서는 reverse하지 않고 사용해도 .insert()로 편하게 할 수 있겠지만 C로 풀 땐 이처럼 reverse해두고 푸는 것이 훨씬 편리합니다. 두 번째로 우리는 1의 자리부터 더해갈 것이기 때문입니다. 만약 두 이진수의 자릿수가 다르다면 index 처리를 따로따로 해주어야 하는데, reverse해두면 두 이진수에 대해 같은 index를 이용해 문제를 풀 수 있습니다.

 

2. 덧셈 구현

1의 자리부터 큰 자리를 차례로 더해 나갈 것이며, 올림을 고려해야 합니다. 우선 한 자리 이진수끼리 더하는 경우는 다음의 3가지 경우가 있겠습니다.

• 0 + 0 == 0
• 0 + 1 == 1
• 1 + 1 == 10 == 1(올림)

여기서 올림을 고려하면, 다음 세 가지의 경우가 추가됩니다.

• 0 + 0 + 1(올려진 값) == 1
• 0 + 1 + 1(올려진 값) == 10 == 1(올림)
• 1 + 1 + 1(올려진 값) == 11 == 1(올림) + 1

그런데 올림의 여부와는 상관없이 덧셈의 결과값은 피연산자들의 총합과만 관계됩니다. 따라서 up이 올려진 값이 저장된 변수라고 하면 a_list[index] + b_list[index] + up에 따라 분기하면 되겠습니다. 물론 상세 case별로 올림 처리를 해 주어야 합니다. 이 부분이야말로 이번 문제의 핵심이므로, 직접 구현해보시기 바랍니다.

 

저는 더 짧은 이진수 배열까지만 덧셈 처리를 했는데, 만약 마지막에 올림된 1이 남은 경우에 대해서도 처리해주어야 했습니다. 이러한 점과 덧셈을 한 이후엔 결과를 그대로 출력하되, 거꾸로 출력해야 한다는 점에 유의하여 직접 코딩해보시면 얻어가는 것이 아주 많을 문제라고 생각됩니다.

 

3. 전체 코드

def bin_to_list(bin_str):
    one_flag = False
    res_list = []
    for i in range(len(bin_str)):
        if bin_str[i] == '1':
            one_flag = True
        if one_flag:
            res_list.append(int(bin_str[i]))

    if not one_flag:
        return [0]

    res_list.reverse()
    return res_list


def print_binary(bin_str):
    for i in range(len(bin_str)):
        print(bin_str[len(bin_str) - 1 - i], end='')
    print('')


a, b = input('').split()
a_list = bin_to_list(a)
b_list = bin_to_list(b)

if len(a_list) < len(b_list):
    tmp_list = a_list[:]
    a_list = b_list[:]
    b_list = tmp_list[:]

up = 0
for i in range(len(b_list)):
    part_sum = up + a_list[i] + b_list[i]
    if part_sum == 0:
        up = 0
        a_list[i] = 0
    elif part_sum == 1:
        up = 0
        a_list[i] = 1
    elif part_sum == 2:
        up = 1
        a_list[i] = 0
    elif part_sum == 3:
        up = 1
        a_list[i] = 1

if up == 1:
    if len(a_list) == len(b_list):
        a_list.append(1)
    else:
        for i in range(len(b_list), len(a_list)):
            if a_list[i] == 0:
                a_list[i] = 1
                break
            elif a_list[i] == 1:
                a_list[i] = 0
                if i == len(a_list) - 1:
                    a_list.append(1)
                    break

print_binary(a_list)

32번줄부터가 덧셈을 처리하는 과정이고, 48번줄부터가 덧셈 이후 올림된 1이 남은 상황을 처리하는 과정입니다. .append()를 사용해서 깔끔하게 처리가 가능하기에 배열을 reverse해서 저장한 것도 있습니다.