one Book a Day

LIS는 예전에는 dp를 통해 이전값들을 검사해주며 모든 count를 계산해 풀었다면 이제는 이진탐색으로 직접dp수열을 관리하며 들어가야할 자리를 찾고 나보다 큰수는 나로 교체해주는 식으로 진행된다. 물론 내가 제일 크다면 그냥 오른쪽에 append한다. 이렇게하면 최종 dp에 남는 수열은 LIS는 안되지만 그 길이는 lis의 길이이다. 알고리즘은 의외로 heap을쓰는 회의실 배정문제와 비슷한 편. from bisect import bisect_left #이진탐색 코드, 같은 수일 경우 왼쪽 index를 돌려준다 input() A = list(map(int, input().split())) dp = [] for i in A: k = bisect_left(dp, i) #자신이 들어갈 위치 k if len(..

이진트리?? 최대 두개의 자식 노드를 가지는 트리형태의 자료구조. 단순 저장보다는 탐색혹은 정렬을 위함. 힙도 이진트리의 일종. 이진 탐색트리? 이진트리의 특수한 경우. 모든 노드에 대해 그 왼쪽 자식들의 값이 현재 노드보다 작거나 같으며 오른쪽 자식들의 값이 현재 노드의 값보다 크다는 조건을 만족하면 이진 탐색 트리가 된다(작은값은 왼쪽 큰값은 오른쪽에 저장.) 가장 처음 입력된 값이 root 클래스 정의, 초기화 노드 클래스 정의 class Node(object): def __init__(self, data): self.data = data self.left = self.right = None 이진 탐색 트리 클래스 정의 class BinarySearchTree(object): def __init__..