해킹왕 양선규

이진 탐색 트리(Binary Search Tree, BST) - 왼쪽 서브트리는 부모 노드보다 작고 오른쪽 서브트리는 부모 노드보다 큰 이진 트리 - BST의 최소값은 “트리의 가장 왼쪽”에 존재한다 - BST의 최대값은 “트리의 가장 오른쪽”에 존재한다 이진 탐색 트리의 삽입 - 아무것도 없는 트리라면 그냥 삽입한다. - 삽입할 노드를 루트 노드부터 하나씩 비교한다. 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 빈 자리를 찾을 때 까지 반복한다. - 같은 값을 가지는 노드는 없다. 이진 탐색 트리의 삭제/검색 - 삭제를 하려면 검색부터 해야 한다. - 찾을 노드를 기준으로, 루트 노드부터 하나씩 비교한다. 삽입할 때처럼 루트 노드보다 작다면 왼쪽, 크다면 오른쪽으로 간다. 값이 같다면 해당 노..

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

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노드 다음값..