230411 화요일
오늘의 TMI
오늘은 화요일~! 파이썬 멘토링하는 날이다.
오늘까지 과제를 PR 해야 하는데 저번주에 못해서 부랴부랴 과제부터 ㅋ,,
과제는 어렵지 않았지만 Mac으로 바꾼 후에 git을 한 번도 안 썼어서 설정이 좀 필요하였다,,
ssh key도 새로 발급받아야 한다는 것도 몰랐고..........
오늘 멘토링이 취소되지 않았으면 난 과제를 제시간에 못 내는 거여따
다행히(?)는 아니지만 어쨌든.. 멘토링 멤버 분 중 한 분의 사정으로 멘토링이 취소되었고 나는 비어버린 시간에 멘토님과 함께 git reset을 하며 겨우 제대로 올리게 되어따!!!!!!!
이상한 파일들이 계속 커밋되어 있었음.. pull, push 하는데 계정도 입력하라 하고!! 그런 이상한 거 다신 나에게 시키지 마라 git아🙃
암튼 이거 하느라 오늘 강의를 제대로 못 들었음 ㅜ 어제 거도 밀려있는데 얼른 채워야징!
정처기도 공부해야 해 승언아.
학습주제
7강 - 연결 리스트(Linked List)(1)
연결리스트에서 제일 기본적인 3가지 연산에 대해 알아보았다.
1. 특정 원소 참조(k번째)
2. 리스트 순회
3. 길이 얻어내기
위 세 가지의 내용이 모두 담긴 코드는 아래와 같다.
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
# 1. 특정 원소 참조(k번째)
# pos번째의 노드 참조하기
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None # 특정 경우 예외
i = 1
curr = self.head # 연결 리스트의 첫 번째 노드
# 앞에서부터 하나하나 탐색하기 때문에 선형탐색과 유사
while i < pos:
curr = curr.next
i += 1
return curr
# 2. 리스트 순회
# 주의! 리스트 안에 append 해야 할 값은 node 자체가 아니라 node 안의 data!
def traverse(self):
result = []
curr = self.head # 첫 번째 노드에 접근
while curr != None: # tail이 되면 none
result.append(curr.data)
curr = curr.next
return result
# 3. 길이 얻어내기
def getLength(self):
return self.nodeCount
8강 - 연결 리스트(Linked List)(2)
위에서 가장 기본적인 3가지의 연산을 소개했다면, 이번에는 가장 핵심적인 3가지의 연산을 소개한다.
4. 원소의 삽입 (insertion)
5. 원소의 삭제 (deletion)
6. 두 리스트 합치기 (concatenation)
구현할 때 항상 생각해야 할 부분은 예외 처리를 하는 부분이다.
맨 앞이나 맨 뒤의 원소를 삽입, 삭제하는 것을 예외 처리 해주어야 한다. (이 경우 내에서도 예외 처리 해주어야 함. 그것은 바로바로~~)
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = None
self.tail = None
def getAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
i = 1
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
# 4. 원소의 삽입
def insertAt(self, pos, newNode):
# pos가 범위에 없는 예외 경우
if pos < 1 or pos > self.nodeCount + 1:
return False
# 맨 앞에 삽입하는 경우
if pos == 1:
# 순서에 유의
newNode.next = self.head
self.head = newNode
else:
# 맨 마지막에 삽입하는 경우
if pos == self.nodeCount + 1:
prev = self.tail # prev의 위치를 가져옴
# 중간에 삽입하는 경우
else:
prev = self.getAt(pos - 1) # prev의 위치를 가져옴
# 순서에 유의. 순서가 바뀌면 prev.next가 바뀌어버리기 때문에 불가능
newNode.next = prev.next
prev.next = newNode
if pos == self.nodeCount + 1:
self.tail = newNode
self.nodeCount += 1
return True
# 5. 원소의 삭제
# 삭제하는 노드의 데이터 값을 리턴해야함
def popAt(self, pos):
# pos가 범위에 없는 예외 경우
if pos < 1 or pos > self.nodeCount:
raise IndexError
# 삭제할 노드
curr = self.getAt(pos)
# 첫 번째 노드를 삭제하는 경우
if pos == 1:
# 연결리스트의 길이가 1인 경우
if self.nodeCount == 1:
self.head = None
self.tail = None
else:
self.head = curr.next
else:
# 삭제하려는 노드의 전 노드인 prev 선언
prev = self.getAt(pos -1)
# 맨 마지막 노드를 삭제하는 경우
if pos == self.nodeCount:
prev.next = None
self.tail = prev
# 중간에 있는 노드를 삭제하는 경우
else:
prev.next = curr.next
self.nodeCount -= 1
return curr.data
# 6. 두 리스트 합치기
def concat(self, L):
self.tail.next = L.head
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
9강 - 연결 리스트(Linked List)(3)
7강에서는 특정 원소를 지정해서 원소를 찾아갔는데 이번 강의에서는 특정 원소의 다음 원소를 지정하고 그 원소를 이용하여 특정 원소를 삽입/삭제하는 연산을 정의하였다. 이것을 위해 연결 리스트 맨 앞에 데이터 원소를 담고 있지 않은, 더미 노드(dummy node)를 추가한 형태를 배운다.
연결 리스트의 장점!
- 삽입과 삭제가 유연하다. 이 강의에서 위와 같은 이유들로 이 특징이 잘 보여짐!
더미 노드를 가지는 연결 리스트의 연산 6가지를 코드를 통해 알아보자.
class Node:
def __init__(self, item):
self.data = item
self.next = None
class LinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = None
self.head.next = self.tail
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next:
curr = curr.next
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
newNode.next = prev.next
# 맨 마지막에 삽입하는 경우
if prev.next is None:
self.tail = newNode
prev.next = newNode
self.nodeCount += 1
return True
# 코드가 간단해짐
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
# 빈 리스트가 아니면서 맨 마지막에 삽입하는 경우
if pos != 1 and pos == self.nodeCount + 1:
prev = self.tail
else:
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
# 삭제할 노드가 없는 경우
if prev.next == None:
return None
# 리스트 맨 끝의 노드를 삭제하는 경우
elif curr.next == None:
self.tail = prev
prev.next = None
# 중간 노드를 삭제하는 경우
else:
prev.next = curr.next
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
raise IndexError
prev = self.getAt(pos - 1)
return self.popAfter(prev)
def concat(self, L):
self.tail.next = L.head.next
if L.tail:
self.tail = L.tail
self.nodeCount += L.nodeCount
10강 - 양방향 연결 리스트(Doubly Linked List)
앞에서 본 연결 리스트들은 한 방향으로만 연결되어 있었다. 그래서 맨 뒤에 있는 원소를 삭제할 때는 맨 앞 원소부터 순회했어야 하는데, 이번에 배우는 양방향 연결 리스트를 사용하면 뒤에서부터 찾아갈 수 있기 때문에 그럴 필요가 없다.
양방향 연결 리스트에서는 노드들이 앞, 뒤로 연결되어 있다. 이 말은, 인접한 두 개의 노드들은 앞의 노드로부터 뒤의 노드가 연결되어 있을 뿐만 아니라, 뒤의 노드로부터 앞의 노드도 연결되어 있다는 말이다...😂
단 방향 연결 리스트와 비교한 양방향 연결 리스트의 장점과 단점
단점
- 링크를 나타내기 위한 메모리 사용량 증가
- 앞, 뒤 링크 모두 조정해야 하기에 귀찮
장점
- 뒤에서부터 순회 가능(역방향 순회)
- 비교적 깔끔한 코드 구현
아래는 양방향 연결리스트의 여러 가지 연산 코드이다.
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertBefore(self, next, newNode):
prev = next.prev
newNode.next = next
newNode.prev = prev
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
prev.next = curr.next
curr.next.prev = prev
self.nodeCount -= 1
return curr.data
def popBefore(self, next):
curr = next.prev
next.prev = curr.prev
curr.prev.next = next
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 0 or pos > self.nodeCount:
raise IndexError
return self.popAfter(self.getAt(pos - 1))
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount
11강 - 스택(Stack)
12강 - 수식의 후위 표기법
13강 - 후위 표기 수식 계산
공부하며 어려웠던 내용
연결 리스트,, 헷갈려 @_@
학교 다닐 때 열심히 할걸 ㅎㅎ