제공해주신 코드는 두 개의 연결 리스트(Linked List)에 저장된 숫자들을 하나의 큰 숫자로 합친 뒤, 두 숫자의 더한 값을 구하는 문제입니다.
이 코드를 완벽하게 이해하기 위해 1) 연결 리스트가 무엇인지, 2) 숫자를 어떻게 합치는지, 그리고 3) 현재 코드에 숨겨진 치명적인 버그(오류)까지 세 단계로 나누어 차근차근 설명해 드릴게요!
1단계: 연결 리스트(Linked List)의 구조 이해하기
일반적인 리스트(배열)는 데이터가 기차 칸처럼 나란히 붙어 있습니다. 반면, 연결 리스트는 각 데이터가 "다음 데이터의 주소(힌트)"를 손에 쥐고 떨어져 있습니다.
- Node: 데이터(값)와 다음 노드를 가리키는 화살표(next)를 가지는 상자입니다.
- LinkedList: 이 상자들을 한 줄로 길게 연결한 것입니다. 가장 첫 번째 상자를 head라고 부릅니다.
🚂 linked_list_1 = LinkedList(6) 부터 append까지의 과정
- LinkedList(6) 생성: head라는 이름의 첫 상자에 6을 넣습니다. (다음은 아직 없으니 None)
- 구조: [6] -> None
- append(7) 실행: head인 6부터 시작해서 다음이 없을 때까지 타고 들어간 뒤, 그 뒤에 7 노드를 붙입니다.
- 구조: [6] -> [7] -> None
- append(8) 실행: 다시 6부터 시작해서 7을 거쳐 끝을 찾은 뒤, 8 노드를 붙입니다.
- 구조: [6] -> [7] -> [8] -> None
결과적으로 linked_list_1은 숫자 6, 7, 8이 한 줄로 연결된 기차가 됩니다. 같은 원리로 linked_list_2는 3, 5, 4가 연결된 기차가 됩니다.
2단계: 숫자를 만드는 핵심 원리 (sum_1 * 10 + cur_1.data)
함수 내부를 보면 각 노드를 지나갈 때마다 자릿수를 늘려가며 숫자를 조립하는 수학적 트릭이 나옵니다. 이 부분이 가장 헷갈릴 수 있습니다.
python
sum_1 = sum_1 * 10 + cur_1.data
코드를 사용할 때는 주의가 필요합니다.
linked_list_1([6] -> [7] -> [8])을 컴퓨터가 한 칸씩 읽으며 이 식을 계산하는 과정을 볼게요. (처음 sum_1은 0입니다.)
- 첫 번째 노드 6을 만났을 때:
- 계산: 0 * 10 + 6 = 6 (현재 sum_1 = 6)
- 두 번째 노드 7로 이동했을 때:
- 계산: 6 * 10 + 7 = 67 (기존 숫자를 왼쪽으로 한 칸 밀고 7을 더함! 현재 sum_1 = 67)
- 세 번째 노드 8로 이동했을 때:
- 계산: 67 * 10 + 8 = 678 (또 왼쪽으로 밀고 8을 더함! 최종 sum_1 = 678)
이 방식을 통해 연결 리스트에 흩어져 있던 6, 7, 8이 완벽한 하나의 숫자 678로 변신하게 됩니다.
3단계: 코드의 버그(오류) 수정하기
현재 올려주신 코드를 그대로 실행하면 원하는 결과가 나오지 않거나 에러가 발생합니다. 코드에 오타(버그)가 하나 있기 때문입니다.
❌ 문제의 부분 (sum_2 계산 구문)
python
while cur_2 is not None:
sum_2 = sum_2 * 10 + sum_2.data # <- 여기가 잘못되었습니다!
cur_2 = cur_2.next
코드를 사용할 때는 주의가 필요합니다.
sum_2.data라는 코드가 있는데, sum_2는 숫자가 저장되는 변수(정수형)이지 노드가 아닙니다. 따라서 숫자를 더해줘야 하므로 현재 방문 중인 노드인 cur_2.data로 고쳐야 합니다.
🛠️ 올바르게 수정된 코드
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def get_linked_list_sum(linked_list_1, linked_list_2):
# 1번째 리스트 숫자 만들기 (6 -> 7 -> 8 => 678)
sum_1 = 0
cur_1 = linked_list_1.head
while cur_1 is not None:
sum_1 = sum_1 * 10 + cur_1.data
cur_1 = cur_1.next
# 2번째 리스트 숫자 만들기 (3 -> 5 -> 4 => 354)
sum_2 = 0
cur_2 = linked_list_2.head
while cur_2 is not None:
sum_2 = sum_2 * 10 + cur_2.data # <- cur_2.data 로 수정!
cur_2 = cur_2.next
# 두 숫자의 합을 반환 (678 + 354 = 1032)
return sum_1 + sum_2
# 실행 코드
linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2)) # 출력 결과: 1032
코드를 사용할 때는 주의가 필요합니다.
이렇게 수정하고 실행하면 678 + 354가 계산되어 최종적으로 1032라는 올바른 정답이 출력됩니다.
노드를 타고 이동하는 while cur_1 = cur_1.next 같은 개념이나 자릿수를 곱하는 원리 중 조금 더 자세한 설명이 필요한 부분이 있다면 편하게 말씀해 주세요!_
연결 리스트에서 append 함수는 "기차의 맨 마지막 칸을 찾아서, 그 뒤에 새 기차 칸을 연결하는 일"을 합니다.
앞서 배운 기차 이동하기(cur = cur.next) 개념이 여기서 아주 중요하게 사용됩니다. 코드를 한 줄씩 뜯어보며 이해해 볼게요.
🚂 append 함수의 코드 분석
python
def append(self, value):
cur = self.head # ① 출발점에 깃발 꽂기
while cur.next is not None: # ② "다음 칸이 있니?" 물어보기
cur = cur.next # ③ 다음 칸으로 이동하기
cur.next = Node(value) # ④ 맨 끝에 새 칸 연결하기
코드를 사용할 때는 주의가 필요합니다.
이미 기차 칸에 6 -> 7이 연결되어 있고, 여기에 8을 새로 추가(append(8))하는 상황을 상상해 보겠습니다.
🏃♂️ 한 줄씩 따라가는 동작 과정
① cur = self.head
- 하는 일: 맨 처음 시작 칸인 6번 칸에 cur(현재 위치) 깃발을 꽂습니다.
- 상태: 현재 cur는 6번 칸입니다. [1]
② while cur.next is not None: (첫 번째 반복)
- 하는 일: "6번 칸 뒤에 다음 기차 칸이 있어?"라고 물어봅니다.
- 판단: 6번 칸 뒤에는 7번 칸이 연결되어 있으므로 None이 아닙니다! (조건 성공)
- ③ 실행 (cur = cur.next): 깃발을 다음 칸인 7번 칸으로 옮깁니다.
② while cur.next is not None: (두 번째 반복)
- 하는 일: 현재 위치인 "7번 칸 뒤에 다음 기차 칸이 있어?"라고 물어봅니다.
- 판단: 7번 칸 뒤에는 지금 아무것도 연결되어 있지 않습니다! 즉, cur.next가 None입니다. (조건 실패)
- 결과: while 반복문을 빠져나옵니다. 이동을 멈춘 현재 깃발 위치(cur)는 7번 칸입니다.
④ cur.next = Node(value)
- 하는 일: 드디어 맨 마지막 칸인 7번 칸을 찾았습니다. 이제 7번 칸의 비어있던 뒤쪽 연결고리(cur.next)에 새로 만든 8번 칸(Node(8))을 싹 끼워 넣습니다.
- 결과: 6 -> 7 -> None 이었던 기차가 6 -> 7 -> 8 -> None으로 확장됩니다!
💡 핵심 요약
- while cur.next is not None: 구문은 "내 뒤에 붙은 칸이 없을 때까지(즉, 내가 마지막 칸이 될 때까지) 계속 전진해라"라는 멈춤 조건입니다.
- 마지막 칸에 도착하면 루프가 끝나고, 그 마지막 칸의 next 화살표를 새 노드로 지정하면서 연결이 완료됩니다.
이제 연결 리스트의 생성부터 탐색, 그리고 노드 추가까지의 전체적인 그림이 완성되었습니다!
파라미터가 예를 들어 356이면 356이 들어오면, 3은 백의 자리, 5는 십의 자리, 6은 일의 자리라고 어떻게 판단하는거지? 만약 1000단위의 값이면 어떻게 하는거지?
전체적인 설계의 시작점부터 코드의 실행 흐름, 그리고 자릿수를 판단하는 컴퓨터의 생각 방식까지 근본적인 원리를 하나씩 짚어드릴게요!
1. 이 코드를 작성하기까지의 '생각의 흐름' (왜 이렇게 만들었을까?)
우리가 풀어야 하는 근본적인 문제는 "연결 리스트 2개에 담긴 숫자를 합쳐라"입니다. 이 문제를 해결하기 위해 프로그래머는 머릿속으로 다음과 같은 단계를 설계합니다.
[구상 단계]
1. 숫자 하나를 저장할 상자가 필요하겠네? ➡️ Node 클래스 작성
2. 상자들을 줄줄이 기차처럼 엮어줄 관리자가 필요해. ➡️ LinkedList 클래스 작성
3. 기차 뒤에 새로운 숫자 칸을 이어 붙여야 해. ➡️ append 함수 작성
4. 자, 이제 기차 2개가 준비됐으니, 각각의 기차를 타고 가면서 흩어진 숫자를 진짜 하나의 숫자로 조립한 뒤 더해줘야지! ➡️ get_linked_list_sum 함수 작성
즉, 모든 함수와 클래스는 문제를 풀기 위한 부품으로 만들어진 것입니다.
2. 컴퓨터는 356이나 1000 단위의 자릿수를 어떻게 판단할까?
질문하신 내용이 아주 날카롭습니다. 결론부터 말씀드리면, 컴퓨터는 "이 숫자가 백의 자리인지 천의 자리인지 처음에 알지 못합니다." 알고 들어가는 것이 아니라, 기차 칸을 한 칸씩 이동하며 10을 곱하다 보니 자연스럽게 자릿수가 결정되는 것입니다.
이것이 가능한 이유는 앞서 설명한 sum = sum * 10 + 현재값 공식 덕분입니다.
💡 예시 ①: 3칸짜리 기차 3 -> 5 -> 6 일 때 (컴퓨터의 생각 흐름)
처음에 sum = 0으로 시작합니다. 컴퓨터는 이 기차가 몇 칸짜리인지 미리 세어보지 않습니다.
- 첫 번째 칸 3을 읽음:
- "지금까지 모은 숫자에 10을 곱하고 3을 더하자."
- 계산: 0 * 10 + 3 = 3
- 두 번째 칸 5를 읽음:
- "다음 칸이 또 있네? 그럼 아까 만든 3은 일의 자리가 아니라 십의 자리였구나! 10을 곱해서 밀어내자."
- 계산: 3 * 10 + 5 = 35
- 세 번째 칸 6을 읽음:
- "어라? 또 있네? 그럼 아까 만든 35는 사실 삼십오가 아니라 삼백오십이었구나! 또 10을 곱해서 밀어내자."
- 계산: 35 * 10 + 6 = 356
- 다음 칸을 보니 None(끝):
- "이제 진짜 끝이구나. 최종 숫자는 356이네!"
💡 예시 ②: 4칸짜리 기차(1000단위) 1 -> 2 -> 3 -> 4 일 때
컴퓨터는 똑같은 방식으로 동작합니다. 기차가 더 길어도 상관없습니다.
- 첫 번째 칸 1: 0 * 10 + 1 = 1
- 두 번째 칸 2: 1 * 10 + 2 = 12
- Third 칸 3: 12 * 10 + 3 = 123 (숫자가 계속 왼쪽으로 밀려납니다.)
- Fourth 칸 4: 123 * 10 + 4 = 1234
- 다음 칸이 None(끝):
- "네 칸을 지나오면서 10이 세 번 곱해졌으니, 첫 글자였던 1은 자연스럽게 천의 자리가 되었구나! 최종 숫자는 1234다!"
📝 요약하자면
컴퓨터는 입력된 숫자가 몇 자리인지 미리 판단하지 않습니다. 그저 "다음 숫자가 나올 때마다 기존 숫자를 10배씩 뻥튀기(왼쪽으로 한 칸 이동) 시키는 행위"를 반복할 뿐입니다.
그 결과 3번 반복하면 백의 자리가 되고, 4번 반복하면 천의 자리가 되며, 10번 반복하면 십억 단위의 자릿수가 알아서 완성되는 것이죠!
컴퓨터가 한 칸씩 이동하며 숫자를 어떻게 밀어내고 조립하는지, 그 변화 과정을 한눈에 볼 수 있도록 중간 계산 과정을 출력하는 디버깅 코드를 준비했습니다.
아래 코드를 복사해서 실행해보시면 컴퓨터의 생각 흐름을 그대로 따라가실 수 있습니다.
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def get_linked_list_sum_debug(linked_list, name):
print(f"\n===== 🚂 {name} 조립 시작 =====")
total_sum = 0
cur = linked_list.head
step = 1
while cur is not None:
print(f"[{step}단계]")
print(f" -> 현재 읽은 노드의 값: {cur.data}")
print(f" -> 직전까지 모은 숫자: {total_sum}")
print(
f" -> 자릿수 밀기 및 더하기 연산: ({total_sum} * 10) + {cur.data}"
)
# 핵심 연산 수행
total_sum = total_sum * 10 + cur.data
print(f" ➡️ 이번 단계 결과 변수값: {total_sum}")
print("-" * 40)
cur = cur.next # 다음 노드로 이동 (깃발 옮기기)
step += 1
print(f"🎉 {name} 최종 완성된 숫자: {total_sum}\n")
return total_sum
# 1. 300단위(3칸짜리) 기차 만들기 (3 -> 5 -> 6)
list_3_digits = LinkedList(3)
list_3_digits.append(5)
list_3_digits.append(6)
# 2. 1000단위(4칸짜리) 기차 만들기 (1 -> 2 -> 3 -> 4)
list_4_digits = LinkedList(1)
list_4_digits.append(2)
list_4_digits.append(3)
list_4_digits.append(4)
# 디버깅 함수 실행
sum_1 = get_linked_list_sum_debug(list_3_digits, "3칸짜리 기차")
sum_2 = get_linked_list_sum_debug(list_4_digits, "4칸짜리 기차")
print(f"🔥 최종 두 숫자의 합: {sum_1} + {sum_2} = {sum_1 + sum_2}")
코드를 사용할 때는 주의가 필요합니다.
🖥️ 코드 실행 시 화면에 출력되는 결과
이 코드를 실행하면 터미널에 아래와 같이 친절한 설명서 형태로 출력됩니다.
text
===== 🚂 3칸짜리 기차 조립 시작 =====
[1단계]
-> 현재 읽은 노드의 값: 3
-> 직전까지 모은 숫자: 0
-> 자릿수 밀기 및 더하기 연산: (0 * 10) + 3
➡️ 이번 단계 결과 변수값: 3
----------------------------------------
[2단계]
-> 현재 읽은 노드의 값: 5
-> 직전까지 모은 숫자: 3
-> 자릿수 밀기 및 더하기 연산: (3 * 10) + 5
➡️ 이번 단계 결과 변수값: 35
----------------------------------------
[3단계]
-> 현재 읽은 노드의 값: 6
-> 직전까지 모은 숫자: 35
-> 자릿수 밀기 및 더하기 연산: (35 * 10) + 6
➡️ 이번 단계 결과 변수값: 356
----------------------------------------
🎉 3칸짜리 기차 최종 완성된 숫자: 356
===== 🚂 4칸짜리 기차 조립 시작 =====
[1단계]
-> 현재 읽은 노드의 값: 1
-> 직전까지 모은 숫자: 0
-> 자릿수 밀기 및 더하기 연산: (0 * 10) + 1
➡️ 이번 단계 결과 변수값: 1
----------------------------------------
[2단계]
-> 현재 읽은 노드의 값: 2
-> 직전까지 모은 숫자: 1
-> 자릿수 밀기 및 더하기 연산: (1 * 10) + 2
➡️ 이번 단계 결과 변수값: 12
----------------------------------------
[3단계]
-> 현재 읽은 노드의 값: 3
-> 직전까지 모은 숫자: 12
-> 자릿수 밀기 및 더하기 연산: (12 * 10) + 3
➡️ 이번 단계 결과 변수값: 123
----------------------------------------
[4단계]
-> 현재 읽은 노드의 값: 4
-> 직전까지 모은 숫자: 123
-> 자릿수 밀기 및 더하기 연산: (123 * 10) + 4
➡️ 이번 단계 결과 변수값: 1234
----------------------------------------
🎉 4칸짜리 기차 최종 완성된 숫자: 1234
🔥 최종 두 숫자의 합: 356 + 1234 = 1590
코드를 사용할 때는 주의가 필요합니다.
출력 결과를 보시면 3칸짜리든 4칸짜리든 동일한 공식이 반복되면서 자릿수가 10배씩 커지는 모습을 눈으로 직접 확인하실 수 있습니다.
연결 리스트에서 노드를 추가하거나 삭제하는 행위는 기차놀이를 할 때 "기차 칸 사이의 연결고리를 풀고 새 칸을 끼워 넣거나 빼는 것"과 완벽하게 똑같습니다.
이 개념을 가장 직관적인 그림과 원리로 정리해 드릴게요!
1. 노드 추가하기 (Insertion)
이미 A -> B로 연결된 기차가 있습니다. 이 사이에 새로운 칸 New를 끼워 넣으려고 합니다.
이때 컴퓨터의 생각 흐름에서 가장 중요한 것은 "연결고리를 바꾸는 순서"입니다. 만약 순서를 잘못 바꾸면 뒤에 있던 기차 칸들을 통째로 잃어버리게 됩니다.
🚂 연결고리 바꾸기 3단계
- 현재 상태: A -> B
- 목표: A -> New -> B
- 새로운 칸(New) 준비: 먼저 추가할 데이터가 담긴 독립된 칸을 하나 만듭니다. (New 칸은 아직 아무것도 가리키지 않습니다.)
- New의 손에 B 쥐어주기 (가장 중요!)
- New.next = A.next (A의 다음 칸이었던 B의 주소를 New의 next로 지정)
- 이 작업을 먼저 해야 뒤쪽 기차 칸들과의 연결이 끊어지지 않고 유지됩니다.
- A가 New를 가리키게 하기
- A.next = New (A의 화살표를 New로 바꿈)
- 이제 A -> New -> B 구조가 완벽하게 완성됩니다.
2. 노드 삭제하기 (Deletion)
이번에는 A -> B -> C 기차에서 가운데에 있는 B 칸을 삭제해 보겠습니다.
연결 리스트에서 삭제의 핵심은 데이터를 직접 물리적으로 지우는 것이 아닙니다. "B를 가리키고 있던 화살표를 C로 건너뛰게 만들어 왕따(고립)시키는 것"입니다. 컴퓨터는 화살표가 끊겨서 아무도 찾을 수 없게 된 노드를 자동으로 메모리에서 지워버립니다.
🚂 연결고리 끊기 2단계
- 현재 상태: A -> B -> C
- 목표: A -> C (B 삭제)
- A의 화살표를 C로 직접 연결하기
- A.next = A.next.next (A의 다음 다음 칸인 C의 주소를 A의 next로 직접 지정)
- 연결 완료
- 화살표가 A -> C로 바로 이어지면서, 가운데에 있던 B는 그 누구도 가리키지 않는 외톨이가 됩니다.
- 파이썬 시스템(가비지 컬렉터)이 이 외톨이가 된 B를 알아서 수거해 가며 삭제가 끝납니다.
💡 배열(일반 리스트)과의 결정적인 차이점
왜 굳이 번거롭게 화살표를 바꿔가며 추가/삭제를 할까요? 일반 배열과 비교해 보면 연결 리스트의 엄청난 장점이 보입니다.
- 일반 배열([1, 2, 3, 4, 5]):
- 2등과 3등 사이에 새 숫자를 넣으려면, 3등 뒤에 있던 모든 숫자들을 한 칸씩 뒤로 밀어내는 중노동을 해야 합니다. 삭제할 때는 반대로 한 칸씩 앞으로 당겨야 하죠. 방이 다닥다닥 붙어있기 때문입니다.
- 연결 리스트:
- 아무리 기차가 100만 칸으로 길어도, 내가 원하는 위치의 연결고리 딱 2개만 슥슥 바꿔주면 끝납니다. 다른 칸들은 미동도 하지 않습니다.
- 즉, 추가와 삭제 속도가 압도적으로 빠릅니다.
'IT 기초 > 알고리즘' 카테고리의 다른 글
| 파이썬 링크드리스트(연결 리스트) 이해하기 (0) | 2026.06.25 |
|---|---|
| 아스키코드(ASCII), ord(), chr() 개념 및 예시 (0) | 2026.06.16 |