[바킹독의 실전 알고리즘] 0x01강 ~ 0x02강

(5) 바킹독의 실전 알고리즘 강의 - YouTube

바킹독의 실전 알고리즘 강의

위 강의를 보고 학습한 내용을 바탕으로 작성하였습니다.

---

1. 시간복잡도, 공간복잡도

1) 시간 복잡도

- 컴퓨터는 1초에 대략 3~5억개 정도 연산 처리 가능

- 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계

- 빅오 표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법

O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)

O(1)	O(logN)	O(N)	O(NlogN)	O(N^2)	O(2^N)	O(N!)
그 이상		N<=10,000,000 (천만)	N<=1,000,000 (백만)	N<=5000	N<=25	N<=11

2) 공간 복잡도

- 입력의 크기와 문제를 해결하는데 걸리는 공간의 상관관계

- 만약 공간복잡도가 512MB이면 1.2억개의 int 가능

 

✅ 입력 :

100 이하 완전탐색 , 백트래킹(bfs,dfs)

100,000 n^2까지 가능

1,000,000 최대 nlogn

힙, 우선순위 큐, 정렬, dp, 위상정렬, 다익스트라(최단거리)

10,000,000 dp

100,000,000 logn (이진탐색)

 

 

2. 정수 자료형 범위

자료형	범위
unsigned char	0~2^8-1 (255)
char	-2^7 ~ 2^7-1 (-128~127)
short	2^15-1(32,767)
int	-2^31 ~ 2^31-1 (-21억 ~ 21억 사이)
long long	-2^63 ~ 2^63-1

- integer Overflow : 자료형의 범위를 넘어갈 때 발생하는 오류

ex) 반복문에서 char i = 0 ; i<127; i++ 로 할때 127에서 1을 더했을 시 -128이 되어 무한 루프에 빠지게 됨

 

3. 실수 자료형 범위

- 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.

- float는 유효숫자 6자리, double은 유효숫자 15자리 (소수점 6, 15자리수를 벗어나면 오차가 발생)

- double에 long long 범위의 수를 담으면 안됨

- 실수를 비교할 때는 등호를 사용하면 안된다.

* 0.1+0.1 != 0.2 ( 1/10을 이진수로 나타냈을 시 무한소수가 되기때문에 오차가 발생함)

자료형	범위
float	1.175494e-38~3.402823e+38
double	2.225074e-308~1.797693e+308

 

 

4. 함수 인자

- 함수인자로 숫자, 구조체, 벡터는 값이 복사가된다.

- 배열로 인자가 들어왔을 때는 주소값이 들어가기때문에 원본 배열을 바꾼다.

bool cmp1(vector<int> v1, vector<int> v2, int idx){
  return v1[idx] > v2[idx];
}

bool cmp1(vector<int>& v1, vector<int>& v2, int idx){
  return v1[idx] > v2[idx];
}

첫번째 함수는 기존 벡터를 복사해서 값을 비교하기에 시간복잡도가 O(N)

두번째 함수는 주소를 가져와 값을 비교하기 때문에 O(1)이 된다.

 

5. 표준 입출력

1) 공백 포함 입력 받기

[C++] 공백(띄어쓰기)포함 문자열 입력받기 (tistory.com)

[C++] 공백(띄어쓰기)포함 문자열 입력받기

* getline을 쓰는게 좋다

 

2) 입출력에서의 시간 줄이기

ios::sync_with_stdio(false); // c stream과 c++ stream 과의 동기화 끊음, 따라서 섞어쓰면 절대 안됨
    cin.tie(0); // cin 명령을 수행하기 전 cout 버퍼를 비우지 않도록 하는 코드
                // 채점 서버에서는 출력만 확인하기 때문에 입출력 순서를 굳이 지킬 필요 없음

✅ endl 절대 쓰지 말것 ! : endl은 개행문자를 출력하고 출력 버퍼를 비우는 명령어