Brute force Study

문제 접근만약 Bruete Force한 접근 방식으로 모든 경우를 다 구한다고 하면 O(n!)로 주어진 시간 내에 해결이 불가능하다.어떻게 접근해야 할 지 잘 모르겠지만 분명 매 케이스마다 나머지를 하고 있으면 매우 많은 연산 시간이 필요하다는 것 정도는 알 수 있다. (문자열의 최대 길이가 50이기 때문에 특정 상태에서 나머지를 구할 때 해당 문자열 처음부터 끝까지 나머지를 계산하는 것 또한 매우 비효율적이다.) 따라서 먼저, 각 문자열의 수를 k로 나눈 나머지를 미리 기록해두자int cachestr[16];// 주어진 문자열과 제수(divisor)를 입력받아 나머지를 반환해주는 함수int mod(const string &s, const int divisor) { int result = 0; ..

Gaussian Elimination(가우스 소거법)많이 사용되는 기본적인 파트이므로 꼼꼼히 보자.사다리꼴 (Echelon Forms)이전 챕터 예제에서 x, y, z의 solution을 구할 때 위와 같은 형태로 만들어 구했던 것을 기억할 것이다. 이러한 형태를 가지기 위해서는 다음 4가지 성질을 만족해야 한다.만약 행이 모두 0이 아닌 경우, 그 행에서 첫 번째로 0이 아닌 수는 1이어야 합니다. 이를 선도 1 (leading 1)이라고 부릅니다.모든 요소가 0인 행이 있으면, 그것들은 행렬의 맨 밑으로 내려가야 한다.모두 0이 아닌 두 연속된 행에서, 하위 행의 선도 1(leading 1)은 상위 행의 선도 1보다 오른쪽에 있어야 한다.선도 1이 포함된 각 열은 그 열의 다른 모든 요소가 0이어야 ..

Systems of Linear Equations and Matrices선형 방정식과 행렬 체계에 대해 배운다Linear Equation(선형 방정식)선형 방정식은 2차원에서는 직선으로, 3차원에서는 평면으로 나타난다.b = 0인 경우 homogeneous linear equation(동차 선형 방정식)이라고 부른다.예시선형 방정식은 변수의 곱이나 루트를 포함하지 않는다. 모든 변수는 1차 형태로만 나타난다.위와 같은 방정식은 선형 방정식이 아니다.Linear System(선형 시스템, 선형 계)유한 개의 선형 방정식으로 이루어진 집합을 system of linear equation, 줄여서 linear system이라고 한다. 변수들은 미지수(unknowns)라고 불린다.미지수 x1, x2, … x..