Minusi

이번 포스팅에서는 행렬의 곱셈의 구현과 최적화 방법에 대해서만 집중적으로 분석합니다. 행렬에 관한 내용은 행렬 대수 포스팅을 읽어보시거나 다른 레퍼런스를 확인하시면 되겠습니다. 행렬의 곱셈은 왼쪽 행렬의 i번째 행, j번째 열에 있는 요소에 대해 왼쪽 피연산자 행렬의 i번째 행과 오른쪽 피연산자 행렬의 j번째 열을 내적한 값을 산출한다고 행렬 대수에서 언급했습니다. 그림으로 나타내면 다음과 같습니다. 이것을 구현하는 것은 어려운 일이 아닙니다. 빠르게 작성된 행렬 곱셈 연산의 구현은 다음과 같습니다 : #include using namespace std; /* 빠르게 작성된 2x2 행렬을 곱하는 코드 */ int main() { int a[2][2] = { 1,2,3,4 }; int b[2][2] = {..

소수는 1과 자기 자신을 제외하고는 어떠한 수로도 딱 나눠지지 않는 수를 의미합니다. 위키피디아에서는 다음과 같이 설명합니다 : 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1 x 5 또는 5 x 1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2 × 3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수 라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 알고리즘 사이트에서는 소수를 주제로 한 알고리즘 문제가 많이 존재합니다. 이번 포스팅에서는 그 중, 소수를 생성하는 알고리즘에 대해서 알아보도록 하겠습니다. ..

순열 알고리즘, 또는 모든 경우의 수를 계산하는 알고리즘은 개인적으로 직관적으로 생각하는 것만큼 코드로 구현하기는 쉽지 않은 알고리즘이라고 생각합니다. 먼저 순열(Permutation)은 위키피디아에서 다음과 같이 정의하고 있습니다: 수학에서, 순열(Permutation) 또는 치환은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. n개의 원소의 순서를 뒤섞는 순열의 개수는 n의 계승 n!와 같다. 즉, n 이하의 양의 정수들을 곱한 값이다. 위키에서 서술했듯이, 순서 있는 n개에 대한 모든 경우의 수를 구하는 것은 n!로 굉장히 구하기 쉽습니다. 또한, 이것의 모든 경우의 수를 하나하나 나열하라고 한다고 해도, 손이 조금 아플 뿐 어려운 문..

vector 컨테이너는 C++에서 자주 사용되는 컨테이너로 GeeksforGeeks에서는 다음과 같이 정의되어 있습니다 : 벡터는 요소가 삽입되거나 삭제 될 때 자동으로 크기를 조정할 수 있는 동적 배열과 동일하며 컨테이너에서 자동으로 처리합니다. 벡터 요소는 반복자를 사용하여 액세스하고 통과 할 수 있도록 인접한 저장소에 저장됩니다. 벡터에서는 데이터가 끝에 삽입됩니다. 때때로 배열을 확장 할 필요가있을 수 있기 때문에 마지막에 삽입할 때 시간이 달라질 수 있습니다(differential time). 마지막 요소를 제거하면 크기 조정(resizing)이 발생하지 않으므로 상수 시간이 소요됩니다(또는 상수 시간 복잡도를 가집니다). 시작 또는 중간에 삽입하거나 및 제거하는 것은 선형 시간(linear i..