[Book Review] Python Algorithm Interview (5)
[Book Review] Python Algorithm Interview (5) : 연결 리스
1. 연결 리스트
연결리스트
- 기본 선형자료구조 중 하나
- 다양한 추상 자료형 (ADT) 구현의 기반이 됨
- 동적으로 새로운 노드를 삽입하거나 삭제하기 간편
- 연결구조를 통해 물리메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉬움
- 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러가지 방법으로 다양하게 활용 가능
- 물리메모리에는 구조체 각각이 서로 연결된 형태로 구성되어있으며 메모리 어딘가에 여기저기 흩뿌려진 형상을 띤다
- 배열과는 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야하므로 상수시간에 접근할 수 없다. = 탐색시간 O(n) 반면 시작 또는 끝지점에 아이템을 추가하거나 삭제,추출하는 작업은 O(1)에 가능
답안에 포함
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next
ㅤ
ㅤ
ㅤ
ㅤ
Q13. 팰린드롬 연결리스트
Q. 연결리스트가 팰린드롬 구조인지 판별하라
입력
1->2->2->1
출력
true
1) 리스트 변환
파이썬의 리스트는 pop()함수에 인덱스 지정 가능해서 마지막 요소 아니라도 원하는 위치 자유롭게 추출가능
def isPalindrome(self, head: ListNode) -> bool: q: List[] ㅤ if not head: return True node = head ㅤㅤㅤ while node is not None: q.append(node.val) node = node.next ㅤ while len(q) > 1: if a q.pop(0) != q.pop(): return False ㅤ return True
2) 데크를 이용한 최적화
앞선 풀이의 문제점 : pop(0)에서 첫번째 아이템을 추출할때의 속도문제
동적배열로 구성된 리스트는 맨 앞 아이템을 가져오기에 적합한 자료형이 아니다.
(첫번째값을 꺼내오면 모든 값이 한칸씩 시프팅(shifting)되며 시간복잡도 O(n)이 발생하기 때문, 최적화를 위해서는 맨 앞에 데이터를 가져올 때 O(n)이내에 처리할 수 있는 자료형 필요
파이썬 데크(Deque)는 이중연결리스트 구조로 양쪽방향 모두 추출하는데 시간복잡도는 O(1)
-> 양방향 모두 O(1)에 가능한 데크를 설명
(두군데만 수정하면 됨)
q : List = [] 대신에 q: Deque = collections.deque() ㅤ if q.pop(0) != q.pop(): 대신에 if q.popleft() != q.pop():
3) 런너를 이용
- fast / slow 두가지 리스트 구성
- slow를 역순 리스트로 둬서(rev)
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: slow = slow.next ㅤㅤ while rev and rev.val == slow.va: slow, rev = slow.next, rev.next return not rev
런너기법
- 연결리스트 순회할 때 2개의 포인터를 두는 방식/ 한 포인터가 다른 포인터보다 앞서게하여 병합 지점이나 중간위치 길이 등을 판별할 떄 유용하게 사용
- 보통 빠른 런너는 두 칸씩 건너뛰고 느린 런너는 한칸씩 이동 / 빠른 런너가 연결 리스트의 끝에 도달하면 느린 런너는 정확히 연결 리스트의 중간지점을 가리키게됨.
- 이런식으로 중간위치 찾아내면 여기서부터 값을 비교하거나 뒤집기를 시도하는 등 여러모로 활용가능
다중 할당
파이썬에서 다중 할당 (multiple assignment) 2개 이상의 값을 2개 이상의 변수에 동시에 할당하는 것
a,b = 1,2
이처럼 한 번에 여러 개의 값을 여러 변수에 할당할 수 있음
rev, rev.next, slow = slow, rev, slow.next
와
rev = slow rev.next = rev slow = slow.next
는 다름
(동일한 참조와 상이한 참조)
전자의 경우 한번의 트랜잭션으로 끝나게됨.
파이썬의 경우 원시타입이 없고 모두 객체이다
(문자와 숫자의 경우)
할당을 진행할 때 값을 할당하는 것이 아니라 불변 객체에 대한 참조를 할당
숫자 5와 변수 a=5 b=5 모두 동일한 ID
(메모리 상에는 단 하나만 존재, ab 두 변수는 각각 이 값을 가리키는 참조)
-> 불변객체이기 때문에 5라는 숫자를 변경한다고 해도 a,b 두 변수의 id가 6으로 변하지 않음
but 숫자가 아닌 리스트와 같은 자료형일 경우 내부의 값은 변할 수 있음. 이 경우 리스트를 참조하는 모든 변수의 값도 따라 바뀜
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Q14. 두 정렬 리스트의 병합
Q. 정렬되어있는 두 연결리스트 합치기
입력
1->2->4, 1->3->4
출력
1->1->2->3->4->
1) 재귀구조로 연결
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
변수 스왑 = 다중 할당
기본 방식
temp = a a = b b = temp
파이썬
a : int = 1 b : int = 2 a,b = b,a
숫자형식 스왑
x += y y = x – y x -= y
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Q15. 역순 연결리스트
연결 리스트를 뒤집어라
입력
1->2->3->4->5->NULL
출력
5->4->3->2->1->NULL
1) 재귀 구조로 뒤집기
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)
2) 반복 구조로 뒤집기
def reverseList(self, head: ListNode) -> ListNode: node, prev = head, None ㅤ while node: next, node.next = node.next, prev prev, node = node, next return prev
반복이 재귀에 비해 70%수준의 메모리 차지해 공간복잡도 낮고 실행 속도 약간 빠름 (둘다 큰문제 없음)
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Q16. 두 수의 덧셈
Q. 역순으로 저장된 연결리스트의 숫자를 더하라
입력
(2 -> 4 -> 3) + (5 -> 6 -> 4)
출력
7 -> 0 -> 8
1) 자료형 변환
# 연결리스트 뒤집기 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 addTwoNumber(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))
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Q17. 페어의 노드 스왑
Q. 연결리스트를 입력받아 페어단위로 스왑
입력
1->2->3->4
출력
2->1->4->3
1) 값만 교환
def sapPairs(self, head: ListNode) -> ListNode: cur = head ㅤ while cur and cur.next: #값만 교환 cur.val, cur.next.val = cur.next.val, cur.val cur = cur.next.next return head
-> 좋지 않은 피드백 받을수도
2) 반복 구조로 스왑
def swapPairs(self, head: ListNode) -> ListNode: root = prev = ListNode(None) prev.next = head while head and head.next: b = head.next head.next = b.next b.next = head ㅤ prev.next = b ㅤ head = head.next prev = prev.next.next return root.next
3) 재귀 구조로 스왑
def swapPairs(self, head: ListNode) -> ListNode: if head and head.next: p = head.next haed.next = self.swapPairs(p.next) p.next = head return p return head
공간복잡도 낮음
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Q18. 홀짝 연결리스트
Q. 연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성
공간 복잡도 O(1), 시간복잡도 O(n)
입력
2->1->3->5->6->4->7->Null
출력
2->3->6->7->1->5->4->Null
1) 반복구조로 홀짝 노드 처리
def oddEvenList(self, head: ListNode) -> ListNode: if head is None: return None ㅤ odd = head even = head.next even_head = head.next ㅤ while even and even.next: odd.next, even.next = odd.next.next, even.next.next odd,even = odd.next, even.next ㅤ odd.next = even_head return head
ㅤ
ㅤ
ㅤ
ㅤ
ㅤ
Q19. 역순 연결리스트 2
Q. 인덱스 m에서 n까지를 역순으로 만들어라, 인덱스 m은 1부터 시작한다
입력
1->2->3->4->5->NULL, m = 2, n = 4
출력
1->4->3->2->5->NULL
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode: if not head or m == n: return head ㅤ root = start = ListNode(None) root.next = head ㅤ for _ in range(m-1): start = start.next end = start.next ㅤ for _ in range(n-m): tmp, start.next, end.next = start.next, end.next, end.next.next start.next.next = tmp return root.next
Author And Source
이 문제에 관하여([Book Review] Python Algorithm Interview (5)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@anthony16/Book-Review-Python-Algorithm-Interview-5저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)