Study/Algorithm
-
📣 #12 수학Study/Algorithm 2022. 3. 6. 15:35
2021.10.14에 작성한 글 BaaaaaaaarKingDog 실전 알고리즘 💡 소수 1과 자기 자신으로만 나눠지는 수 = 약수가 2개인 수 반대개념 : 합성수 📌 소수 판정법 소수의 정의 이용 👉2부터 N-1까지의 수로 나누어지지 않는 수이다. 시간 복잡도는 O(N) bool isprime(int n) { if (n == 1 ) return 0; //1은 소수X for (int i= 2; i < n; i++) { if (n % i == 0) return 0; } return 1; } 2. 합성수 N에서 1을 제외한 가장 작은 약수는 √N이하이다. 👉 2부터 √N까지의 수로 나누어지지 않으면 소수이다. 시간복잡도는 O(√n) bool isprime(int n) { if (n == 1 ) return 0..
-
📣 #3 배열 (선형자료구조)Study/Algorithm 2022. 3. 6. 15:29
2021.02.25에 작성한 글 BaaaaaaaarKingDog 실전 알고리즘 👉 정의와 성질(자료구조로서의 배열) O(1)에 k번째 원소 확인/변경, 끝자리에 추가/삭제 가능 추가 소모 메모리 양이 적고, cache hit rate 높음 메모리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림 배열은 전역에 선언 -> 0으로 초기화 지역변수는 쓰레기값으로 됨 👉 기능과 구현 임의의 위치에 원소를 제거/추가 -> O(N) memset 함수 (C string 헤더) fill 함수 (알고리즘 헤더) 👉 STL vector vector 배열명( , , , , ) 배열명.push_back() : 추가, insert 기능 배열명.pop_back() : 삭제, erase 기능 배열 사이즈는 unsigned int를..
-
📣 #2 기초코드 작성 요령Study/Algorithm 2022. 3. 6. 15:28
2021.02.25에 작성한 글 BaaaaaaaarKingDog 실전 알고리즘 👉 STL과 함수인자 참조자 : 함수인자 조심. int 배열은 복사가 아니라 주소를 가져옴. STL - vector : 가변배열, STL을 쌩으로 함수인자에 보내면 복사본이 된다. vector & v1 : 시간복잡도를 줄여준다.(참조자) 👉 표준입출력 공백포함 문자열 -> getline사용 cin사용X 단, c++ string만 가능 sync_with_stdio(0) c++ stream 쓸 때 동기화 끊는 명령 cin.tie(0) 굳이 count 버퍼 안 지우도록 하는 명령. 버퍼 지우면 시간걸림 endl 사용 X , 그대신 \n사용 하기
-
📣 #1 기초 코드 작성 요령Study/Algorithm 2021. 2. 26. 00:28
BaaaaaaaarKingDog 실전 알고리즘 👉 시간 복잡도 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 빅오표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 O(N) = 2N+10logN O(N²) = N²+2N+3 O(1) = 5, 16, 35 👉 공간 복잡도 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 512MB = 1.2억개의 int int = 4byte 👉 정수 자료형 char(1 byte) = 8 bit 8개의 칸 중 맨 앞 1칸은 -2^7의 칸. integer overflow 주의 127+1 = -128 short(2 byte) : 32767 (표현할 수 있는 수의 최댓값) int(4 byte) : 21억 비슷(2,147,483,647) 10의 10제..