해킹왕 양선규

분할 정복(Divide and Conquer) - 여러 알고리즘의 기본이 되는 해결 방법, 엄청나게 크고 방대한 문제를 작은 단위로 쪼개어, 결과적으로 큰 문제를 해결하는 방법 - 퀵 정렬, 병합 정렬, 이분 탐색 등이 대표적 예시이다. - Divide를 제대로 나누면 Conquer은 자동으로 쉬워지기 때문에 Divide를 잘 설계하는 것이 매우 중요하다. - 분할 정복에서는 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할 정복의 효율을 깎아내릴 수 있다. 분할 정복의 설계 1. Divide(분할) - 원래의 문제를 분할하여, 비슷한 유형의 하위 문제로 더 이상 분할이 불가능할 때 까지 나눈다. 2. Conquer(정복) - 각 하위 문제를 재귀적으로 해결한다. 더 이상 나눌 수 없는 단위일 때의 탈..

from collections import deque import sys def DFS(graph, v, visited): # 인접노드리스트, 시작 노드, 방문목록 visited[v] = True print(v, end=' ') for i in graph[v]: # 현재 노드의 인접 노드로 재귀 if visited[i] == False: # 아직 안 갔으면 가기 DFS(graph, i, visited) def BFS(graph, start, visited): # 인접노드리스트, 시작 노드, 방문목록 queue = deque([start]) # 큐에 시작 노드 넣기 visited[start] = True while queue: v = queue.popleft() # 큐에서 노드 빼고 출력 print(v, ..

import sys sys.setrecursionlimit(10**9) # 재귀호출 최대 깊이를 늘려준다 pre = [] # 전위순회 순서 입력받기 while True: try: n = int(sys.stdin.readline()) pre.append(n) except: break def postOrder(nodeList): # 전위순회 결과를 입력받는다 생각지 말고, 그냥 노드 리스트를 입력받는다 생각하면 이해가 편함 if len(nodeList) == 0: # 빈 리스트라면 return return left, right = [], [] root = nodeList[0] # root노드 기준으로 작은값, 큰값으로 나눈다 for i in range(1, len(nodeList)): # root노드 다음값..

import sys n = int(sys.stdin.readline()) tree = {} for _ in range(n): root, left, right = sys.stdin.readline().split() tree[root] = [left, right] # {'root' : ['left', 'right']} 형태로 저장한다 def preorder(root): # 전위 순회 if root != '.': print(root, end='') preorder(tree[root][0]) preorder(tree[root][1]) def inorder(root): # 중위 순회 if root != '.': inorder(tree[root][0]) print(root, end='') inorder(tree[r..