실습_4. 자료구조의 끝판왕
Updated:
실습
팩토리얼 계산하기
팩토리얼(!) 은 하나의 정수를 n을 입력받고 n X n-1 X n-2 X …. X 1 을 반환하는 연산자입니다.
예를 들어서, 5! = 5 X 4 X 3 X 2 X 1 = 120 입니다.
팩토리얼 연산자를 파이선 함수로 구현 해 봅시다. 재귀(recursion)방법과 반복(iteration)방법의 두 가지 다른 방법으로 구현 해 보도록 합시다.
1! = 1, 0! = 1 입니다. 입력값은 0보다 크거나 같은 정수라고 가정합시다.
def factorial(num):
if num == 1:
return 1
return num * factorial(num-1)
def main():
print(factorial(5)) # should return 120
if __name__ == "__main__":
main()
피보나치 수
피보나치 수열은 N 번째 수가 N-1번째 수와 N-2번째 수의 합인 수열입니다. 즉, F(0) = 0, F(1) = 1이며 그 이외의 모든 F(n) = F(n-1) + F(n-2) 입니다.
예를 들어서 피보나치 수열을 0~ 10번째까지 적어보면
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
와 같습니다.
F(10) = F(9) + F(8) = 21 + 34 = 55 임을 확인 할 수 잇습니다.
0보다 크거나 같은 입력 정수 n이 주어졌을때 n번째 피보나치 수를 반환하는 함수를 구현 해 봅시다.
예를 들어서, 10이 입력으로 주어지면 55를 반환해야 합니다.
재귀 방법으로 구현 해 보도록 합시다. 메모이제이션도 활용 해 보도록 합시다.
class Fib():
def __init__(self):
self.memo = {}
def fibonacci(self, num):
self.memo[0] = 0
self.memo[1] = 1
for i in range(2, num+1):
self.memo[i] = self.memo[i-2]+self.memo[i-1]
return self.memo[num]
def main():
fib = Fib()
print(fib.fibonacci(10)) # should return 55
if __name__ == "__main__":
main()
이진 트리 출력하기
완벽한 이진 트리가 주어졌다고 합시다. 이때, 이 트리를 출력하기 좋은 형태로 반환하는 함수를 구현 해 봅시다. 위에서부터 순서대로, 트리의 각 층별로 하나의 배열을 만들고, 이 배열들의 배열을 반환하는 형태면 됩니다.
예를 들어서
1
2 3
와 같은 트리가 주어졌을 경우 [[1],[2,3]] 을,
1
2 3
4 5 6 7
과 같은 트리가 주어졌을 경우에는 [[1],[2,3],[4,5,6,7]]을 반환하면 됩니다.
import queue
#====이 문제를 풀기 위해 필요한 클래스와 함수들입니다. 따로 수정 할 필요는 없습니다.
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def listToCompleteBinaryTree(lst):
def helper(index):
if index >= len(lst):
return None
node = Node(lst[index])
node.left = helper(index * 2 + 1)
node.right = helper(index * 2 + 2)
return node
return helper(0)
#=================================================================================
def printTree(node):
all_lines = []
line = []
q = queue.Queue()
q.put(node)
q.put(Node(-1))
while q.qsize()!=0:
node_one = q.get()
if not node_one:
break
if node_one.val == -1:
all_lines.append(line)
line = []
q.put(Node(-1))
else:
line.append(node_one.val)
q.put(node_one.left)
q.put(node_one.right)
return all_lines
def main():
node = listToCompleteBinaryTree([1,2,3,4,5,6,7])
print(printTree(node)) # [[1], [2, 3], [4, 5, 6, 7]]
if __name__ == "__main__":
main()
트리의 경로의 합
완벽한 이진 트리가 주어졌다고 합시다. 그리고 어떤 합 숫자가 주어졌다고 합시다. 이때, 이 트리의 루트(root)에서부터 잎(leaf)까지의 가능한 경로들을 고려해서, 이 경로들 중 최소 하나 이상의 해당 경로상의 value들의 합산과 주어진 합 숫자가 일치하면 True를, 아니면 Fals를 반환하는 함수를 구현 해 봅시다.
예를 들어서,
1
2 3
와 같은 트리가 주어지고 3 값이 주어진다면 1->2 경로의 합이 3이기 때문에 True를 반환하면 됩니다.
1
2 3
4 5 6 7
과 같은 트리가 주어지고 8이 주어진다면 1->2->5 경로의 합이 8이기 때문에 True를 반환하면 됩니다. 하지만 만약 15가 주어진다면 해당 트리의 어떤 경로도 합산이 15가 되지 않기 때문에 False를 반환하면 됩니다.
깊이 우선 탐색을 활용 해 봅시다.
#====이 문제를 풀기 위해 필요한 클래스와 함수들입니다. 따로 수정 할 필요는 없습니다.
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def listToCompleteBinaryTree(lst):
def helper(index):
if index >= len(lst):
return None
node = Node(lst[index])
node.left = helper(index * 2 + 1)
node.right = helper(index * 2 + 2)
return node
return helper(0)
def printTree(node):
q = [Node(-1), node]
line = []
while q:
node = q.pop()
if not node:
continue
elif node.val == -1:
if len(line) > 0:
print(" ".join(line))
line = []
q.insert(0,Node(-1))
else:
q.insert(0,node.left)
q.insert(0,node.right)
line.append(str(node.val))
#=================================================================================
def path_sum(node, targetSum):
def dfsHelper(node, curSum):
# 여기에 깊이 우선 탐색을 구현 해 봅시다.
if not node:
if curSum == targetSum:
return True
return
curSum += node.val
if dfsHelper(node.left,curSum):
return True
if dfsHelper(node.right,curSum):
return True
if dfsHelper(node, 0):
return True
else:
return False
def main():
node = listToCompleteBinaryTree([1,2,3,4,5,6,7])
printTree(node)
print(path_sum(node, 8)) # return True
print(path_sum(node, 15)) # return False
if __name__ == "__main__":
main()
#
연결 리스트 뒤집기
단순 연결리스트의 head 노드가 입력으로 주어진다고 합시다.
이때 이 연결 리스트를 순회하면서 순서를 뒤집어서, 뒤집힌 연결 리스트의 head 노드를 반환하는 함수를 구현 해 봅시다.
예를 들어서, 연결리스트 2->8->19->37->4->5 가 주어졌다면 5->4->37->19->8->2 를 반환해야 합니다.
이 함수는 Node 객체를 입력으로 받는다는 것에 유의하세요. 배열로 변환 한 후, 뒤집고, 다시 새로운 연결 리스트를 만드는 것도 하나의 방법입니다. 하지만 더 (공간적으로)효율적인 구현법을 생각 해 보세요. 주어진 연결 리스트의 노드들을 그대로 사용하는 방식을 고려 해 보면 됩니다.
# 실습 3-3과 정의가 약간 바뀌었습니다. 유의하세요.
# 연결 리스트의 노드. 단일 연결 리스트의 경우입니다.
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
# head node가 주어졌을 때 해당 링크드리스트를 문자열로 변환해 주는 함수입니다.
def linkedListToStr(node):
toPrint = []
while node:
toPrint.append(str(node.val))
node = node.next
return "->".join(toPrint)
# 주어진 배열을 linkedlist로 변환해서 돌려줍니다. 실습 3-1을 참조하세요
def toLinkedList(lst):
ll = LinkedList(Node(lst[0]))
for i in range(1, len(lst)):
ll.addToEnd(Node(lst[i]))
return ll
####################################################################################################################################
# head 노드가 주어졌을 때, 해당 링크드 리스트를 뒤집은 후 뒤집힌 링크드 리스트의 헤드를 반환하는 함수를 구현 해 보세요.
def reverseLinkedList(head):
arr = []
while True:
arr.append(head.val)
head = head.next
if not head:
break
re_arr = []
for i in range(len(arr)-1,-1,-1):
re_arr.append(arr[i])
print(re_arr)
head = toLinkedList(re_arr).head
return head
def main():
nums = [2,8,19,37,4,5]
head_node = toLinkedList(nums).head
print(linkedListToStr(head_node)) # 2->8->37->4->5
reversed_head_node = reverseLinkedList(head_node)
print(linkedListToStr(reversed_head_node)) # 5->4->37->19->8->2
if __name__ == "__main__":
main()
주식 수익 최대화
주식 가격을 나타내는 숫자들의 배열이 주어집니다. 즉, 배열의 인덱스 i의 숫자가 해당 시간의 주식 가격입니다.
주식 한 주를 단 한번 사고 단 한번 팔 수 있다고 합시다. 이때 최대 수익을 구해내는 알고리즘을 구현 해 보세요.
예를 들어서,
1, 2, 3, 4, 5, 6, 7 과 같은 경우엔 1일때 사서 7일때 파는게 가장 이득입니다. 따라서 6을 반환하면 됩니다.
7, 6, 5, 4, 3, 2, 1 과 같은 경우에는 주식 가격이 쭉 하락했으므로, 이득을 낼 수 없습니다. 0을 반환하면 됩니다.
1, 2, 3, 4, 3, 2, 1 과 같은경우엔 1일때 사서 4일때 파는게 가장 이득입니다. 3을 반환하면 됩니다.
2, 8, 19, 37, 4, 5 와 같은경우엔 2일때 사서 37일때 파는게 가장 이득입니다. 35를 반환하면 됩니다.
def maximizeProfit(nums):
min_num = nums[0]
max_score = 0
for num in nums:
if min_num > num:
min_num = num
if min_num < num and num - min_num > max_score:
max_score = num-min_num
return max_score
def main():
print(maximizeProfit([1,2,3,4,5,6,7])) # 6
print(maximizeProfit([7,6,5,4,3,2,1])) # 0
print(maximizeProfit([1,2,3,4,3,2,1])) # 3
print(maximizeProfit([2,8,19,37,4,5])) # 35
if __name__ == "__main__":
main()
트리의 모든 경로
완벽한 이진 트리가 주어졌다고 합시다. 이때, 이 트리의 루트(root)에서부터 잎(leaf)까지의 가능한 모든 경로들을 반환하는 함수를 구현 해 봅시다.
가능한 경로상의 value들을 순서대로 포함한 배열들의 배열을 반환하면 됩니다.
예를 들어서,
1
2 3
과 같은 트리가 주어졌을 경우, [[1,2], [1,3]] 을 반환하면 되고,
1
2 3
4 5 6 7
과 같은 트리가 주어졌을 경우에는, [[1,2,4], [1,2,5], [1,3,6], [1,3,7]] 을 반환하면 됩니다.
깊이 우선 탐색을 활용 해 봅시다.
#====이 문제를 풀기 위해 필요한 클래스와 함수들입니다. 따로 수정 할 필요는 없습니다.
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def listToCompleteBinaryTree(lst):
def helper(index):
if index >= len(lst):
return None
node = Node(lst[index])
node.left = helper(index * 2 + 1)
node.right = helper(index * 2 + 2)
return node
return helper(0)
def printTree(node):
q = [Node(-1), node]
line = []
while q:
node = q.pop()
if not node:
continue
elif node.val == -1:
if len(line) > 0:
print(" ".join(line))
line = []
q.insert(0,Node(-1))
else:
q.insert(0,node.left)
q.insert(0,node.right)
line.append(str(node.val))
#=================================================================================
def all_paths(node):
all_paths = []
def dfsHelper(node, cur_path):
# 여기에 깊이 우선 탐색을 구현 해 봅시다.
if not node:
print(cur_path)
if cur_path not in all_paths:
all_paths.append(cur_path)
return
dfsHelper(node.left, cur_path+[node.val])
dfsHelper(node.right, cur_path+[node.val])
return
dfsHelper(node, [])
return all_paths
def main():
node = listToCompleteBinaryTree([1,2,3,4,5,6,7])
printTree(node)
print(all_paths(node))
if __name__ == "__main__":
main()
Leave a comment