지금까지 내가 해왔던 파이썬은 주로 주가데이터 등을 끌고와서 그냥 Dataframe에서 간단한 데이터 전처리하는 정도에 불과했다. 그저 그래프만 간단하게 그리면 완전 뿌듯해서 끝났던 거 같은데, 그 결과 데이터 프레임을 9개를 그냥 날코딩으로 하는 경지에 이르렀고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 결국 취업 준비 겸 알고리즘 스터디에 들어갔다,,, 그러나 문제는 파이썬 초급만 3회독 했는데 여전히 함수만드는 거랑 클래스 만드는 건 쩔쩔 매고 있다는 거.... ㅠ_ㅠ
# 파이썬 클래스의 "Self"
# Leetcode Add Two numbers
문제 링크와 공부할 때 참고 했던 동영상도 함께 첨부합니다.
https://leetcode.com/problems/add-two-numbers
Add Two Numbers - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
https://www.youtube.com/watch?v=SbcCpAw_8Dg
* 해결하는 데 어려웠던 점?
- 인풋이 어떻게 들어가는지 몰랐음
- ListNode가 무엇을 의미하는 지 몰랐음.
1) 원리 (알고리즘)
어릴 때 덧셈할 때나 지금도 가끔 4자리 5자리 수 덧셈 오랜만에 할 때 항상 위에 자릿수 올림 1 을 숫자 위에 조그맣게 적었던 기억들이 있을 것이다, 바로 그 원리를 이용해 각 자릿수 덧셈을 하는 것이다. 처음에 문제를 접근할 적에는 자릿수를 거꾸로 해야 한다는 점에서 연산 과정이 추가 되는게 아닐까? 생각했다. 그런데 생각해보면 1의 자리 수끼리 덧셈 -> 10의 자리수 덧셈 -> 100의 자리수 순서로 덧셈을 계산한다는 점에서 오히려 reversed 된 상태가 알고리즘 만들기 더 쉬운(?) 방법이다.
2) 대략의 알고리즘 (Pseudo Code)
- ListNode() 함수를 이용해 Linked List를 만드는 함수를 만든다. (이미 리트코드에서 제공)
- ListNode 함수의 숫자를 문제에서 원하는 꼴로 출력하는 함수를 만든다.
- 현재 노드와 carrier를 초기화한다.
- 일단 각 자리수에 맞춰 더한다. 각 자리수의 합이 10 이 넘으면 1의 자리수만 남기고 carrier에 1을 넘겨준다.
- 현재 값을 추가해야 다음 자리 수에 더할 수 있음.
- 각 자리수를 합하는 과정 : Linked List를 반복시켜서 (Add base cases for iterating linked listed)
- l1, l2에 들어갈 숫자를 하나하나 리스트 노드로 이어주고, l3로 결과 값을 원하는 형식에 맞게 출력한다.
3) 각 과정의 코드 구성
1. ListNode() 함수를 이용해 Linked List를 만드는 함수를 만든다.
## 우선 데이터가 어떻게 들어오고 나가는 지 파악하기 위해
# 연결리스트 함수 만들기, ListNode 함수.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next문제에서 기본으로 제공하는 클래스 코드. 이 ListNode라는 클래스에 Object에 2를 넣으면, 기본값 0이던 val이 2 가 된다. 그리고 self.next에 다음 자리 숫자를 넣으면 self.next에 숫자가 계속(?) 저장된다. 사실 정확히 어떤 구조를 갖고 있는지는 모르겠다. next함수에 대해 추가적으로 공부가 필요할 듯.
#243 넣기
god2=ListNode(2)
god2.next=ListNode(4)
god2.next.next=ListNode(3)
god2.val
>>> 2
god2.next.val
>>> 4
god2.next.next.val
>>> 3god2라는 객체에 243 (원래는 342)를 하나하나 리스트 노드를 이용해 linked list 형태로 표현했다. 위와 같이 .next.val을 붙이는 형태로 각 값을 꺼내야 한다.
2. ListNode 함수의 숫자를 문제에서 원하는 꼴로 출력하는 함수를 만든다.
def linked_list_print(l):
if l is None:
return ''
return str(l.val)+'->'+linked_list_print(l.next)
linked_list_print(god2)
>>> 2->4->3->linked_list_print라는 함수를 만들어 leetcode에서 원하는 꼴로 출력할 수 있도록 했다.
3. 현재 노드와 carrier를 초기화한다.
class Solution(object):
def addTwoNumbers(self, l1, l2):
p1 = l1
p2 = l2 #l1, l2는 listnode
carry=0
head = cur = ListNode(0) #초기화 처리
#'cur' 변수를 선언하여 트래버스(traverse) 작업을 지원하고 노드를 새 목록에 추가합니다.
#'head' 변수를 목록의 머리글로 선언합니다.우선 class Solution 안에는 addTwoNumbers라는 유일한 함수가 들어가 있다. addTwoNumbers는 나중에 ListNode() 함수를 통해 linked list 형태로 들어갈 l1(342->243), l2(465->564)가 들어갈 것이다. 그리고 우리가 덧셈 시 자릿수 올림(carry over)를 우선 0으로 초기화한다,
여기서 head와 cur이라는 변수도 ListNode(0)을 통해 0으로 초기화 해주는 데, 참고 동영상에서는 이 방법이 가장 단순하게 초기화 할 수 있는 방법이라고 소개하고 있다. 코드 후반부에서 cur과 next라는 변수에 각 자릿수의 덧셈값을 차례로 누적하고, l3에 할당 된 후 출력된다. 아무튼 우선은 cur과 next 라는 변수는 결과값을 위한 변수라는 정도로 이해하고 넘어가자.
4. 일단 각 자리수에 맞춰 더한다. 각 자리수의 합이 10 이 넘으면 1의 자리수만 남기고 carrier에 1을 넘겨준다.
while p1 or p2 or carry:
print(p1.val, p2.val, carry)
# CurrentVal과 carryover 를 계산
currentval = carry #첨에 0으로 초기화
currentval += 0 if p1 is None else p1.val
currentval += 0 if p2 is None else p2.val
if currentval >= 10 :
currentval -=10
carry = 1
else:
carry = 0
print(currentval, carry)이 과정에서 각 자리 수끼리의 덧셈이 이뤄지고, 자리수올림이 if currentval~ 이하를 통해 연산이 이루어진다, 즉, 자리수 끼리 덧셈이 5+6=11 이라면, 10을 뺀 1만이 currentval에 남고, carry=1이 되어 다음 자릿수 연산에 더해진다. print(currentval, carry)를 통해 중간중간 자릿수 덧셈이 잘 이뤄지는 지 확인할 수 있다.
>>>2 5 0
>>>7 0
>>>4 6 0
>>>0 1
>>>3 4 1
>>>8 0간단히 설명하자면 342+465를 더할 때, 1의 자리 연산은 2+5 = 7, carry =0이 되고, 10의 자리 연산에서 4+6=10 이므로 currentval =0, carry=1 이 되어 다음 100의 자리에 자릿수 올림으로 더해진다.
5.
# 현재값을 추가한다. 현재값은 항상 1 이상이여야 한다.
cur.next = ListNode(currentval) #cur에 linkedlist(ListNode)이용해서 연결한다.
cur = cur.next
6.
if p1 is None and p2 is None:
break # 왜 자꾸 out of loop?
elif p1 is None:
p2=p2.next
elif p2 is None:
p1=p1.next
else:
p1=p1.next
p2=p2.next
return head.next
7.
# l1, l2 리스트 노드로 엮어주기
l1=ListNode(2)
l1.next=ListNode(4)
l1.next.next = ListNode(3)
print(linked_list_print(l1))
l2=ListNode(5)
l2.next=ListNode(6)
l2.next.next = ListNode(4)
print(linked_list_print(l2))
# Step 6: l3로 덧셈값 인쇄.
#add linked lists
s = Solution()
l3 = s.addTwoNumbers(l1,l2)
print(linked_list_print(l3))
# 최종 출력결과
2->4->3->
5->6->4->
2 5 0
7 0
4 6 0
0 1
3 4 1
8 0
7->0->8->
총 코드
## 우선 데이터가 어떻게 들어오고 나가는 지 파악하기 위해
# 연결리스트 함수 만들기, ListNode 함수
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
#243 넣기
god2=ListNode(2)
god2.next=ListNode(4)
god2.next.next=ListNode(3)
god2.val
print(god2)
# recursive print linked list : 재귀 출력 linked list.
def linked_list_print(l):
if l is None:
return ''
return str(l.val)+'->'+linked_list_print(l.next)
linked_list_print(god2) # 2->4->3 프린트 됨.
#-----------------------------------------------------------
# step 1 : Node, carry를 초기화 해준다.
class Solution(object):
def addTwoNumbers(self, l1, l2):
p1 = l1
p2 = l2 #l1, l2는 listnode
carry=0
head = cur = ListNode(0) #초기화 처리
#'cur' 변수를 선언하여 트래버스 작업을 지원하고 노드를 새 목록에 추가합니다.
#'head' 변수를 목록의 머리글로 선언합니다.
# Step 2 : 자릿수올림방법을 이용해 덧셈하는 부분 계산
while p1 or p2 or carry:
print(p1.val, p2.val, carry)
# CurrentVal과 carryover 를 계산
currentval = carry #첨에 0으로 초기화
currentval += 0 if p1 is None else p1.val
currentval += 0 if p2 is None else p2.val
if currentval >= 10 :
currentval -=10
carry = 1
else:
carry = 0
print(currentval, carry) #70
# Step 3 : 현재값을 추가한다. 현재값은 항상 1 이상이여야 한다.
cur.next = ListNode(currentval) #cur에 linkedlist(ListNode)이용해서 연결한다.
cur = cur.next
# Step 4 : Add base cases for iterating linked listed
if p1 is None and p2 is None:
break # 왜 자꾸 out of loop?
elif p1 is None:
p2=p2.next
elif p2 is None:
p1=p1.next
else:
p1=p1.next
p2=p2.next
return head.next
#---------------------------------------------
# step 5: l1, l2 리스트 노드로 엮어주기
l1=ListNode(2)
l1.next=ListNode(4)
l1.next.next = ListNode(3)
print(linked_list_print(l1))
l2=ListNode(5)
l2.next=ListNode(6)
l2.next.next = ListNode(4)
print(linked_list_print(l2))
# Step 6: l3로 덧셈값 인쇄.
#add linked lists
s = Solution()
l3 = s.addTwoNumbers(l1,l2)
print(linked_list_print(l3))