1. N의 크기에 따른 시간 복잡도
| <N의 크기> | <허용 시간복잡도> |
|---|---|
N ≤ 11 | O(N!) |
N ≤ 25 | O(2^N) |
N ≤ 100 | O(N^4) |
N ≤ 500 | O(N^3) |
N ≤ 3000 | O(N^2logN) |
N ≤ 5000 | O(N^2) |
N ≤ 백만 | O(NlogN) |
N ≤ 천만 | O(N) |
그 이상 | O(logN), O(1) |
풀이를 생각했다면 그 풀이의 시간복잡도를 먼저 분석해야 한다.
공간복잡도는 신경을 안써도 되지만 512mb = 1.2억개의 int 라는 것만 기억하자.
즉, 요소개수가 5억개인 배열이 필요하다면? 당연히 안된다.
2. 정수 자료형
int는 최대 21억
long long은 최대 920경
3. 실수 자료형
실수를 2진수로
3 = 2^1 + 2^0 = 11(이진수)
3.75 = 2 + 1 + 0.5 + 0.25 = 11.11(이진수)
실수의 정규화
11101.001(이진수) = 1.1101001 X 2^4
실수의 저장 방식
float의 저장
예시) -6.75 = 1.1011 X 2^2(이진수)
| 구성 | 데이터 | 비고 |
|---|---|---|
| sign(1비트) | 1 | 음수일땐 1, 양수일땐 0 |
| exponent(8비트) | 10000001 | 지수인 2에 127을 더한 값, 음수도 넣기위해 127을 더한 것 |
| fraction(23비트) | 1011000000...00 | 정수부분은 제외하고 소수부분만 왼쪽부터 채움 |
| 총 32비트 | 1.1011 X 2^2 | / |
실수의 저장 / 연산 과정에서 반드시 오차가 발생
float: 유효숫자 6자리 => 10의 -6승까지 안전
double: 유효숫자 15자리 => 10의 -15승까지 안전
안전하다는 의미
소수부분을 10의 -15승까지만 표현한다고 할 때, double은 1 - 10^(-15)승에서 1 + 10^(-15)승까지의 실수 값을 가진다는 의미이다.
실수자료형을 쓸 때는 double만 쓰자
double에 long long범위의 정수를 함부로 담으면 안된다.
둘 다 64비트 자료형인데, long long은 정수를 표현하는데 모든 비트를 다 쓰지만, double은 64비트를 fraction과 exponent로 나눠서 표현하다보니 표현하는 범위가 다르다.
실수를 비교할 때는 등호를 사용하면 안된다.
double a = 0.1 + 0.1 + 0.1;
double b = 0.3;
if(a == b) cout << "same1\n";
if(abs(a-b) < 1e-12) cout << "same2\n";둘의 차이가 대략 10의 -12승보다 작다면 동일하다고 취급해야함.
4. STL과 함수 인자
STL을 함수 인자로 넘길 때
C언어의 배열처럼 원본을 넘기지 않고 C언어의 구조체처럼 복사본을 만들어 넘긴다.
따라서 파라미터가 STL을 복사할 때 비용이 들어간다.
그래서 원본을 넘기고 싶다면 &연산자로 reference를 보내면 된다.
5. 표준 입출력
ios::sync_with_stdio(0)
C언어의 표준 입출력 스트림과 C++ 표준 입출력 스트림과 동기화 되어 있다.
그래서 printf 와 cout를 섞어 써도 순서가 유지된다.
하지만 cout / cin만 쓸꺼면 동기화할 필요가 없어서 동기화를 위한 비용을 제거할 수 있다.
VS에서는 sync_with_stdio(0)를 무시하고 강제 동기화를 하지만 채점 컴파일러에는 적용된다.
cin.tie(0)
기본적으로 cin으로 입력받기 전에 cout에 담겨있는 모든 버퍼를 출력해서 버퍼를 비운다.
그래서 입력라인과 출력라인이 동기화되어서 콘솔에서 볼 때 순서가 유지된다.
입력: 1+1은?
출력: 2
입력: 2+2는?
출력: 4만약 cin으로 입력받기 전에 cout버퍼를 강제 출력하지 않으면 다음과 같은 상황이 발생할 수 있다.
입력: 1+1은?
입력: 2+2는?
출력: 2
출력: 4버퍼를 출력해서 비우는 과정에는 비용이 들어간다.
채점 컴파일러에서는 입력과 출력을 따로 저장한다.
그래서 입력과 출력간의 순서를 유지할 필요가 없다.
따라서 cin을 하기 전에 cout의 버퍼를 비우지 않도록 해서 비용을 줄인다.
해당 코드가 cin.tie(nullptr)이다.
endl
개행 후에 강제로 출력 버퍼를 비우는 코드이다.
중간중간에 버퍼를 비우는것이 코딩테스트에서는 필요가 없다.
개행이 필요하면차라리 \n 를 사용하자.
STL 컨테이너 순회
새로운 for문법으로 순회
vector<int> v = {1, 2, 3, 4};
// 요소 복사
for(int e: v) cout << e << ' ';
// 원본 요소
for(int& e: v) cout << e << ' ';일반 for문으로 순회할 때 주의할 점
size()메서드의 반환 타입은 size_t이다.
이는 음수가 아닌 정수 즉, unsinged 타입을 가진다.
따라서 size() - 1 은 언더플로우가 발생할 여지가 있으므로 이렇게 사용하면 안된다.
// 처음부터 마지막 전 까지 순회할 때
for(int i = 0; i < v.size() - 1; i++) cout << v[i] << ' '; // X
for(int i = 0; i + 1 < v.size(); i++) cout << v[i] << ' '; // OK입출력 스트림
istringstream
cin 처럼 사용
#include <sstream>
#include <string>
#include <vector>
#include <iostream>
std::string line = "10 20 30 40";
std::istringstream iss(line);
std::vector<int> nums;
int x;
while (iss >> x) nums.push_back(x);ostringstream
cout 처럼 사용
마지막에 str()로 문자열 추출
#include <sstream>
#include <string>
#include <iostream>
int score = 95;
std::string name = "ab";
std::ostringstream oss;
oss << "Name: " << name << ", Score: " << score;
std::string result = oss.str();to_string()보다 유연하다.
원시 문자열
문자열을 원본 그대로 저장하는 방식.
\n, \t 등을 그대로 유지한다.
std::string data = R"(Line1
Line2\tTabbed
Line3 "quoted")";