큐
데크와 회문
데크를 사용하면 문장이 회문인지 쉽게 확인할 수 있다.
내 정답:
from deque import Deque
def check_palindrome(string):
d = Deque()
for i in string:
d.enqueue_back(i)
h_leng = d.size() // 2
for i in range(h_leng):
if d.dequeue() == d.dequeue_front():
continue
else:
return False
return True
palindrome = '다시합창합시다'
not_palindrome = '안녕하세요'
print(check_palindrome(palindrome))
print(check_palindrome(not_palindrome))
책의 정답:
STRIP = string.whitespace + string.punctuation + "\"'"
def check_palindrome_answer_book(str1):
d = Deque()
for s in str1.lower():
if s not in STRIP:
d.enqueue(s)
eq = True
while d.size() > 1 and eq:
if d.dequeue_front() != d.dequeue():
eq = False
return eq
책은 띄어쓰기와 따옴표 모두 신경써 주는 듯 하다. 따라서 내 코드도 다음과 같이 바꿔주었다.
def check_palindrome(string):
temp = string.lower()
d = Deque()
for i in temp:
if not i in " '\"":
d.enqueue_back(i)
else:
continue
h_leng = d.size() // 2
for i in range(h_leng):
if d.dequeue() == d.dequeue_front():
continue
else:
return False
return True
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_queue_palindrome_check.py"
True
False
큐와 동물 보호소
개와 고양이를 입양했다가 다시 출양하는 동물 보호소를 큐로 구현해 보자. 동물 보호소는 개와 고양이를 지정하여 입출양할 수 있어야 한다.
from queue import Queue
class AnimalShelter(object):
def __init__(self):
DogQ = Queue()
CatQ = Queue()
self.set = [DogQ, CatQ]
def size(self):
return (self.set[0].size(), self.set[1].size())
def enqueue_dog(self, name):
self.set[0].enqueue(name)
def dequeue_dog(self):
value = self.set[0].dequeue()
if value is not None:
return value
else:
print("Got no Dog...")
def enqueue_cat(self, name):
self.set[1].enqueue(name)
def dequeue_cat(self):
value = self.set[1].dequeue()
if value is not None:
return value
else:
print("Got no Cat...")
def peek_dog(self):
value = self.set[0].peek()
if value is not None:
return value
else:
print("Got no Dog...")
def peek_cat(self):
value = self.set[1].peek()
if value is not None:
return value
else:
print("Got no Cat...")
def __repr__(self):
return repr(self.set)
s = AnimalShelter()
s.enqueue_cat('Kitty')
s.enqueue_cat('Nabi')
s.dequeue_cat()
s.enqueue_dog('Dangdang')
s.dequeue_dog()
s.dequeue_dog()
print(s)
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_queue_animal_shelter.py"
Queue is empty.
Got no Dog...
[[], ['Nabi']]
연결 리스트
끝에서 k번째 항목 찾기
연결 리스트의 끝에서 k번째 항목을 찾아보자.
책의 정답:
from linkedListFIFO import LinkedListFIFO
from node import Node
class KthFromLast(LinkedListFIFO):
def find_kth_to_last(self, k):
p1, p2 = self.head, self.head
i = 0
while p1:
if i > k-1:
try:
p2 = p2.pointer
except AttributeError:
break
p1 = p1.pointer
i += 1
return p2.value
k = KthFromLast()
for i in range(1, 11):
k.addNode(i)
k._printList()
k_from_last = k.find_kth_to_last(3)
print(k_from_last)
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_find_kth_from_the_end.py"
a
b
1 2 3 4 5 6 7 8 9 10
8
연결 리스트 분할하기
숫자가 담긴 연결 리스트에서 한 항목을 선택했을 때, 그 항목 값의 왼쪽에는 작은 숫자 항목만 나오고 오른쪽에는 큰 숫자 항목만 나오도록 연결 리스트를 분할해보자. 즉, 예를 들어 연결리스트가 다음과 같고 6을 기준으로 나눈다면,
분할 전
6 7 3 4 9 5 1 2 8
분할 후
3 4 5 1 2 6 2 9 8
이와 같이 되야한다.
내 정답:
from linkedListFIFO import LinkedListFIFO
def part_linked_list(ll, n):
result_ll = LinkedListFIFO()
ll_temp = ll
node = ll_temp.head
i = 0
while node:
if node.value < n:
result_ll.addNode(node.value)
ll_temp.deleteNode(i)
elif node.value == n:
ll_temp.deleteNode(i)
else:
i += 1
node = node.pointer
result_ll.addNode(n)
node = ll_temp.head
while node:
result_ll.addNode(node.value)
node = node.pointer
return result_ll
ll_test = LinkedListFIFO()
for i in [4,7,2,9,8,5,2,4,1]:
ll_test.addNode(i)
part_linked_list(ll_test, 5)._printList()
책의 정답:
def part_linked_list_answer_book(ll, n):
more = LinkedListFIFO()
less = LinkedListFIFO()
node = ll.head
while node:
item = node.value
if item < n:
less.addNode(item)
elif item > n:
more.addNode(item)
node = node.pointer
less.addNode(n)
nodemore = mode.head
while nodemore:
less.addNode(nodemore.value)
nodemore = nodemore.pointer
return less
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_ll_part_linked_list.py"
4 2 2 4 1 5 7 9 8
기본적으로 코드를 들여다 봤을 때 메커니즘 자체는 비슷하지만 내 풀이 방식은 인덱스를 더했기 때문에 좀 더 보기 어렵고 난해할 수 있다. 책의 코드가 훨씬 직관적이고 알아보기 쉽다.
이중 연결 리스트와 FIFO
linkedListFIFO 코드를 사용하여 이중 연결 리스트를 구현해보자. 우리가 배운 연결 리스트는 단일 연결 리스트 (singly linked list) 로써, 각 노드의 포인터 하나가 다음 노드를 가리키지만, 이중 연결 리스트 (doubly linked list) 에서는 포인터가 두 개 있어 하나는 앞 노드를, 하나는 뒤 노드를 가리킨다. Node가 단일 포인터 노드를 쓰는 대신, 앞 노드 (previous) 와 뒤 노드 (pointer) 모두를 가리키도록 만들면 된다.
회문 확인하기
앞에서는 데크를 사용하여 회문 여부를 확인했다. 이번에는 연결 리스트가 회문인지 확인해보는 코드를 작성해보자.
내 정답:
from linkedListFIFO import LinkedListFIFO
def ll_check_palindrome(string):
str_temp = ''
for i in string.lower():
if not i in ' \'"':
str_temp += i
else:
continue
mid_i = len(str_temp) // 2
from_fwd_ll = LinkedListFIFO()
from_back_ll = LinkedListFIFO()
for i in range(mid_i):
from_fwd_ll.addNode(str_temp[i])
from_back_ll.addNode(str_temp[-1-i])
fwd_node = from_fwd_ll.head
back_node = from_back_ll.head
while fwd_node and back_node:
if fwd_node.value == back_node.value:
fwd_node = fwd_node.pointer
back_node = back_node.pointer
else:
return False
return True
palindrome = 'Madam I\'m Adam'
not_palindrome = 'Hello World!'
print(ll_check_palindrome(palindrome))
print(ll_check_palindrome(not_palindrome))
책의 정답
def isPal(l1):
if len(l1) < 2:
return True
if l1[0] != l1[-1]:
return False
return isPal(l1[1:-1])
def checkllPal(ll):
node = ll.head
l = []
while node is not None:
l.append(node.value)
node = node.pointer
return isPal(l)
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_ll_check_palindrome.py"
True
False
책에서는 위와 같이 리스트로 취급을 하여 리스트의 첫 아이템과 마지막 아이템이 일치하는지, 일치 한다면 1과 -1 인덱스 안에 있는 리스트를 사용해 재귀함수를 돌리는 방식으로 하였다. 그런데 개인적으로 이 경우 굳이 연결 리스트를 써야하는지 의문이 있다. 그냥 리스트 그대로 넣어도 동작이 될텐데, 아무튼 책에선 이렇게 풀었다.
두 연결 리스트의 숫자 더하기
연결 리스트의 각 항목은 양의 정수라고 가정하자. 한 연결 리스트의 항목으로 예를 들어 1, 7, 6, 2가 추가되었다면 이 연결 리스트의 숫자는 2671이다. 두 연결 리스트의 숫자를 더하여 숫자 결과를 출력하는 코드를 작성해보자.
내 정답:
from linkedListFIFO import LinkedListFIFO
def sum_linked_list(ll1, ll2):
# 연결 리스트: 숫자 2671의 경우 1 7 6 2 순으로 되어있다.
ll_result = LinkedListFIFO()
node_1 = ll1.head
node_2 = ll2.head
def node_val_or_zero(node):
if not node is None and node.value:
return node.value
else:
return 0
def node_pointer_or_None(node):
if not node is None and node.pointer:
return node.pointer
else:
return None
pending = 0
while node_1 or node_2:
sum_val = node_val_or_zero(node_1) + node_val_or_zero(node_2) + pending
pending = 0
if sum_val < 10:
ll_result.addNode(sum_val)
else:
ll_result.addNode(sum_val - 10)
pending += 1
node_1 = node_pointer_or_None(node_1)
node_2 = node_pointer_or_None(node_2)
return ll_result
list_2671 = [1, 7, 6, 2]
list_355 = [5, 5, 3]
ll_2671 = LinkedListFIFO()
ll_355 = LinkedListFIFO()
for i in list_2671:
ll_2671.addNode(i)
for i in list_355:
ll_355.addNode(i)
ll_result = sum_linked_list(ll_2671, ll_355)
ll_result._printList()
결과:
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_ll_sum_linked_list.py"
6 2 0 3
2671 + 355 = 3026이고, 결과값 연결리스트는 6 2 0 3 (3026) 이 나왔으니 일단은 성공이다. 다만 살짝 지저분해졌다. 책의 정답을 보자.
class LinkedListFIFOYield(LinkedListFIFO):
def _printList(self):
node = self.head
while node:
yield node.value
node = node.pointer
def sumlls(l1, l2):
lsum = LinkedListFIFOYield()
dig1 = l1.head
dig2 = l2.head
pointer = 0
while dig1 and dig2:
d1 = dig1.value
d2 = dig2.value
sum_d = d1 + d2 + pointer
if sum_d > 9:
pointer = sum_d // 10
lsum.addNode(sum_d % 10)
else:
lsum.addNode(sum_d)
pointer = 0
dig1 = dig1.pointer
dig2 = dig2.pointer
if dig1:
sum_d = pointer + dig1.value
if sum_d > 9:
lsum.addNode(sum_d % 10)
else:
lsum.addNode(sum_d)
dig1 = dig1.pointer
if dig2:
sum_d = pointer + dig2.value
if sum_d > 9:
lsum.addNode(sum_d % 10)
else:
lsum.addNode(sum_d)
dig2 = dig2.pointer
return lsum
l1 = LinkedListFIFOYield()
l2 = LinkedListFIFOYield()
l1.addNode(1)
l1.addNode(7)
l1.addNode(6)
l1.addNode(2)
l2.addNode(5)
l2.addNode(5)
l2.addNode(3)
lsum = sumlls(l1, l2)
l = list(lsum._printList())
for i in reversed(l):
print(i, end="")
print()
결과
3026
책의 정답은 나와 달리, 둘 중 하나라도 노드의 값이 존재하지 않게 되면 (즉 자릿수가 맞는 계산들이 끝나면) 자릿수가 남아있는 연결 리스트의 노드를 가져와 계속 계산한다. 내 계산법은 노드가 존재 하지 않으면 (즉 나는 예를 들어 455라는 수를 0455로 변환한 것처럼 계산을 했던 것이다) 그 자리를 0으로 간주하고 계산을 계속했었다. 따라서 비효율적일 수 있는 방법이다.
원형 연결 리스트 찾기
헤드와 테일이 연결된 연결 리스트를 원형 연결 리스트 (circular linked list) 라고 한다. 어떤 연결 리스트가 원형 연결 리스트인지 여부를 확인하는 함수를 구현해보자. 두 포인터를 사용하면 원형 연결 리스트의 여부를 확인할 수 있다. 내 짧은 지식으론 이게 어떻게 구현 가능한지 가늠이 안간다. 책의 정답을 보자.
from linkedListFIFO import LinkedListFIFO
from node import Node
class CircularLinkedListFIFO(LinkedListFIFO):
def _add(self, value):
self.length += 1
node = Node(value, self.head)
if self.tail:
self.tail.pointer = node
self.tail = node
def isCircularll(ll):
p1 = ll.head
p2 = ll.head
while p2:
try:
p1 = p1.pointer
p2 = p2.pointer.pointer
except:
break
if p1 == p2:
return True
return False
ll = LinkedListFIFO()
for i in range(10):
ll.addNode(i)
print(isCircularll(ll))
lcirc = CircularLinkedListFIFO()
for i in range(10):
lcirc.addNode(i)
print(isCircularll(lcirc))
결과
PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/7. 추상 데이터 타입/eg_ll_circular_linked_list.py"
False
True
원형 연결 리스트는 위와 같이 구현되었다.
'Python > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 9-2. 로그 선형 정렬, 고급정렬 (Log-linear Sorting, Advanced Sorting) (0) | 2020.08.07 |
|---|---|
| 9-1. 2차 정렬과 선형 정렬 (Quadratic and Linear Sorting) : 파이썬 자료구조와 알고리즘 (0) | 2020.08.06 |
| 8. 점근적 분석 (Asymptotic Analysis): 파이썬 자료구조와 알고리즘 (0) | 2020.08.04 |
| 7-2-1. 스택 연습문제 (Stack Examples): 파이썬 자료구조와 알고리즘 (0) | 2020.08.03 |
| 7-1. 추상 데이터 타입 (Abstract Data Type): 파이썬 자료구조와 알고리즘 (0) | 2020.08.02 |
