반응형

전체 글 429

[이산수학] 함수의 증가, big o notation

함수의 증가 함수 f(x)가 g(x)보다 더 빠르게 증가한다면, f(x)는 충분히 큰 x에 대해 항상 g(x)보다 커집니다. 사용자 데이터를 처리하는 웹 사이트를 설계한다고 가정해봅시다. 데이터 베이스 처리를 위해서 프로그램 A는 n개 레코드를 처리하기 위해 fa(n) = 30n+8 microseconds가 걸립니다. 프로그램 B는 n개 레코드를 처리하기 위해 fa(n) = n^2+1 microseconds가 걸립니다. Big - o notation 함수의 order에 대한 big o notation에 대해서 설명하겠습니다. f와 g를 정수의 집합 또는 실수의 집합에서 실수의 집합으로의 함수라고 하자. 만약 x > k 일 때, 다음을 만족하는 상수 c와 k가 존재한다면 f(x)는 o(g(X)) 라고 한다..

[이산수학] 알고리즘 선형탐색 이진탐색 정렬 알고리즘

알고리즘 컴퓨터 프로그래밍의 기초/ 기반입니다. 알고리즘은 input, output, definiteness(명확성), correctness(정확성), finiteness(유한성), effectivenesS(효율성), generality(일반성) 등이 있습니다. 결정성은 각 단계의 중간 결과는 유일하고 그리고 입력과 이전 단계의 결과에 의해서만 결정됩니다. 의사코드 (3개의 수 중 최대의 수 찾기) Algorithm to find the largest of three numbers a, b, c Input : a, b, c Output : large(the largest of a, b, and c) procedure max3(a, b, c:integers) { large := a if (b > large..

[이산수학] 수열, 문자열 ,점화관계를 푸는 법 ( 반복 )

수열이란? 일정한 규칙에 따라 한 줄로 배열된 수의 열. a₁, a₂, a₃,…, aₙ의 꼴로 배열한 것으로, {aₙ}로 나타냄. 문자열(String) 이란? 문자열의 유한 sequence입니다. 그런데 항상 순서있는 유한 sequence입니다. 이것을 우리가 string이라고 합니다. 집합 X를 공집합이 아닌 집합이라고 하고 집합 X 상에서의 String은 유한 수열입니다. 집합 X가 {a, b, c} 로 이루어져 있을 때 a = bbaccc 이랗게 표현된 수열이라면 연속적으로 중복된 문자들은 지수승으로 인해서 표현을 할 수 있습니다. b^2 * a* c^3으로 표현할 수 있습니다. |a| 은 길이를 나타냅니다. |a|의 개수를 의미하며 bbaccc로 총 6개의 문자가 나열되어 있기 때문에 길이는 6이..

[따배시 C++ 8.6] 소멸자 destructor

소멸자란? 소멸자는 return 타입이 없습니다. 그리고 파라미터 또한 없습니다. #include using namespace std; class IntArray { private: int* m_arr = nullptr; int m_length = 0; public: IntArray(const int length_int) { m_length = length_int; m_arr = new int[m_length]; } ~IntArray() { if (m_arr != nullptr) delete[] m_arr; delete[] m_arr; } int size() { return m_length; } } int main() { while (true) { IntArray my_int_arr(10000); del..

[이산수학] 멱집합, 순서가 있는 n쌍, 데카르트 곱

집합은 근본적으로 원소들의 순서가 중요하지 않습니다. {a, b, c} 가 순서가 바뀌어도 별 상관이 없습니다. 또한 집합에서 모든 원소는 서로 다르다라는 것이 중요합니다. 집합 내 원소들이 중복이 발생하면 그 중복은 의미가 없습니다. 원소 a와 원소 b가 같다면 {a, b, c} = {a, c} = { b, c } = { a, a, b, a, b, c, c, c, c } 전부 다 같습니다. 모든 원소는 같은 하나의 원소로 생각하기 때문입니다. N = 자연수의 집합 Z = 정수의 집합 Z+ = 양의 정수의 집합 R = 실수의 집합 R+ = 양의 실수의 집합 C = 복소수의 집합 Q = 유리수의 집합 실수에서 구간, 즉 범위를 나타내는 표기법이 있습니다. -[a, b] = {x | a

[이산수학] 유일성 증명, 가설의 형식화, 증명, 반례

n이 정수이면 n^2 >= n 임을 증명하라 경우에 의한 증명 n = 0, n >= 1 , n = 0 이 성립 - n >=1 일때, 양변을 n으로 곱하면 n^2 >= n 이 성립 - n = 0 이므로 n^2 >= n 이 성립\ 따라서 세 경우 모두에 대해 성립하므로 증명하였다. 유일성 증명 -유일하게 하나의 값만이 주어진 특성을 만족하는 경우를 유일성이라고 하고 이에 대한 증명을 유일성 증명이라고 합니다. 유일성 증명 과정 존재성 : x가 주어진 특성을 가짐을 보인다. 유일성 : 만일 y != x 이면 y는 주어진 특성을 가지지 않음을 보인다. 즉 하나의 원소만이 주어진 특성을 갖는지 보이면 됩니다. 예시 a와 b는 실수이고 a != 0 이라면, ar + b = 0을 만족하는 유일한 실수 r이 존재함을 ..

반응형