728x90 Quality control (Univ. Study)197 Lecture4 - 점화식과 점근적 복잡도 분석 점화식의 이해 점화식이란 어떤 함수(보통 입력 변수를 n등의 미지수로 표현)를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 식이다. 병합 정렬 알고리즘을 통해 살펴보자 mergeSort(A[],p,r){ if(p 2023. 3. 8. Lecture3 - 알고리즘 설계와 분석의 기초(2) Big O relation d>c>1인 경우 b>1, c,d>0인 경우 b>1, d>0인 경우 c>b>1인 경우 합성 함수에서의 Big O relation Big Omega notation Ω(g(n))과 같이 표기하고 적어도 g(n)의 비율로 증가하는 함수라는 뜻으로 O(g(n))과 대칭적이라고 볼 수 있다. Formal definition은 Ω(g(n)) = { f(n) | ∃c > 0, n0 ≥ 0 s.t.∀n ≥ n0 , cg(n)≤f(n) }과 같은 방식으로 정의된다. 직관적으로 생각해보면 "f(n) = Ω(g(n)) ⇒ f는 g보다 느리게 증가하지 않는다"라고 생각할 수 있다. Big Theta notation Θ(g(n))과 같이 표기하고 정확히 g(n)의 비율로 증가하는 함수를 뜻한다. F.. 2023. 3. 6. Lecture1,2 - 알고리즘 설계와 분석의 기초(1) 알고리즘이란? 알고리즘이란 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 체계적 으로 기술한 것을 말한다. 다음은 문제, 입출력 및 알고리즘에 대한 간단한 예시이다. ▪ 문제: 100명의 학생들의 시험점수 중 최대값을 찾으라 ▪ 입력: 100명의 학생들의 시험점수 ▪ 출력: 위 100개의 시험점수들 중 최대값 ▪ 알고리즘: Algorithm maxScore(x[], n) { x[1...n]의 값을 차례대로 보면서 최대값을 계산 위에서 찾은 최대값을 반환 } 또한 현존하는 어떤 알고리즘으로도 polynomial시간 내에 최적의 해를 구할 수 없는 "Travelling Salesman Problem"도 있다. ▪ 입력: 어떤 영업사원이 방문해야 할 고객 n명의 위치 ▪ 출력: 모든 .. 2023. 3. 5. Lecture1,2-Vector Analysis(1) Scalar vs Vector Scalar: 크기만 존재하는 물리량 ex) temperature, time, ditance, mass, density, pressure, voltage... Vector: 크기와 방향이 모두 존재하는 물리량 ex) force, velocity, acceleration Scalar field: 스칼라장(스칼라 물리량의 위치별 분포) Vector field: 벡터장(벡터 물리량의 위치별 분포) Vector 벡터는 위와 같이 시점, 종점, 길이로 표현이된다. 벡터간의 연산은 다음과 같다. 벡터 연산도 결합법칙과 교환법칙이 성립된다. Vector Representation using Orthogonal Rectangular Unit Vectors 위의 방식처럼 벡터를 표현하면 다.. 2023. 3. 3. 자료구조론 과제(1) Array Stack 과제 ArrayStack.h #ifndef ARRAYSTACK_H #define ARRAYSTACK_H #include using namespace std; class StackEmpty { public: StackEmpty(const string& err) { } }; class StackFull { public: StackFull(const string& err) { } }; template class ArrayStack { enum { DEF_CAPACITY = 100 };// default stack capacity public: ArrayStack(int cap = DEF_CAPACITY);// constructor from capacity int size() const;/.. 2023. 2. 17. ArrayStack(3) postfix notation transformation 중위표기식을 후위 표기식으로 변환하는 코드이고 ArrayStack(1)의 헤더 파일을 이용한다. #include #include "ArrayStack.h" using namespace std; //후위표기식 변환 함수 string postfix_transform(ArrayStack& oper_stack, string infix) { string ans;//결과를 담아둘 ans 문자열 선언 ArrayStack checker_stack; //음수가 입력된 경우 error 처리 for (const char& check : infix) {//범위기반 반복문 사용 if (check == '-') {//음수일 가능성이 존재하는 -기호 조사 if (checke.. 2022. 11. 20. ArrayStack(2) stock_span 아래와 같이 n일수 만큼의 일련의 주식 시세표가 주여졌다고 가정했을 때, 특정일의 주가보다 작거나 같은 주가가 가장 길게 연속되는 날의 수를 조사하는 알고리즘이다. ArrayStack(1)글의 헤더파일을 이용한다. #include #include //vector STL #include "ArrayStack.h" using namespace std; //span을 computing하는 linear-time algorithm 함수 int computeSpans(vector p) { ArrayStack d;//빈 stack d 선언 int n = p.size();//integer n에 vector의 길이 대입 int h = 0;//계산용 인자 h를 0으로 초기화 int S[100];//각 .. 2022. 11. 19. OS (File System) File OS의 5대 개념 Interrupt, Process, File, Memory, I/O중 File에 대해 공부하였다. File system은 파일들을 disk에 효율적으로 저장하는 것을 목적으로 한다. 효율적으로 저장하는 것은 Space efficienty와 Time efficiency 두개로 나누어 고려한다. Space efficiency: Divide file into blocks, Store file blocks scattered in empty disk blocks Time efficiency: Remember file block location in Inode table Disk: collection of disk blocks (1 disk block = 1K byte) File: col.. 2022. 11. 18. ArrayStack(1) 괄호 매칭 ArrayStack을 이용하여 괄호 매칭 시스템을 만들어보았다. //ArrayStack Header Source Code #ifndef ARRAYSTACK_H #define ARRAYSTACK_H #include using namespace std; class StackEmpty { public: StackEmpty(const string& err) { } }; class StackFull { public: StackFull(const string& err) { } }; template class ArrayStack { enum { DEF_CAPACITY = 100 };// default stack capacity public: ArrayStack(int cap = DEF_CAPACITY);/.. 2022. 11. 18. 이전 1 ··· 17 18 19 20 21 22 다음 728x90
