너와 나의 스토리

Summary Class P: 해당 문제를 다항 시간에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합 Class NP: 해당 문제를 해결하는 Non-deterministic 다항 시간 알고리즘이 존재하는 문제. 어떤 certificate를 다항시간에 verification할 수 있으면, 그 문제는 class NP에 속함 Class P The set of decision problems that are polynomially bounded 해당 문제(P)를 다항시간에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합 다항 시간: 시간 복잡도가 $O(n^k)$, k가 상수 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로,..

Background binary tree / binary search tree -> data structure binary search tree는 순서 조건 만족해야 함 binary search -> algorithm Binary Search Tree property Binary search tree를 inorder traversal(왼쪽부터 탐색)하면 결과적으로 오름차순으로 정렬됨 balanced tree일 경우 어떤 데이터를 찾을 때 O(log n) 시간이 걸린다. 하지만 long chain tree 구조이면, 어떤 데이터를 찾을 때 O(n) 시간이 걸린다. -> 한 방향으로 쭉 늘어진 형태 Binary Tree Rotations 기술을 사용해서 트리를 균형 있게 만들 수 있다 ex) AVL tree..

Array doubling 사이즈가 n인 배열 A가 있다고 하자. A가 꽉 찼을 때, push가 들어온다면 사이즈가 두 배인(2n) 배열 B를 만들어, 배열 A에 있는 것들을 옮기고, 새로운 데이터를 push한다. 이때, (n*t+1)만큼의 연산을 한다. t: A에서 B로 데이터를 하나 옮기는데 드는 시간 1: 새로 들어온 데이터는 처음부터 B로 들어감 그렇다면, push 연산의 시간 복잡도는 O(n)이다. 하지만, doubling은 가끔씩만 발생하는데 O(n)으로 취급하기는 아깝다 ㅠㅠ -> Amortized Analysis를 하자! Amortized Analysis worst case 분석 연속해서 연산이 발생할 때, 최악의 경우의 평균 연산을 고려한다. Average Analysis와의 차이 Ave..