Crtl + F

1. 오답노트

백준

• 팩토리얼0의개수
• 프린터큐
• 스택수열
• 소수구하기
  • 어디까지 탐색할것인지 -> 루트 int 변환시 +1
  • 1은 소수가 아니다
• ISBN
  • 체크섬인 m은 가중치와 무관
  • m이 *인경우도 고려해야함

2. 개념정리

2-1. 소수: 에라토스테네스의 체

• 소수가 아닌 수(합성수)는 어떤 소수의 배수임
• 1부터 까지의 숫자 중에서 소수를 찾고 싶다면, 소수의 배수들을 순차적으로 제거하고 남는 숫자들을 확인
• 시간 복잡도
  • $O(n \log \log n)$
• 장점
  • 하나하나 나누어보며 소수인지 확인하는 방식보다 훨씬 빠릅니다. 특히 특정 범위 내의 소수를 한꺼번에 구할 때 유리
• 단점
  • 숫자의 범위가 커질수록 메모리(숫자들을 저장할 공간)를 많이 차지

예시수행 단계 (1부터 30까지의 예시)

• 초기화
  • 2부터 30까지의 숫자를 나열하기
  • 1은 소수가 아니므로 제외
• 2 선택
  • 아직 지워지지 않은 가장 작은 수인 2 를 소수로 선택
  • 2의 배수를 모두 지우기. (4, 6, 8, …)
• 3 선택
  • 다음으로 지워지지 않은 수인 3 을 소수로 선택
  • 3의 배수를 모두 지우기. (6, 9, 12, …)
• 반복
  • 이 과정을 반복
  • 다음 숫자인 4는 이미 지워졌으니 건너뛰고, 5를 선택해 그 배수를 지우기…
• 종료
  • 구하려는 범위의 제곱근까지만 반복하면 남은 모든 수는 소수임!

실전에서

• 제곱근까지만 확인
  • 0 숫자 까지의 소수를 구할 때, $\sqrt{n}$까지만 배수를 지우면 충분
  • 예를 들어 100까지의 소수를 구할 때 10의 배수까지만 지우면 나머지는 자동으로 결정
• 이미 지워진 수는 패스
  • 이미 배수로 판명되어 지워진 숫자는 다시 검사할 필요가 없음

2-2. DP 활용하는 팩토리얼

적어두고, 그거랑 곱하기 for문으로만 가능

이진탐색

C++ Round