array = [5,7,9,0,3,1,6,2,4,8]
def quick(array):
if(len(array) <= 1):
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
#print(pivot)
#print(left_side)
#print(right_side)
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
return quick(left_side) + [pivot] + quick(right_side)
print(quick(array))
이진 트리: 이진 트리의 순회는 재귀 호출을 사용한다. 따라서 전위, 중위, 후위 순회를 간단하게 구현할 수 있다. 순회란 모든 원소를 빠트리거나 중복하지 않고 처리하는 연산을 의미한다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def __str__(self):
return str(self.data)
class Tree:
def __init__(self):
self.root = None
def preorderTraversal(self, node):
print(node, end='')
if not node.left == None : self.preorderTraversal(node.left)
if not node.right == None : self.preorderTraversal(node.right)
def inorderTraversal(self, node):
if not node.left == None : self.inorderTraversal(node.left)
print(node, end='')
if not node.right == None : self.inorderTraversal(node.right)
def postorderTraversal(self, node):
if not node.left == None : self.postorderTraversal(node.left)
if not node.right == None : self.postorderTraversal(node.right)
print(node, end='')
def makeRoot(self, node, left_node, right_node):
if self.root == None:
self.root = node
node.left = left_node
node.right = right_node
if __name__ == "__main__":
node = []
node.append(Node('-'))
node.append(Node('*'))
node.append(Node('/'))
node.append(Node('A'))
node.append(Node('B'))
node.append(Node('C'))
node.append(Node('D'))
m_tree = Tree()
for i in range(int(len(node)/2)):
m_tree.makeRoot(node[i],node[i*2+1],node[i*2+2])
print( '전위 순회 : ', end='') ; m_tree.preorderTraversal(m_tree.root)
print('\n' + '중위 순회 : ', end='') ; m_tree.inorderTraversal(m_tree.root)
print('\n' + '후위 순회 : ', end='') ; m_tree.postorderTraversal(m_tree.root)
전위 순회
전위 순회는DLR순서로 순회한다.
D: 현재 노드를 출력한다
L: 현재 노드 왼쪽 서브트리로 이동한다
R: 현재 노드 오른쪽 서브트리로 이동한다
def preorderTraversal(self, node):
print(node, end='')
if not node.left == None : self.preorderTraversal(node.left)
if not node.right == None : self.preorderTraversal(node.right)
해당 노드를 출력하고 왼쪽으로 이동한다. 왼쪽 노드가 존재하면 계속해서 왼쪽으로 이동하여 출력하고 왼쪽이 끝나는 노드부터 오른쪽 노드를 순회한다.
중위 순회
중위 순회는LDR순서로 순회한다. 왼쪽 순회가 우선이고 출력이 중앙에 위치한다.
def inorderTraversal(self, node):
if not node.left == None : self.inorderTraversal(node.left)
print(node, end='')
if not node.right == None : self.inorderTraversal(node.right)
후위 순회
후위 순회는LRD로 순회한다. 출력이 마지막에 위치한다.
def postorderTraversal(self, node):
if not node.left == None : self.postorderTraversal(node.left)
if not node.right == None : self.postorderTraversal(node.right)
print(node, end='')
가장 처음에 insert()할 때, self.head = None이다. 따라서 self.head = Node(x, key)를 수행한다.
나중에 insert()할 때, While문으로 들어간다.
class Node:
def __init__(self, x, key):
self.x = x
self.key = key
self.left = None
self.right = None
class Tree:
....
def insert(self, x, key):
current_node = self.head
if self.head is None:
self.head = Node(x, key)
....
while True:
if current_node.x > x:
if current_node.left:
current_node = current_node.left
else:
current_node.left = Node(x, key)
break
else:
if current_node.right:
current_node = current_node.right
else:
current_node.right = Node(x, key)
break
while문에서
현재의 node의 x값이 insert할 x값보다 클 때, 현재 node의 left에 무엇인가 담겨있다면 현재의 node에 현재의 node 왼쪽값을 담는다.(왼쪽 아래로 비어있을 때까지 이동) // 현재 node의 left가 비어있다면 insert할 Node(x, key)를 넣어주고 break한다.
현재의 node의 x값이 insert할 x값보다 작을 때, 현재 node의 오른쪽에 무엇인가 담겨있다면 현재의 node에 현재의 node 오른쪽값을 담는다.(오른쪽 아래로 비어있을 때까지 이동) // 현재 node의 오른쪽이 비어있다면 insert할 Node(x,key)를 넣어주고 break한다.
my_list = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
# 한 리스트에 몇개씩 담을지 결정
n = 3
result = [my_list[i * n:(i + 1) * n] for i in range((len(my_list) + n - 1) // n )]
print(result)
NOTATION = '0123456789ABCDEF'
def numeral_system(number, base):
q, r = divmod(number, base)
n = NOTATION[r]
return numeral_system(q, base) + n if q else n
지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.
어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.
입력 형식
캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
cacheSize는 정수이며, 범위는 0 ≦cacheSize≦ 30 이다.
cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.
def solution(cacheSize, cities):
answer = 0
cache = []
if cacheSize == 0:
return len(cities) * 5
for city in cities:
if city.lower() in cache: # cache에 있을 때
answer+=1
cache.remove(city.lower())
cache.append(city.lower())
else: # cache에 없을 때
answer+=5
if len(cache) == cacheSize:
cache.pop(0)
cache.append(city.lower())
else:
cache.append(city.lower())
return answer
