1. 어레이(Array)란?
어레이는 파이썬의 리스트보다 한 단계 더 깊은 기층에 있는 데이터 형식입니다. 즉 리스트는 어레이 기반 위에 만들어진 형식이라 할 수 있는데요. 만약 우리가 A=1 이라고 선언했다면, 컴퓨터는 이를 저장하기 위해 메모리 공간을 쓸 것입니다. 이때 메모리 공간을 중구남방으로 사용하는 것보다 메모리 공간을 모아두면 훨씬 효율적이겠죠.
어레이란 이런 메모리 공간을 시퀀스 형태로 붙여서 관리하는 오브젝트를 의미합니다. 쉽게 말해, A=1, B=2, C=3 이라고 선언한다면 각 변수를 메모리 공간에 저장하고, 각 메모리 공간을 박스라고 생각하고 3개 박스를 이어붙인 것입니다.
그리고 어레이는 처음 선언할 때 사이즈를 반드시 정해주어야 합니다. 리스트처럼 추가하고, 제거하는 것이 제한됩니다. 이에 따른 문제는 2가지가 제기될 수 있습니다.
1. 메모리 낭비: 처음에 선언한 사이즈보다 채워 넣을 원소가 부족할 때
2. 메모리 부족: 처음에 선언한 사이즈가 충분하지 않을 때
이런 문제를 해결하기 위해 Array resize라는 테크닉이 필요합니다. 우리가 마주하는 리스트는 쉽게 원소를 추가하고, 삭제할 수 있는 것처럼 보이지만 그 이면에는 array resize라는 기법을 통해 몇 가지 작업을 거치는 것이죠.
예를 들어, 사이즈가 6인 어레이를 선언했다고 가정해봅시다. 유저는 L.append(3)을 입력했고, 사이즈가 고정된 어레이는 원소 3을 넣을 자리가 없습니다. 이때, 컴퓨터는 다른 메모리 공간에 사이즈가 6보다 큰 어레이를 다시 저장하고, 원래 어레이에 있던 원소들을 옮깁니다. 이후 유저가 추가하고자 하는 원소 3을 넣는 것입니다.
이러한 Array resize는 사실 연산을 많이 잡아먹는 방법입니다. 새로운 메모리 공간을 필요로 하고 기존 리스트에 있던 값을 그대로 복사하는 작업도 필요하죠. 기존 어레이보다 얼마나 큰 어레이를 새로 선언할 것이냐? 하는 것도 문제입니다. 1) 한 번에 많이 늘려놓으면 이후에 다시 늘릴 필요가 없으니 좋겠지만 메모리 공간을 낭비할 문제가 있구요. 2) 한 번에 1개씩만 늘리면 그만큼 작업을 반복적으로 해야겠죠.
파이썬 리스트 사이즈는 0, 4, 8, 16, 25, 35, 47, 58, 72, 88과 같이 커집니다. 즉 원소가 0개일 때, 어레이 사이즈를 4개 늘리고, 원소 4개가 꽉 차 있다면, 어레이 사이즈를 8개 늘립니다. 다시 말해 L.append(3)를 할 때 어레이 사이즈를 1개만 늘리는 것이 아니라 위에 나온 개수대로 늘리는 것입니다. 기존 리스트의 원소가 16개였을 경우, L.append(3)를 하면 25개의 어레이 공간이 더 생기는 것이죠.
2. Linked List란?
Linked List를 설명하기 위해 먼저 클래스를 정의하고 실제 예시를 만들어보겠습니다.
class LinkedNode():
def __init__(self, x):
self.val = x
self.next = None # x 다음에 나올 값을 의미
a = LinkedNode(3)
b = LinkedNode(5)
a.next = b위 코드 의미는 아래 그림을 보면 쉽게 이해할 수 있습니다. a의 val=3 다음에 나올 값이 b의 val값 5가 되는 것이죠.
b.val = a.next.val
이렇게 Linked list란 리스트의 원소 간 연결된 것을 의미합니다. 따라서 어떤 원소든 리스트의 첫 번째 원소를 통해 접근할 수 있겠죠.
본격적으로 Linked list 코드를 살펴보겠습니다.
class LinkedNode():
def __init__(self, x):
self.val = x
self.next = None
class SLList():
def __init__(self) -> None:
self.first = None
def addFirst(self, x: int) -> None:
newFirst = LinkedNode(x)
newFirst.next = self.first # 새로 들어온 값이 가리키는 것은 바로 이전 노드
self.first = newFirst # 새로 들어온 값이 첫 번째 노드가 됨
def getFirst(self) -> int:
if self.first:
return self.first.val
else:
return None
a.addFirst(3)
print(a.getFirst()) # 첫 번째 노드값
print(a.first.next) # 첫 번째 노드값이 가리키는 노드값 <- 이 단계에선 아직 없으니 None
a.addFirst(5)
print(a.getFirst())
print(a.first.next.val) # 이 단계에선 이전 노드값 5 리턴
이제부터 기능을 하나하나 추가해보겠습니다. 먼저, 리스트에 원소가 몇 개 있는지를 카운팅하는 함수를 만들어봅시다. 사이즈를 측정하기 위해 while 문을 사용해서 마지막 노드값이 None이면 멈추고, while loop이 돌 때마다 size +=1을 통해 총 개수를 셀 수도 있습니다. 하지만 이 경우 시간 복잡도는 O(N)이 되겠죠.
대신 메모리를 좀 더 사용해서 시간 복잡도와 트레이드 오프를 합니다. 메모리는 조금 더 사용하지만 시간 복잡도가 훨씬 줄어드는 것이죠.(메모리에 저장하는 것을 caching이라고도 부릅니다.)
class SLList():
def __init__(self) -> None:
self.first = None
self.size = 0 # 메모리 하나 더 쓰기
def addFirst(self, x: int) -> None:
newFirst = LinkedNode(x)
newFirst.next = self.first
self.first = newFirst
self.size += 1
def getFirst(self) -> int:
if self.first:
return self.first.val
else:
return None
def getSize(self) -> int:
return self.size
위와 같이 size라는 메모리 공간을 하나 더 확보하면 addFirst() 함수가 실행될 때마다 size를 하나씩 늘려주고, 최종적으로 getSize() 함수를 통해 그 값을 리턴하기만 하면 됩니다.
a = SLList()
print(a.getSize())
a.addFirst(3)
print(a.getSize(), a.getFirst())
a.addFirst(5)
print(a.getSize(), a.getFirst())
센티넬 노드(Sentinel Node)
이제 append()라는 함수를 정의해보려고 합니다. append() 역시 처음에 생각했던 size() 함수와 비슷하게 while loop을 돌려서 None이 나오면 해당 값을 추가해주면 될 것입니다. 하지만 append()는 size()처럼 메모리를 더 사용하지 않습니다.
def append(self, x: int) -> None:
self.size += 1
curNode = self.first
while curNode.next != None: # curNode=None이면 while문 자체가 성립 불가
curNode = curNode.next
curNode.next = LinkedNode(x)하지만 위 코드의 문제점은 curNode=None일 때(첫 번째 노드) 발생합니다. 코드 작동에 에러가 발생하게 되는 것이죠. 이를 어떻게 해결할까요? if 조건절을 추가해서 첫 번째 노드의 스페셜 처리 코드를 추가해줘야 할까요? 정답은 센티넬 노드를 사용하는 것입니다.
센티넬 노드는 첫 번째 노드값을 None이 아닌 특정 값으로 미리 설정하는 것입니다. 하지만 센티넬 노드가 가리키는 값은 정해지지 않으며, 그럼에도 유효한 노드의 역할을 합니다. 대신 값은 정해지지 않으니 센티넬이 가리키는 다음 노드(sentinel.next)가 진정한 첫 번째 노드가 됩니다.
class SLList():
def __init__(self) -> None:
self.sentinel = LinkedNode(0) # dummy node but valid -> sentinel 값으로 0 설정
self.size = 0
def addFirst(self, x: int) -> None:
newFirst = LinkedNode(x)
newFirst.next = self.sentinel.next # sentinel.next = first node
self.sentinel.next = newFirst
self.size += 1
def getFirst(self) -> int:
return self.sentinel.next.val
def getSize(self) -> int:
return self.size
def append(self, x: int) -> None:
self.size += 1
curNode = self.sentinel
while curNode.next != None:
curNode = curNode.next
curNode.next = LinkedNode(x)3. 큐(Queue)란?: 가장 먼저 들어온 놈이 가장 먼저 나갈 수 있다!
큐는 쉽게 말해 가장 먼저 추가된 원소가 가장 먼저 없어지는 구조입니다. 이를 FIFO(First In and First Out)라고 부릅니다.
enqueue(): add an element to the queue
dequeue(): remove the oldest element from the queue
4. 스택(Stack)이란?: 가장 늦게 들어온 놈이 가장 먼저 나갈 수 있다!
스택은 큐와 반대의 개념으로, 가장 늦게(=최근에) 추가된 원소가 가장 먼저 삭제되는 것입니다. 이를 LIFO(Last In and First Out)라고 부릅니다.
push(): add an element to the stack
pop(): remove the newest element from the stack
class LinkedNode():
def __init__(self, x):
self.val = x
self.next = None
class myStack():
def __init__(self) -> None:
self.sentinel = LinkedNode(0)
self.size = 0
def push(self, x: int) -> None:
newNode = LinkedNode(x)
newNode.next = self.sentinel.next
self.sentinel.next = newNode
self.size += 1
def pop(self) -> None: # 가장 최근에 추가된 노드값부터 삭제
if not self.isEmpty(): # 비어있을 때도 작동하면 사이즈 크기가 음수가 됨
removal = self.sentinel.next # 최근 추가된 노드를 변수로 선언
self.sentinel.next = self.sentinel.next.next # 최근에 추가된 노드를 이전 노드로 덮어쓰기
removal.next = None # 최근 추가된 노드의 연결고리가 없도록 보장
self.size -= 1
def top(self) -> int: # 가장 최근에 추가된 노드값 리턴
if not self.isEmpty():
return self.sentinel.next.val
else:
return None
def getSize(self) -> int:
return self.size
def isEmpty(self) -> bool: # 리스트가 비어있는지 확인
return self.size == 0a = myStack()
print(a.isEmpty())
a.push(3)
print(a.isEmpty(), a.getSize(), a.top())
a.push(5)
print(a.isEmpty(), a.getSize(), a.top())
a.pop()
print(a.isEmpty(), a.getSize(), a.top())
a.pop()
print(a.isEmpty(), a.getSize(), a.top())
'문돌이 존버 > 프로그래밍 스터디' 카테고리의 다른 글
| Binary Search Tree, 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (8) (0) | 2021.02.09 |
|---|---|
| Hash table, 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (7) (0) | 2021.02.08 |
| Sorting 알고리즘 구현 예제 코드 모음집 (0) | 2021.02.01 |
| Merge sort, Quick sort비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (5) (0) | 2021.01.31 |
| Search, Sort 비전공자 문돌이가 설명하는 파이썬(Python) 기본 문법 (4) (0) | 2021.01.27 |
