1. Euclidean algorithm (유클리드 호제법)
- GCD(a,b) = GCD(b,r) : r은 a를 b로 나눈 나머지
2. GCD, LCD
- a b = GCD(a,b) LCD(a,b)
3. Prime number
- 임의의 수 N이 소수인지 판단하려면 root(N)보다 작거나 같은 모든 수에 대해 나누어지는지 판단
- 혹은 소수는 6m+1, 6m+5의 꼴 안에 존재한다는 것을 응용해도 됨
4. Sieve of Eratosthenes (에라토스테네스의 체)
- 효율적으로 특정 영역에서의 소수들을 기록하여 저장하는 방법
- 단순한 메모의 컨셉
5. Goldbach's conjecture (골드바흐의 추측)
- 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능
- 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능
- 아직 증명이 되지 않은 문제이나 컴퓨터의 연산 능력을 이용해서 특정 영역(10^18 이하)에서 참인 것을 보이는 문제들이 출제되곤 함
6. N!를 소인수 분해 할 시 특정 소수 p의 차수
- 가우스 함수(N/p) + 가우스 함수(N/(p^2)) + 가우스 함수(N/(p^3)) + etc
- 1의 자리수로 부터 연속된 0의 개수를 구하는 경우 소인수 분해시 2와 5의 차수중 낮은 값이 해당 됨 (10 = 2 * 5 이므로)
- 보통 2보다는 5의 개수가 적으므로 5의 차수만으로 판단하면 보다 효육적임
7. 나눗셈
- c++의 경우 나누기의 나머지의 절대값이 나누는 값의 절대값보다 작으면 되고 부호는 상관이없게 나옴
e.g) -5 = (2) * (-2) -1로 -5를 -2로 나누면 나머지가 -1로 나옴 - 파이썬의 경우 나머지가 0보다 크거나 같다를 만족하여 나옴
e.g) -5 = (3) * (-2) +1로 -5를 -2로 나누면 나머지가 +1로 나옴
8. 소인수분해
- 소수들을 일일히 구하지 않고도 주어진 값을 계속 나누어가면서 해당 값보다 작은 애들로 최대한 나누어 질때까지 나누는 것을 반복하면 됨
9. dynamic programming
-
overlapping subproblem
큰 문제와 작은 문제를 같은 방법으로 풀 수 있으며 (e.g. N의 값이 큰 경우와 작은 경우)
큰 문제를 작은 문제들로 쪼갤 수 있는 경우 -
optimal substructure
큰 문제의 정답을 쪼개진 작은 문제들의 정답(optimal solution)으로 부터 구해지는 경우
-
위의 두 조건들을 잘 보고 판단하여 문제들을 해결하려고 한다면 DP문제들은 비교적 쉽게 해결되는 경우가 많음
-
memoization을 잘 활용하고 (반복해서 중복되는 작은 문제들을 매 번 해결하지 않기 위해) TOP-DOWN(재귀)으로 풀 것인지 BOTTOM-UP(반복문)으로 풀 것인지 잘 판단해야 함
-
TOP-DOWN : 문제를 큰 문제에서 해당하는 작은 문제들로 계속 분할 후 해결
-
BOTTOM-UP : 문제들을 작은 문제부터 쭉 해결하고 풀고자하는 큰 문제에 도달했을 때 멈추고 해당 solution을 반환
10. 문제 견적 내기
- 시간 복잡도가 1억 즉 이면 대충 1초라고 계산하면 됨
- N이 500일 경우 이 1초를 넘김
11. brute force
- 다음의 3단계를 통해 문제를 풀 수 있는지 견적 내기
1) 문제의 크기 계산 (시간 복잡도)
2) 가능한 모든 경우를 계산
3) 그 중 문제의 조건에 맞는 정답 고르기 - 푸는 방법 크게 3가지
1) 재귀
2) 순열
3) 비트마스크
12. 합동식 문제 - 중국인의 나머지 정리
- 추후 정리 할 것
13. 순열
- 사전순으로 나열시 다음 순열을 찾는 방법
1) A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾습니다.
2) j>=i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾습니다.
3) A[i-1]과 A[j]를 값을 서로 바꾸어 줍니다.
4) A[i]부터 순열을 뒤집습니다.
즉 오름차순이 어긋나는 마지막 지점을 기준으로 뒤에서 부터 오름차순으로 계속 바꾸어 주어 사전순으로 나열된 순열을 찾아갑니다. - 특정 값의 집합에서 조합을 구할 때 고르는 개수의 1과 나머지 0들로 index를 순열로 나열하여 해당 index를 고르는 방향으로 응용이 가능합니다.
예시문제 : https://www.acmicpc.net/problem/6603
14. 백트래킹(backtracking)
- 가능한 모든 경우의 수를 조사할 경우 주어진 조건에 만족이 되지 않음에도 고려함으로써 과한 연산을 할 경우가 생깁니다.
- 따라서 이러한 경우를 방지하기 위하여 주어진 조건을 만족시키는 경우의 수들만 조사하여 모든 경우의 수를 조사하는 방법이 백트래킹 방법입니다.
- 시간복잡도를 정확히 나타낼 수 없는 경우도 존재하지만 대체적으로 백트래킹을 하게되면 경우의 수가 대폭 감소하게 됩니다.
15. 비트마스크(bitmask)
- ans(&), or(|), not(~), xor(^), shift(<<, >>)를 이용하여 집합 연산을 정수를 통해 가능합니다.
- 집합 S에 대하여
i를 추가 : S | (1 << i)
i를 검사 : S & (1 << i)
i를 제거 : S & ~(1 << i)
i를 토글 : S ^ (1 << i) - 문제에 따라서 사용시 매우 도움이 되기도 하지만 굳이 사용하지 않아도 될 경우가 더 많은 것 같긴 합니다.
Reference
han811