:: ADVANCE ::

[수학][GCD LCM] 최대공약수와 최소공배수 최대공약수 (GCD, Greatest Common Measure) 두 자연수의 경우 약수를 구해보면 공통된 약수를 가지고 있다.이 중 가장 큰 약수를 최대공약수라 한다.최대공약수를 구하는 가장 단순한 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 방법이 있다. 123456int g = 1;for(int i = 2; i

[수학][mod] % 나머지 연산자 나머지 연산% 또는 mod(모드) 연산자 라고 한다. 나머지 연산자는 나눗셈 연산 후 나머지를 구하는데 사용한다.나머지 연산의 특성상 결과값은 0 ~ (자신 - 1) 의 값이 나온다. 나머지 연산자의 분배 법칙을 보자.각각 나머지 연산을 취한 후 다시 전체적으로 나머지 연산을 한다. 일단, 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 한다.) 뺄셈의 경우, 음수가 나올 수 있기 때문에 M을 더해준 후 다시 전체의 나머지 연산을 해주어야 한다. 이는 C 언어의 % 연산자에서 음수 처리는 다음과 같이 정의되어 있기 때문이다. X % Y를 연산할 때 그 연산 결과의 부호는 X의 부호를 따라간다.Y의 부호는 무시되며, 오직 X가 양수이면 결과도 ..

[Greedy] Greedy Algorithm (그리디, 탐욕 알고리즘) 정의 : 미리 정한 기준에 따라서 매번 가장 좋은 답, 최선의 답을 선택하는 알고리즘 최적화 문제를 푸는 데 사용한다.단계 단계 별로 가장 최적인 해를 구한다.효율적이긴 하나 반드시 전체의 최적의 해를 구해준다는 보장은 없다. 1. 해 선택 (Selection Procedure) : 지금 가장 최적인 해를 구하여 부분해 집합에 추가한다.2. 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.3. 해 검사 (Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 그렇지 않을 경우 1번부터 반복한다. 탐욕 알고리즘의 대표적인 예로, 최소의 동전 수로 거스름돈 주기 문..