computer science (8) 썸네일형 리스트형 polymorphism - overriding & virtual keyword - late binding #include using namespace std; class base { public: void fun_1() { cout DP-3 LIS (백준 11053) 개념 링크: Longest Increasing Subsequence | DP-3 - GeeksforGeeks We have discussed Overlapping Subproblems and Optimal Substructure properties. Let us discuss Longest Increasing Subsequence (LIS) problem as an example problem that can be solved… Read More » www.geeksforgeeks.org 문제 링크: 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우.. Arrays in C When list[i] occurs on the RHS of '=' in an assignment statement, a dereference takes place and the value pointed at by (list+i) is returned. If list[i] appears on the LHS of '=', then the value produced on the right-hand side is stored in the location (list+i). 성능 측정(Perfomance Measurement) #include 방법1 방법2 Start timing Start=clock(); Start=time(NULL); Stop timing Stop=clock(); Stop=time(NULL); Type returned Clock_t Time_t Result in seconds Duration = ((double)(stop-start))/CLOCKS_PER_SEC; Duration = (double) difftime(stop, start); 1.4.3 점근 표기법(Asymptotic Notation) 균형분기점(Break Even Point) 두 프로그램의 연산량를 같게 만드는 입력의 크기 두 프로그램의 Program Counter가 각각 : n^2 + 2*n, 100*n이라고 하면 n이 98일 때 두 프로그램의 연산량이 같아진다. 빅오 표기법(Big O notation) f(n) = O(g(n)), iff there exist positive constants c and n0 such that f(n) = n0 . 오메가 표기법(Omega Notation) f(n) = Ω(g(n)), iff there exist positive constants c and n0 such that f(n) = n0 . 세타 표기법(Theta Notation) f(n) = Θ(g(n)), iff there exist .. 1.4.2 Program Step increment program steps upon encountering; a if statement each iteration of a loop(including the iteration for exiting the loop) a return statement any kind of assignment statement However, any subset of above items whose size is constant might be considered as 1 자료구조 인덱스 Basic Concepts System Life Cycle Algorithm Specification Introduction Recursive Algorithms 이진탐색(Binary Search) Data Abstraction Performance Analysis Space Complexity Time Complexity Program Counter 점근 표기법(Asymptotic Notation) Practical Complexities 성능 측정(Perfomance Measurement) 1.2.2 이진 탐색(Binary Search) 벡터의 크기, 탐색 대상, 벡터의 원소들을 입력 받아 이진탐색 결과 탐색 대상이 벡터에 존재한다면 상응하는 인덱스를, 존재하지 않는다면 -1을 반환한다. 입력 방식에는 임의로 벡터를 생성하는 RAND_INUT과 표준입출력으로 벡터를 생성하는 STD_INPUT이 있다. 두 입력 방식은 동시에 사용할 수 없으며, 전자가 기본값으로 설정되어 있다. 후자를 사용하기 위해서는 맨 윗줄 #define RAND_INPUT를 주석처리해서 #define STD_INPUT을 활성화시키면 된다. 탐색 방식에는 ITER_SEARCH와 RECUR_SEARCH있다. 각각 반복과 재귀 방식으로 탐색한다. 두 탐색 방식은 함께 사용할 수 있기 때문에 #ifndef로 상호배제하지 않도록 했으며, 둘 다 사용하는 것이 기본값이다. #d.. 이전 1 다음
