안 쓰던 블로그

[정렬과 이분탐색] 1920 수 찾기 #include #include #include #include using namespace std; vector v; int n; int find(int num) { int s = 0, e = n - 1; while (s > n; for (int i = 0; i > a; v.push_back(a); } //int m; cin >> m; //for (int i = 0; i > a; //auto it = find(v.begin(), v.end(), a); //if (it == v.end()) cout a; cout n; for(int i=0;i> x; a[x]++; //인덱스 증가..

10610 30 #include #include #include #include using namespace std; /* "길거리에서 찾은 수에 포함된 숫자들을 섞어, 30의 배수가 되는 가장 큰 수를 만든다" 처음에 문제를 봤을 때는 주어진 N값을 소인수분해해서 나온 여러 숫자들을 어케 잘 연산해서 30의 배수를 만드는 줄 알았다. 그런데 무한히 더해버리면 무한히 큰 30의 배수를 만들 수 있기 때문에 이건 아니었다 예제를 다시 보니까 "포함된 숫자"라는 의미가 주어진 N의 각각 자리수를 의미하는 것이었다 그리고 각 자리수를 어케 잘 재배치해서 가장 큰 30의 배수를 만들면 된다 30의 배수가 될 조건을 만족하는지 확인하고 각 자리수를 큰 수부터 재배치한다 30의 배수가 될 조건 1. 끝자리가 0 2..

1676 팩토리얼 0의 개수 #include #include #include #include using namespace std; int n, m; /* 2와 5를 곱할 때만 0이 생긴다 5보다 2가 많으니까 5만 세면 된다 근데 5의 배수가 예외 5*2=10 5*5*2*2=100 5*5*5*2^3=1000 2는 충분히 많다고 칠 수 있으므로(소인수분해 하면 2가 잔뜩나온다) 5의 배수는 1개씩 늘 때마다 0의 개수가 1개씩 증가되며 추가된다고 볼 수 있다 5^4=625는 문제 범위인 500을 넘으므로 패스 */ int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; while (n >= 2) { if (n % ..

약수 1: https://www.acmicpc.net/problem/4375 약수: https://www.acmicpc.net/problem/1037 C가 A의 약수라면, A/C도 A의 약수가 되어야 한다 C=3, A=24라면, 24/3=8도 24의 약수가 되어야 한다 그러면 중간을 기준으로 대칭을 이루게 된다 이 아이디어로 전체 약수를 구할 때 더 빠르게 구할 수 있다 전체 약수 구하기 1. 1~A로 모두 나눠보기: O(A)걸림. N개 수에 대해서 연산하므로 N*O(N) = O(N^2) 2. 1~루트(A)로 모두 나눠보기: O(루트(A))걸림. N개 수에 대해서 연산하면 N*O(루트(N))=O(N*루트(N)) 이런 아이디어는 범위가 클 때 사용 가능하다 N

알고리즘에서 나머지 연산은 연산의 값이 너무 커져서 자료형으로 담기 어려울 때, 각 연산마다 나머지 연산을 하여 자료형 안에 담기 위하여 사용한다 덧셈, 곱셈, 뺄셈은 성립하지만 나눗셈의 경우 성립하지 않는다. (나눗셈의 경우는 modular inverse를 구해야 한다) 그리고 주의할 점은 뺄셈의 경우 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 한 번 더하는 과정이 필요하다 $(A-B) mod M = ((A mod M) - (B mod M) + M) mod M$ 그 이유는 무엇일까? M을 더해도 전체 식에 영향은 없는 것인가? 나머지 연산에서 음수가 나오는 예시를 먼저 본다 $(6-5) mod 3 = 1 mod 3 = 1$ 이다 만약 $(6 mod 3-5 mod 3) mod..

크래머의 법칙이란, 미지수의 개수와 방정식의 개수가 같은 연립 1차 방정식의 해를 두 행렬식의 나눗셈으로 구할 수 있다는 것이다 행렬 방정식 $AX=B$ 가 $n$ 개의 미지수의 $n$ 개의 1차 방정식으로 이루어진 연립 1차 방정식이라고 한다면, 만일 $det(A) \neq 0$ 이면 이 연립 방정식은 유일한 해 를 갖는다 여기서 $A_j$ 는 $A$ 의 제 $j$ 열의 원소를 다음 행렬의 원소로 바꾼 행렬을 나타낸다 $$B=\begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}$$ 왜 이렇게 되는지는 직접 계산 해 보면 된다 크래머의 법칙을 이용하여 다음 연립 1차 방정식의 해를 구하는 문제의 풀이는 다음과 같다

수반 행렬을 이용하여 역행렬 구하기 크래머의 법칙을 이용하여 연립 1차 방정식의 해 구하기 마지막 계산은 너무 복잡해서 계산기 돌림; 솔직히 이 문제는 이런 방법보다 그냥 대입해서 풀면 훨씬 쉽게 답이 나왔음 문제에서 그렇게 하라고 해서 그런 거지.. 아래 처럼 풀면 된다