연결 리스트로 표현된 두 숫자를 더하는 방법

이 글에서는 서로 다른 연결 리스트(Linked List)에 저장된 두 숫자를 더하는 방법을 살펴보겠습니다. 연결 리스트에는 숫자의 각 자릿수가 한 노드씩 저장됩니다. 예를 들어 숫자 512는 다음과 같이 표현됩니다.

512 = (5)-->(1)-->(2)-->NULL

이러한 형태의 두 개의 리스트가 주어졌을 때, 우리의 목표는 두 리스트를 더하여 그 합계를 계산한 결과를 얻는 것입니다. 여기서는 C++ STL의 list 컨테이너를 활용합니다. 구현 내용을 더 잘 이해할 수 있도록 먼저 알고리즘부터 확인해 보겠습니다.

알고리즘

addListNumbers(l1, l2)

시작
    짧은 쪽 리스트의 앞에 0을 추가하여 l1과 l2의 길이를 동일하게 맞춤
    carry := 0
    res := 빈 리스트
    l1의 각 노드 n에 대해 뒤에서부터 앞쪽으로 스캔하며 반복:
        item := (l1.item + l2.item + carry) mod 10
        item을 res의 맨 앞에 삽입
        carry := (l1.item + l2.item + carry) / 10
    반복 종료
    만약 carry가 0이 아니라면
        res의 맨 앞에 carry 추가
    조건문 종료
    res 반환
끝

예제 코드

#include<iostream>
#include<list>
using namespace std;
list addListNumbers(list<int> l1, list<int> l2){
    //짧은 숫자 쪽 앞에 0을 추가하여 두 리스트의 길이를 동일하게 맞춤
    if(l1.size() > l2.size()){
        for(int i = l2.size(); i != l1.size(); i++){
            l2.push_front(0);
        }
    }else if(l1.size() < l2.size()){
        for(int i = l1.size(); i != l2.size(); i++){
            l1.push_front(0);
        }
    }
    list<int>::reverse_iterator it1 = l1.rbegin();
    list<int>::reverse_iterator it2 = l2.rbegin();
    list<int> result;
    int carry = 0;
    while(it1 != l1.rend()){
        result.push_front((*it1 + *it2 + carry) % 10);
        carry = (*it1 + *it2 + carry) / 10;
        it1++; it2++;
    }
    if(carry != 0){
        result.push_front(carry);
    }
    return result;
}
list<int> numToList(int n){
    list<int> numList;
    while(n != 0){
        numList.push_front(n % 10);
        n /= 10;
    }
    return numList;
}
void displayListNum(list<int> numList){
    for(list<int>::iterator it = numList.begin(); it != numList.end();
    it++){
        cout<<*it;
    }
    cout << endl;
}
int main() {
    int n1 = 512;
    int n2 = 14578;
    list<int> n1_list = numToList(n1);
    list<int> n2_list = numToList(n2);
    list<int> res = addListNumbers(n1_list, n2_list);
    cout << "First number: "; displayListNum(n1_list);
    cout << "Second number: "; displayListNum(n2_list);
    cout << "Result: "; displayListNum(res);
}

실행 결과

First number: 512
Second number: 14578
Result: 15090

위 코드의 동작 원리를 간단히 정리하면 다음과 같습니다. numToList() 함수는 정수를 받아 각 자릿수를 분리해 연결 리스트로 변환합니다. addListNumbers() 함수는 두 리스트의 길이를 맞춘 후, 역방향 반복자(reverse iterator)를 사용해 일의 자리부터 차례대로 더합니다. 이때 각 자릿수의 합을 10으로 나눈 나머지를 결과에 저장하고, 몫은 올림수(carry)로 다음 자릿수 계산에 반영합니다. 마지막으로 올림수가 남아 있다면 결과 리스트의 맨 앞에 추가합니다.

이 방식은 초등학교에서 세로셈으로 두 수를 더하는 것과 완전히 동일한 원리입니다. 리스트의 길이가 매우 길어져 정수형 변수의 표현 범위를 넘는 큰 수의 연산에도 활용할 수 있다는 점이 큰 장점입니다.