실습_3. 심화된 자료구조
Updated:
실습
연결 리스트 <–> 배열 변환하기
연결 리스트 클래스 LinkedList와, 그 노드 클래스 Node가 주어졌습니다.
연결 리스트 객체가 주어졌을때 이를 배열로 변환해서 반환하는 함수 toArray와, 배열이 주어졌을때 이를 연결 리스트로 변환해서 반환하는 함수 toLinkedList를 구현 해 봅시다.
연결 리스트에서 노드 삭제하기
연결 리스트가 주어지고, 이 연결리스트에서 삭제하고 싶은 노드의 값이 주어졌다고 해 봅시다.
연결 리스트를 순회하면서 해당 노드를 찾아서, 삭제하는 함수를 만들어 봅시다.
주어진 연결 리스트에서 직접 삭제를 시행하면 되기 때문에, 해당 연결 리스트를 반환 할 필요는 없습니다.
# 연결 리스트의 노드. 단일 연결 리스트의 경우입니다.
class Node:
def __init__(self, val):
self.val = val
self.next = None
def __str__(self):
return str(self.val)
# 연결 리스트 클래스. head 와 tail을 가지고 있으며, 가장 뒤에 새로운 노드를 추가하는 addToEnd 함수가 있습니다.
class LinkedList:
def __init__(self, head):
self.head = head
self.tail = head
def addToEnd(self, node):
self.tail.next = node
self.tail = node
def __str__(self):
node = self.head
toPrint = []
while node:
toPrint.append(str(node.val))
node = node.next
return "->".join(toPrint)
####################################################################################################################################
# 주어진 연결 리스트 ll을 배열로 변환해 봅시다.
# 이때 연결 리스트 LinkedList의 객체가 입력으로 주어진다고 가정합니다.
def toArray(llNode):
arr = []
it = llNode.head
while it !=llNode.tail:
arr.append(it.val)
it = it.next
arr.append(it.val)
return arr
# 주어진 배열을 연결 리스트로 변환 해 봅시다.
def toLinkedList(lst):
print(lst)
li = LinkedList(Node(lst[0]))
for i in range(1,len(lst)):
li.addToEnd(Node(lst[i]))
print("asd",li)
return li
def deleteNode(ll, valToDelete):
if ll.head.val == valToDelete:
ll.head = ll.head.next
curNode = ll.head
nextNode = curNode.next
while nextNode:
if nextNode.val == valToDelete:
curNode.next = nextNode.next
if nextNode == ll.tail:
ll.tail = curNode
break
curNode = curNode.next
nextNode = curNode.next
return ll
def example():
## Linkedlist 클래스와 Node 클래스를 사용하는 예시입니다.
ll = LinkedList(Node(3))
ll.addToEnd(Node(4))
ll.addToEnd(Node(8))
print(ll)
print(ll.head)
print(ll.tail)
def main():
example()
nums = [2,8,19,37,4,5]
ll = toLinkedList(nums)
print(ll)
deleteNode(ll, 19)
print(ll) # 19를 삭제하였으므로, 2->8->37->4->5
deleteNode(ll, 3)
print(ll) # 3이 없으므로, 2->8->37->4->5
lst = toArray(ll)
print(lst)
if __name__ == "__main__":
main()
스트리밍 데이터의 이동 평균
정수 데이터가 스트리밍으로 (한번에 하나씩) 주어진다고 합시다. 이때, 주어진 범위 만큼의 이동 평균을 구하는 클래스 MovingAvg를 만들어 봅시다.
MovingAvg는 처음에 이동 평균의 범위를 입력받아서 초기화 되며, 매 정수 데이타가 입력되는 nextVal(num)함수는 이때까지의 이동 평균을 반환합니다.
예를 들어서, 2,8,19,37,4,5 의 순서로 데이터가 입력되고, 이동 평균의 범위는 3이라고 합시다. 이 경우 다음과 같이 MovingAvg가 사용 될 것입니다.
ma = MovingAvg(3)
print(ma.nextVal(2))
# 현재까지 입력된 값이 2밖에 없으므로, 2를 반환합니다.
print(ma.nextVal(8))
# 현재까지 입력된 값이 2와 8이므로, (2 + 8) / 2 = 5 를 반환합니다.
print(ma.nextVal(19))
# (2 + 8 + 19) / 3 = 9.666666666666666 를 반환합니다.
print(ma.nextVal(37))
# 이동 평균의 범위가 3이므로, 지난 3개의 값의 평균 (8 + 19 + 37) / 3 = 21.333333333333332 을 반환합니다.
print(ma.nextVal(4))
# (19 + 37 + 4) / 3 = 20 을 반환합니다.
print(ma.nextVal(5))
# (37 + 4 + 5) / 3 = 15.333333333333334 를 반환합니다.
import queue
class MovingAvg():
def __init__(self, size):
self.size = size
self.que = queue.Queue()
self.sum = 0
def nextVal(self, num):
if self.que.qsize() < self.size:
self.que.put(num)
self.sum += num
return self.sum / self.que.qsize()
else :
self.que.put(num)
self.sum += num
self.sum -= self.que.get()
return self.sum /self.size
print(self.que.qsize(), self.sum)
return self.sum / self.que.qsize()
def queueExample():
q = queue.Queue()
q.put(1)
q.put(2)
print(q.qsize())
print(q.get())
print(q.qsize())
print(q.get())
def main():
# queueExample()
nums = [2,8,19,37,4,5]
ma = MovingAvg(3)
results = []
for num in nums:
avg = ma.nextVal(num)
results.append(avg)
print(results) # [2.0, 5.0, 9.666666666666666, 21.333333333333332, 20.0, 15.333333333333334]
if __name__ == "__main__":
main()
괄호 매칭
(, ), {, }, <, >, [, ] 의 여덟개의 문자로만 구성된 문자열이 입력으로 주어진다고 해 봅시다.
이때, 이 문자열이 유효한지를 확인하는 함수를 작성 해 보세요.
열린 괄호들이 닫히는 순서가 올바르게 되어 있는 경우에 그 문자열을 유효하다고 합니다.
즉, ({()}) 나 [<>{} 등은 유효한 문자열이며, )( <] <(>) 등은 유효하지 않은 문자열입니다.
def isParenthesisValid(st):
stack = []
pDic = {'}':'{',']':'[',')':'(','>':'<'}
pOpens = {'{','[','(','<'}
for ch in st:
if ch in pOpens: # ch가 열린 괄호
skack.append(ch)
else: # ch가 닫힌 괄호
if len(stack) != 0 and stack[-1] = pDic[ch]:
stack.pop()
else:
reutn False
return True
def main():
examples = ["({()})", "[]<>{}", ")(" "<]", "<(>)"]
for example in examples:
print(example, isParenthesisValid(example))
if __name__ == "__main__":
main()
미션
조세퍼스 순열
입력으로 두 숫자가 들어오면 조세퍼스 순열을 구하는 함수를 작성해 봅시다.
조세퍼스 순열이 무엇인가 어렵게 느껴지지만 알고보면 쉽습니다.
사람이 7명이 둘러 앉아 있다고 생각해 봅시다. (캠프파이어를 상상해 보세요.) 이때 3번째 사람이 나갑니다. 그후 그 다음 3번째 사람이 나가고 다음 3번째 사람이 나가는 것을 모두가 나갈 때가지 반복해봅시다. 그러면 차례대로 3, 6, 2, 7, 5, 1, 4번째 사람이 나가게 될 것입니다.
이때 사람이 나간 순서가 7, 3의 조세퍼스 순열입니다.
입력 예시
josephus(7,3)
출력 예시
[3, 6, 2, 7, 5, 1, 4]
import queue
def josephus(num, target):
q = queue.Queue()
for i in range(1,num+1):
q.put(i)
arr = []
if target == 1:
while True:
arr.append(q.get())
if len(arr) == num:
return arr
else:
cnt = 0
while q.qsize() != 0:
cnt += 1
if cnt == target:
cnt = 1
arr.append(q.get())
if len(arr) == num:
break
q.put(q.get())
return arr
def main():
print(josephus(7, 3)) #[3, 6, 2, 7, 5, 1, 4]이 반환되어야 합니다
if __name__ == "__main__":
main()
스택 수열
스택에 1부터 N까지 차례대로 넣었다가 뽑아 리스트에 넣습니다. 이때 모두 넣은뒤 모두 뽑는것이 아닌 넣는 과정과 뽑는 과정을 섞어서 진행할 수도 있습니다. 이때 만들어진 수열을 스택 수열이라고 합시다.
1부터 N까지의 수로 이루어진 리스트가 주어집니다. 이때 이 리스트가 스택수열인지 검사하는 함수를 만들어 봅시다.
예를 들어 [2, 1, 4, 3]은 스택 수열입니다. 1넣기 -> 2넣기 -> 2뽑기 -> 1뽑기 -> 3넣기 -> 4넣기 -> 4뽑기 ->3뽑기 의 과정을 거치면 만들어 질 수 있기 때문입니다.
그러나 [3, 1, 2, 4]는 스택 수열이 아닙니다. 위에 나온 스택수열을 만드는 방법으로는 어떻게 해도 만들 수 없기 때문입니다.
def isStackSequence(nums):
stack = []
cnt = 0
check = False
for i in range(1, len(nums) + 1):
stack.append(i)
#print("??", stack, i)
while len(stack) > 0 and stack[-1] == nums[cnt] :
stack.pop()
cnt+=1
# if cnt == len(nums):
# check = True
# break
# if check:
# break
if len(stack) == 0:
return True
else:
return False
def main():
print(isStackSequence([2, 1, 4, 3])) # True가 리턴되어야 합니다
print(isStackSequence([3, 1, 2, 4])) # False가 리턴되어야 합니다
if __name__ == "__main__":
main()
Leave a comment