알고리즘을 위한 간략 정리/수학 (4) 썸네일형 리스트형 [C++] 소수 판정(에라토스테네스의 체) 숫자들 중 소수인 것들을 어떻게 구분할 수 있을까? 0. 충분히 큰 수를 최댓값으로 설정한다. 1. int형 배열을 하나 만든 뒤, 각 값들을 각 인덱스로 초기화한다. 2. 소수인 2부터 시작해서 배수들을 모두 0으로 초기화한다. ※이때, 소수들은 초기화해선 안되므로 bool형 변수를 활용한다. 3. 배열에 0이 아닌 숫자들이 들어있는 숫자들은 모두 소수이다! #include #define MAX 1000000 using namespace std; int num[MAX]; int main(){ for(int i = 2; i [C++] 수학 함수 제곱(pow) 함수 원형 double pow(double base, double n) // base가 되는 숫자의 n 제곱 새로운 수학 함수를 사용할 때마다 차근차근 정리할 예정입니다. 비트마스킹(Bitmasking) 비트마스킹 데이터 타입마다 각 메모리 사용 크기가 있다. 만약 int 라고 하면 4byte 즉, 32 bit의 크기를 가진다. 표현하면 0000 0000 0000 0000 0000 0000 0000 0000이 될 것이다. (0과 1을 씀) 만약 아이템이 있고 없고를 구현해야할 때 bool 변수 32개를 쓰는 대신에 하나의 비트를 다룰 수 있을경우, 우리는 int 자료형 하나로 32개의 아이템이 있고 없고를 표현할 수 있다. 또한 비트 연산은 연산 속도가 빠르다는 장점을 가지고 있다. 만약 2번째 아이템이 있다면 0100 이런식으로 0을 1로 바꾸어 표현하는 것이다. &, |, ~, ^, >>, n - shift 연산자 오른쪽 혹은 왼쪽으로 n비트 만큼 이동 후 뒤에는 0으로 채움 공집합 만들기 int s.. DP(Dynamic Programming) 핵심요약 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 간단한 구현, 복잡한 점화식 최적의 원리가 성립해야함. 최적의 원리 "어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.” 문제 풀이 순서 문제 탐색 DP 배열에 어떤 값을 저장할 것이고, 인덱스는 어떤 것을 의미할지 정의를 한다. dp 벡터를 선언할 때 최소값을 찾을경우 MAX로, 최대값을 찾을경우 MIN으로 선언한다. DP식(점화식) 세우기 메모이제이션된 부분 문제들의 해를 이용하여 차례로 더 큰 상위 문제의 답을 어떻게 구할지를 고민한다. 검증 및 구현(시간 복잡도) 문제 유형 결과값들 더하기. 결과값들 중 최대, 최소 구하기. 배낭 채우기(.. 이전 1 다음