알고리즘
연결 리스트:
데이터의 선형집합, 메모리에 물리적인 순서대로 저장되지않아 동적으로 새로운 노드 삽입, 삭제가 간편하며, 관리도 쉽다. 하지만 배열과 달리 물리적인 순서가 없다는 것이 단점으로 작용한다. 특정 인덱스에 접근하기위해서 전체를 순서대로 읽어야하기 때문이다.
앞의 5장 설명에 따르면 파이썬에선 기본적으로 동적 배열(Dynamic Array)을 사용해 리스트를 만든다고 한다. 사용하다 정해진 칸만큼의 배열이 가득차면 더블링(Doubling, 칸을 늘린 배열을 새로 만들고 거기로 전체 복사)을 하는 방식을 통해 동적으로 배열을 관리한다. (잡다한 지식으로, 재할당하는 비율을 그로스 팩터(growth factor)라고 하며, 파이썬은 초반엔 2배 전체적으론 1.125배씩 늘려간다.)
평소에 사용하던 리스트(동적 배열)와는 다르게 연결리스트는 노드끼리 연결되어 있으며, 노드 내부에는 인자와 (다음 노드를 가리키는) next 포인터로 구성된다.
그리고 이 구조때문에 메모리에 차례대로 쌓인 리스트와 다르게 인덱스로 탐색하기위해선 각 노드에 접근해 다음 포인터를 순서대로 따라가야 한다.
234. Palindrome Linked List (leetcode)
def isPalindrome(self, head: ListNode) -> bool:
q:List=[]
while head is not None:
q.append(head.val)
head =head.next
while len(q)>1:
if q.pop(0) != q.pop():
return False
return True.val 을 통해 연결 리스트의 현재 노드에 저장된 인자를 호출하고, .next 로 next 포인터를 따라 다음 노드에 접근한다.
그후 pop을 이용하는데, 파이썬은 pop(n)을 이용하면 n번째 값을 pop할 수 있다. 그리고 pop() 을 하면 원래처럼 맨 뒤의 값을 가져온다.
여기서 pop의 문제점은 pop(0)등 맨뒤가 아닌 다른 값들을 호출하면 꺼낸 값 뒤의 모든 값들이 한 칸씩 시프팅되며 시간복잡도 O(n)이 발생한다.
이에 대한 대책으로 Deque가 있다. 데크는 이중 연결 리스트 구조로 양쪽 방향 모두 추출하는 데 시간 복잡도 O(1)이 발생한다. (데크 자세한건 나중에)
데크를 적용하기위해 코드 두줄만 수정해주면 된다.
q:Deque = collections.deque()
if q.popleft() != q.pop():
파이써닉한 풀이
def isPalindrome(self, head: ListNode) -> bool:
rev = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, slow = slow, rev, slow.next
if fast: ## head가 홀수일때. 가운댓 값은 slow와 rev를 비교할때 없어야하니까.
slow = slow.next
while rev and rev.val == slow.val: ## rev랑 slow를 비교하는데, 같은 값이 안나오면
slow, rev = slow.next, rev.next ## rev나 slow에 값이 남도록 설계됨.
return not rev런너를 이용해 푼다. 이는 연결 리스트 풀이에서 주로 사용되는데, 빠른 런너와 느린 런너 라 부르는 2개의 포인터를 이용한다. 빠른 런너는 head값을 두칸씩 건너뛰면서 while을 이용해 짝/홀 구분과 동시에 느린 런너와 rev값을 조절하는 역할을 한다. 느린 런너는 한칸씩 이동하면서 자신의 현재값을 rev에 저장하는 역할을 한다.
주의할 점 rev, rev.next, slow = slow, rev, slow.next는 작성한 것처럼 무조건 다중할당을 통해 작성해야한다. (다중할당은 매우 중요하다) 만약 이 코드를
rev, rev.next = slow, rev
slow = slow.next
형태로 고친다면, 코드가 제대로 작동하지 않는다.
rev=1, slow=2->3 일때
rev, rev.next, slow = slow, rev, slow.next 코드이면
rev=2->3, rev.next=1, slow=3, ---> rev=2->3 대신 rev.next=1임으로 rev=2->1이 된다.
rev, rev.next = slow, rev
slow = slow.next 코드이면 첫줄 rev=2->3, rev.next=1 ---> rev=2->1이 된다. 둘째줄은 첫줄의 rev=slow 에 따라 rev.next인 1이 나오게 된다.
위의 코드는 바로 이해하기 어려워 금방 이해가 가는 쉬운 코드를 작성해봤다.
a=[2,1]
b=[3,5]
a[1]=2
b[1]=a[1]
print(a,b)
--> [2, 2] [3, 2]
a=[2,1]
b=[3,5]
a[1], b[1]=2, a[1]
print(a,b)
--> [2, 2] [3, 1]다중할당을 해주면 a[1]이 2로 변경되기 전인 1을 b[1] 에 대입하고, 그렇지 않으면 a[1]=2 로 변경된 상태에서 대입된다.
왜 이런 경우가 발생하냐면, 파이썬은 모든 것이 객체이기때문에, 변수에 해당 값을 저장하지 않고 해당 값의 위치(참조)를 넣는다.
저번 TIL에 작성한걸로 기억하는데, >>> id(5) 와 a=5, >>> id(a)의 값은 같다.
21. Merge Two Sorted Lists (leetcode)
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if (not l1) or (l2 and l1.val > l2.val):
l1, l2 = l2, l1
if l1:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1 우선 순위가 높은 연산자는 비교연산(>, =, <) > not > and > or 이다.
이 문제는 재귀함수를 사용했다.
재귀를 설명하기 가장 쉬울거 같은 그림
F1이 끝나면 F2을 호출하고, F2가 끝나면 F1을 호출하는 일정 조건까지 반복하는 코드들이 재귀라고 이해하면 쉽다.
l1이 없거나 l2값이 l1보다 작으면 l2값과 l1값을 스왑한다. 그리고 l1이 존재한다면 l1의 다음 노드는 함수를 또 실행시켜서 얻어 내는데, 이때 함수안에서도 또 자기딴에는 자신의 다음 노드를 함수를 실행시켜 얻어낼것이다.
또한 변수 스왑에서 파이썬은 앞서말한 다중할당에 의해서 임시 변수를 만들 필요가 없어 편하다.
c의 경우 스왑하려면
temp=a
a=b
b=temp을 이용해야한다.
206. Reverse Linked List (leetcode)
오답, 연결 리스트로 return 해야해서 틀렸다.
def reverseList(self, head: ListNode) -> ListNode:
q:List=[]
while head is not None:
q.append(head.val)
head=head.next
q=q[::-1]
return q리턴을 그냥 리스트가 아니라 연결 리스트로 줘야하네;;
def reverseList(self, head: ListNode) -> ListNode:
def reverse(node:ListNode,prev:ListNode = None):
if not node:
return prev
next, node.next = node.next, prev
return reverse(next, node)
return reverse(head)머리속으로만 이해하긴 어려워서 로직을 그렸다.
node.next=A라면 node=1,2,3 에서 1뒤에 어떤 숫자가 있던 node=1,A로 대체된다.
def reverseList(self, head: ListNode) -> ListNode:
node, prev = head, None
while node:
next,node.next= node.next, prev
prev, node = node, next
return prev이 코드는 반복 구조를 이용했다.
또한, 이것도 머리속으론 어려워 로직을 그렸다.
2. Add Two Numbers (leetcode)
def reverseList(self, head: ListNode) -> ListNode:
node, prev = head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev
def toList(self, node: ListNode) -> List:
list: List = []
while node:
list.append(node.val)
node = node.next
return list
def toReversedLinkedList(self, result: str) -> ListNode:
prev: ListNode = None
for r in result:
node = ListNode(r)
node.next = prev
prev = node
return node
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
a = self.toList(self.reverseList(l1))
b = self.toList(self.reverseList(l2))
resultStr = int(''.join(str(e) for e in a)) + \
int(''.join(str(e) for e in b))
return self.toReversedLinkedList(str(resultStr))음,, 로직자체는 간단하다. 코드를 실행하면 addTwoNumbers 함수가 실행된다. 연결 리스트 상태에서 reverse하고 일반 동적 리스트로 만든다. 그리고 resultStr을 통해 리스트를 합치고 int로 형변환 시킨 각각의 값을 더한다.
이후 int를 str로 형변환하고 toReversedLinkedList를 통해 다시 연결 리스트로 변환하여 리턴해준다.
이 풀이는 문제에서 원하는 풀이는 아니라고 한다.
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
root = head = ListNode(0)
carry=0
while l1 or l2 or carry:
sum=0
if l1:
sum +=l1.val
l1= l1.next
if l2:
sum+=l2.val
l2= l2.next
carry, val = divmod(sum+carry,10)
head.next = ListNode(val)
head=head.next
return root.next
이것도 로직 그려봤다. 근데 왜 return root.next를 해주는건지는 아직 의문,,, 일단 책 전용 깃허브에 이슈를 오픈해놨다. 나중에 수정하자.
숫자형 리스트를 단일 값으로 병합하기.
a=[1,2,3,4,5]이라 가정할때
리스트를 단일값으로 병합할때는 원래''.join(e) for e in a)코드를 이용했다.
하지만 다른 방법이 더 있다.
첫번째로
''.join(map(str, a))
두번째로
`functools.reduce(lambda x, y : 10 * x + y, a, 0)
이 코드는 reduce(계산할 식, 대입 리스트, 초깃값) 으로 이뤄진거 같다.
x에 1, y에 2를 넣고 --> 10 + 2
x에 12, y에 3을 넣고 --> 120 +3
x에 123, y에 4를 넣고 --> 123 + 4
x에 1234, y에 5를 넣고 --> 1234 + 5
간단하고 쉬운 코드인거같다.
제발 머리속으로만 굴리지말고 손코딩 꼭좀 하자.
파알인 228p까지 완료.
