728x90 Quality control (Univ. Study)196 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. OS (pthread) fork의 return값은 child에서 0이고 parent는 pid이다. 0인경우와 그렇지 않은 경우로 조건문을 나누었으나 child와 parent 모두 40000000이 나온것으로 보아 fork를 진행하면 child와 parent에서 모두 process가 진행됨을 알 수 있다. deadlock 상태가 되어 아무것도 출력이 되지 않았다. 코드를 수정해보았다. foo2 함수에서 pthread_mutex_lock 함수를 통해 뮤텍스 잠금을 요청하고 임계영역에 접근을 해야하는데 lock1과 lock2의 순서가 바뀌어서 lock1과 lock2가 얽혀서 dedlock상태가 된것으로 추정되어 그 순서를 바꾸었더니 제대로 출력이되었다. 2022. 11. 13. 이전 1 ··· 17 18 19 20 21 22 다음 728x90
