Python3) 리스트에서 in
으로 검색을 하면 시간 복잡도가 O(n)이 되니, 사용에 유의해주세요.
- 10610 (30)
- 3의 배수의 각 자리 수를 더하면 3의 배수가 되는 점 이용
- 가장 큰 수를 만들기 위해 정렬
- 이미 정렬된 상태에서 0을 확인하기 위해
find
(C++)나 in
키워드(Python3) 사용하여 O(n) 탐색을 할 필요는 없다
- 자리 수를 더하면서 0 확인해도 좋음
- 14490 (백대열)
- 두 수를 최대한으로 약분하려면 최대공약수로 나누면 된다는 것을 이용해야 함. O(n)의 브루트포스로 풀지 않도록 주의.
- 최대공약수 구할 때 유클리드 호제법 활용했는지 확인
- 2436 (공약수)
- 두 수 A, B의 곱은 최대공약수와 최소공배수의 곱이라는 점을 이용해서 브루트포스
- LCM/GCD = a*b 라는거 파악했는지 확인 (a = A/GCD, b = B/GCD)
- 그 후, 두 수의 차이를 최소로 하는 제곱근부터 검사해야 효율적
- 두 수의 합을 최소로 만들기 위해서는 두 수의 차이가 최소여야 한다.
- ex) 1 * 16 = 2 * 8 = 4 *4 = 16, 두 수의 합의 최소는 4 + 4 = 8
- 6588 (골드바흐의 추측)
- 매 테스트케이스마다 소수 배열을 새로 구하면 시간초과로 이어지니, 처음부터 최댓값까지의 소수 배열을 미리 구해 두어야 한다.
- b-a가 가장 큰 것 → 작은 소수부터 탐색해서 n을 만들 수 있으면 바로 종료
- 20302 (민트초코)
- 소인수분해 할 때 에라토스테네스의 체 활용했는지 확인
- 소인수분해 경로 배열을 미리 구해두어 연산을 줄인다.
- 0이 식에 등장하면 무조건 0이므로 유리수 → 따라서 0 곱했을 때 처리 해주어야 함
- 1로 여러번 나누어도 결과에는 영향을 미치지 않음
- 정수의 부호는 중요하지 않다 → 절댓값 이용