알고리즘 개념 및 Tool C++

[C++] 에라토스테네스의 체 , 소수판별을 위한 도구

에라토스테네스의 체는 소수판별을 하기 위한 간단하고도 강력한 방법입니다. 1,0과 영은 소수가 아니므로 2부터 판별을 시작합니다. 소수의 정의는 약수가 자기 자신과 1만을 가진 숫자입니다. 그러므로 2는 소수입니다. 하지만 2의 배수는 2를 약수로 갖기 시작하므로 소수의 조건에서 벗어나게 됩니다. 이러한 점을 이용해 빠르게 소수가 아닌 수를 false로 저장하는 방법입니다. int m[1001]; // 에라토스테네스의 체 배열 크기 지정 //2~999까지 소수판별을 하는 코드입니다. void eratos() { for(int i=2;i

[C++] permutation을 이용한 조합과 순열 활용

완전탐색에 많이 이용되는 조합과 순열을 알아보려고 합니다. !! C++ 의 algorithm 헤더파일에 있는 next_permutation prev_permutation 을 이용해서 출력하고 활용하는 방법까지 알아보려고 합니다. 먼저 기본적인 순열 출력인 next_permutation 함수를 사용해볼게요. 순열로 출력할 원소들은 오름차순으로 정렬되어있어야 합니다 ! vector v{1,2,3,4}; -> OK vector v{1,3,10,4}; -> NO C++의 sort함수를 활용하면 permutation을 사용할때 좋겠죠? (tip: C++ sort 함수는 퀵소트 방식으로 구현되어 있어요~) vector v{1,2,3}; do{ for(auto it = v.begin();it != v.end();it..