백투더코딩

ios_base::sync_with_stdio(false);

c++ 컴파일러는 c와 c++ 입출력을 다 허용하는데, 이를 위해 동기화 되어있다.

위 코드는 C 표준 스트림과 C ++ 표준 스트림 간의 동기화를 비활성화

iostream과 stdio 버퍼를 모두 사용하지 않고 C++만의 독립적인 버퍼 사용

사용하는 버퍼 수 감소 -> 실행 속도 향상

cin.tie(NULL);

cin과 cout은 버퍼를 공유(tie)하고 있다.

cin에 cout이 묶여 있으면 프로그램이 사용자에게 입력을 요청하기 전에 버퍼를 확인하고 플러시과정 거침

위 코드는 cin에 cout을 untie

플러쉬 과정 사라짐 - > 실행 속도 향상

참고 사이트

https://jaimemin.tistory.com/1521

https://leeeegun.tistory.com/4

브루트 포스(Brute Force) / 완전탐색

brute: 짐승 force:힘

->무식하게 풀기, 모든 경우의 수를 다 계산해보기

->시간면에서 매우 비효율적

->하지만 그만큼 만들기 단순함

주의할 점) 모든 경우의 수를 다 계산해보기 때문에 문제의 데이터값 범위를 잘 확인하여

범위를 넘지않는지 잘 확인해야 함.

소수: 1과 자기자신(n)만을 약수로 가지는 수

방법 1) 2~n-1까지 모든 수를 다 나눠보며 나눠 떨어지지 않으면 소수다.

방법 2) 메모제이션 이전까지의 모든 소수로 나눠 떨어지지 않으면 그 수는 소수다.

방법 3) 제곱근 2~루트n 사이의 수를 다 나눠보며 나눠 떨어지지 않으면 소수다.

방법 4) 에라토스테네스의 체  n^1/2 이하의 수의 배수를 다 지운후 남아있는 수가 소수다.

참고사이트

https://velog.io/@hyeon930/%EC%86%8C%EC%88%98%EB%A5%BC-%EA%B5%AC%ED%95%98%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://coding-factory.tistory.com/367

https://danidani-de.tistory.com/50

구글링을 하다가 우연히 endl을 통해 개행을 할 경우 출력과 함께 버퍼를 지워 속도가 

더 느리다는 게시글을 봤다.

endl 대신 C언어에서 사용했듯이 '\n'을 통해 개행을 진행하면 실행 속도를 향상 시킬 수 있다.

참고사이트 

https://jaimemin.tistory.com/1521

최대공약수: 공통된 약수 중 가장 큰 수

유클리드 호제법 이용

R이 0이 될 때까지

A % B = R

A = B

B = R 

반복하고 마지막 A가 최대 공약수가 된다.

최소공배수: 공배수 중에서 가장 작은 수

A*B/최대공약수 이용  (최소공배수 * 최대공약수 = A * B이기 때문에)

=>A*B/gcd(A, B)

참고 사이트

https://twpower.github.io/69-how-to-get-gcd-and-lcm

mod 연산을 사용하여 나머지 연산을 구한다.

a mod b : a를 b로 나눈 나머지

• (A + B) % M = ((A%M) + (B%M)) % M
• (A X B) % M = ((A%M) X (B%M)) % M
• (A - B) % M = ((A % M) - (B % M) + M) % M

뺄셈 연산의 경우만 mod 연산을 수행한 값이 음수가 나올 수 있으므로 굵은 글씨 부분을 추가해야 한다.

ex) -5 mod 3 은 값이 1이 나와야 한다. (-2+3=1)

참고사이트

https://velog.io/@gidskql6671/%EB%82%98%EB%A8%B8%EC%A7%80Modulo-%EC%97%B0%EC%82%B0-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99

https://codingram.tistory.com/26

https://teus.me/736