All Posts

동적 메모리 할당 정적으로 메모리를 할당하면 간편하고, 메모리 누수와 같은 부분을 신경쓰지 않아도 된다는 장점이 있지만, 할당된 메모리 크기가 말 그대로 정적이라 조절이 불가능해서 메모리가 추가로 필요할 때 대응이 어렵다. 따라서 동적으로 메모리를 할당하여 프로그램이 동작하는 중에 할당 메모리의 크기를 조절하는 방식이 필요하다.C 에서는 malloc, calloc, realloc 을 이용하여 동적 메모리 할당을 하였고, C++ 에서도 cstdlib 를 include 하여 사용할 수 있지만, 다른 방법으로도 동적 메모리 할당이 가능하다.참고로 정적 할당된 메모리는 스택 메모리를 사용하고, 동적 할당된 메모리는 힙 메모리를 사용한다. 또 추가로 C99 에서 표준으로 도입되었던 VLA(variable leng..

크라메르 공식 (Cramer's Rule) 행렬식을 이용하여 연립일차방정식의 해를 구하는 방법에 관련된 공식이다.연립일차방정식이 다음과 같다 가정하자.$$ \begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n} x_n = b_2 \\ \qquad \qquad \qquad \quad \vdots \\ a_{n1} x_1 + a_{n2} x_2 + \cdots + a_{nn} x_n = b_n \end{cases} $$이를 $ AX = B $ 로 나타내면 $ A $ 와 $ B $ 와 $ X $ 는 아래와 같다.$ A = \begin{bmatrix} a_{11} & a..

여인수 (Cofactor) $ n $ 차 정사각행렬 $ A = \left[ a_{ij} \right] $ 의 $ i $ 행과 $ j $ 열을 제거하여 만든 부분행렬을 $ M_{ij} $, 소행렬(minor matrix)이라 하고, $ | M_{ij} | $ 를 $ a_{ij} $ 의 소행렬식(minor determinant)이라 하며, $ A_{ij} = (-1)^{i+j} |M_{ij}| $ 를 $ a_{ij} $ 의 여인수라 한다.다음 행렬 $ A $ 를 가정하자.$$ A = \begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{bmatrix} $$행렬 $ A $ 를 통해 ..

원형 큐  선형 큐는 구현하였을 때 전열과 후열이 큐를 사용하면서 지속적으로 증가하기 때문에 전열과 후열이 배열의 끝에 도달한다면 배열의 앞 부분이 비어있더라도 사용하지 못하는 단점이 있다. 이를 보완하기 위해 모든 요소를 왼쪽으로 이동시킬 필요가 있는데, 실제 데이터를 이동시키기 위해서는 추가 연산도 필요하고, 구현도 복잡해지기 때문에 다른 방법이 필요하다.이러한 단점을 극복한 것이 원형 큐이다. 원형 큐는 배열을 선형이 아니라 원형으로, 즉 전열과 후열을 연결하여 배열의 끝에 도달하더라도 지속적으로 큐를 사용할 수 있게 하는 것이다. 실제로 배열을 원형으로 만드는 것은 아니고 후열이 배열의 끝에 도달하면 다시 전열을 사용하도록 하여 개념적으로 원형을 만들어 사용한다.큐를 어떻게 구현할 것인가가 다를 ..

큐  큐는 선입선출(FIFO, first in first out) 방식으로 동작하는 자료구조이다. 즉 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다는 뜻이다. 일상에서 흔히 볼 수 있는 줄 서기 상황이 이와 유사하다. 줄을 먼저 선 사람이 먼저 빠져나가는 방식에서 큐의 작동원리를 생각해 볼 수 있다.즉 데이터 추가는 후열(rear)에서만 일어나고 데이터 삭제는 전열(front)에서만 일어난다. 데이터를 처리할 때 순서를 보장하는 성질이 있는 것이다. 때문에 공정하게 데이터를 처리하는 대기열, 프로세스 스케줄링 등에 사용된다. ADT 객체 (Object)0 개 이상의 요소들로 구성된 선형 리스트연산 (Operation)create(size) ::= 최대 크기가 size 인 공백 큐를 생성한다.init() ..

알고리즘 (Algorithms) 알고리즘은 어떤 문제를 해결하기 위한 단계별 방법이며, 다음의 특성을 가진다.입력 (Input) : 알고리즘은 입력을 받는다.출력 (Output) : 알고리즘은 출력을 생성한다.정밀성 (Precision) : 각 단계가 명확하게 기술되어 있다.결정성 (Determinism) : 실행 과정에서 각 단계의 결과는 유일하며, 입력과 이전 단계의 결과에 의해 결정된다.유한성 (Finiteness) : 알고리즘은 유한한 수의 명령어가 실행된 후 종료된다.정확성 (Correctness) : 알고리즘이 생성한 출력은 문제를 정확하게 해결한다.일반성 (Generality) : 알고리즘은 일련의 입력에 대해 적용된다. 의사코드 (Pseudo-code) 영어를 그대로 읽어서 슈도코드라고도 ..

이항 관계 (Binary Relation) 어떤 집합에서 다른 집합으로의 관계(relation)는 첫 번째 집합의 요소들이 두 번째 집합의 어떤 요소들과 관련되어 있는지로 확인할 수 있다. 예를 들어 자연수의 영역에서 정의된 항등함수를 생각하면, $ \{(1, 1), (2, 2), \cdots, (n, n) \} $ 으로 나타낼 수 있을 것이다.즉 집합 $ X $ 에서 집합 $ Y $ 로의 관계(여기서는 두 집합의 관계이므로 이항관계) $ R $ 은 $ X \times Y $ 의 부분집합이다. 만약 $ (x, y) \in R $ 이면, $ x \text{ } R \text{ } y $ 라 쓰고 $ x $ 가 $ y $ 와 관계있다고 말한다. 이 후 관계라 하면 이항 관계를 말한다.이때 관계 $ R $ 의..

순열 (Permutation) 자연수의 집합 $ S = \{ 1, 2, \cdots, n \} $ $ (n \geq 2) $ 에서 $ S $ 로의 전단사 함수 $ \sigma $ 를 순열 혹은 치환이라 하며 다음과 같이 나타낸다.$$ \sigma =  \begin{pmatrix} 1 & 2 & \cdots & k & \cdots & n \\ i_1 & i_2 & \cdots & i_k & \cdots & i_n \end{pmatrix} $$또한 이를 다음과 같이 나타낸다.$$ \begin{pmatrix} i_1 & i_2 & \cdots & i_n \end{pmatrix} $$즉 다음과 같다.$$ \sigma(1) = i_1, \cdots , \sigma(k) = i_k , \cdots , \sigma(..

푸아송분포 (Poisson Distribution) 어떤 시공간 혹은 명시된 영역에서 사건이 평균적으로 $ \lambda $ 번 발생할 때, 사건이 발생할 횟수를 확률변수 $ X $ 라 하면, 확률변수 $ X $ 가 푸아송분포를 따른다고 한다. 포아송이라고도 한다.$$  X \sim Po(\lambda) $$확률변수 $ X $ 가 평균적으로 벌어지는 사건 횟수가 $ \lambda $ 인 푸아송분포를 따를 때 위와 같이 나타낸다. 이때 각 구간에서 벌어지는 사건이 독립적이고, 일정해야 하며, 가능한 희소한 사건이어야 푸아송분포로 확인하는 것이 의미가 있다. 만약 독립적이지 않고, 일정하지 않다면 푸아송분포를 사용하지 못하며, 희소한 사건이 아니라면 푸아송분포를 사용하는 의미가 퇴색된다.특징을 생각해본다면 ..

이산균등분표 (Discrete Uniform Distribution) 유한하고 공집합이 아닌 수들의 집합 $ C $ 에서 하나의 원소를 선택할 확률이 동일할 때, 선택 값을 확률변수 $ X $ 라 하면, 확률변수 $ X $ 가 이산균등분포를 따른다고 한다.$$ X \sim \text{DUnif}(n) $$확률변수 $ X $ 가 $ 1 $ 에서 $ n $ 까지의 자연수 하나를 선택하는 이산균등분포를 따를 때 위와 같이 나타낸다. 주로 $ 1 $ 에서 $ n $ 까지 나타내기 때문에 위와 같이 나타내는 것이지, 범위가 $ a $ 에서 $ b $ 까지라면, $ X \sim \text{DUnif}(a, b) $ 와 같이 나타내기도 한다. 이산균등분포의 성질 $ X \sim \text{DUnif}(n) $ 일 때..