[실전 압축 알고리즘] - 시간, 공간 복잡도

본 게시글은 실전 기술을 정리해 놓은 '실전 압축' 입니다. 

C++ 기준으로 작성하였습니다.

---

시간 복잡도

 

작동하는 알고리즘의 수행시간을 정량화하는 것을 의미합니다. 


시간 복잡도를 표기하기 위한 방법에 빅-오, 빅-오메가, 세타 등이 있으며 

일반적으로 최악의 케이스(Worst Case)를 가정하고 계산 하므로 빅-오 표기법을 

빅오 표기법은 최고차항의 차수만을 표기합니다. 


N^3 + N^2 + N + 1 = O(N^3)

 

---

숫자 빨리 읽기

 

0을 3개씩 묶어서 숫자 단위를 빠르게 파악하도록 암기합니다.

숫자	읽기
1'000	천
1'000'000	백만
1'000'000'000	10억

배열을 만들 때 arr[10000000] 보다는 arr[10'000'000] 이런식으로    
작은 따옴표를 넣어서 가독성을 높이고 실수를 줄이도록 합니다.  
  
혹은 1e7로도 표현이 가능합니다. (대신 double형 입니다.)

 

---

시간 예측

 

컴퓨터는 1초에 대략 1-3억개의 연산을 수행할 수 있습니다.  

문제의 입력 데이터의 범위를 보고 대략적으로 시간이 얼마나 걸릴지 유추할 수 있어야 합니다.

제한 시간이 1초일 때 대략 이 정도의 입력 범위에서 
이 정도 효율의 알고리즘은 사용할 수 있고 없고를 판단할 수 있어야 합니다.

빅 오	N	1억 + a 정도의 시간이면 1초에 가능
O(N)	약 1억	1억
O(N*logN)	약 1000만	log(1000만) = 7.1 x 1000만 = 7100만
O(N^2)	약 10000	10000 x 10000   = 100,000,000
O(N^3)	약 500	500 x 500 x 500 = 125,000,000

이는 대략적인 수치이며 로직의 복잡성에 따라 예상보다 적을 수도 클 수도 있습니다.

 

 

---

공간 복잡도

 

l  정수 자료형  

자료형	크기	범위	쉽게 외우기
char	1byte	-128~127	2^7-1
short int	2byte	-32,768~32,767	3만
int	4byte	-2,147,483,648~ 2,147,483,647	21억
long long int	8byte	9.2 * 10^18 = 9,223,372,036,854,775,807	18 ~ 19자리 수 정도

 

입력, 계산 과정, 계산 결과 모두 21억이 넘는지 반드시 고려해야 합니다.

 

l  실수 자료형

자료형	크기	범위	쉽게 외우기
float	4byte	3.4e +/- 38 (7 digits)	상대오차는 10^-7 정도
double	8byte	1.7e +/- 308 (15 digits)	상대오차는 10^-15 정도

지수 표기법

e + a	a만큼 오른쪽으로 소수점 이동
e - a	a만큼 왼쪽으로 소수점 이동

3.4e+3이라면 3.4 * 1000 = 3400
  

정밀도를 위해 float보다는 double을 사용해야 합니다.

float는 그냥 사용할 일이 많은 없다고 생각하면 됩니다. 
괜히 썼다가 정밀도에서 문제 생기는 경우가 많아집니다.

 

---

숫자가 너무 커요

 

C++

 

만약 unsigned long long 을 벗어나는 너무 큰 숫자를 처리해야 하는 문제가 나온다면 
(Big Integer 문제)

string, char배열 혹은 구조체를 활용해야 됩니다.
구현에는 여러가지 방법이 있는데

1) 앞에서 부터 0 추가하여 자리수 맞추기

 

A와 B의 자릿수가 맞지 않을 때 앞에 0을 넣어서 맞춰줘서 계산합니다.

2) 뒤집어서 계산하는 경우 

 

아예 배열을 뒤집어 버려서 더한 뒤 다시 뒤집어 주는 방법이 있습니다.
올림 수를 그냥 다음 인덱스에 바로 더해버리면 되는 편리성이 있습니다.
이 때 rbegin, rend, reverse 를 사용하면 깔끔하게 작성이 됩니다.


혹은 굉장히 큰 숫자에 모듈러 연산을 한 결과를 구하는 문제도 있는데
중간 연산의 결과에 모듈러를 해도 결과는 같으므로

중간 중간에 모듈러를 하여
자료형의 크기를 벗어나지 않도록 하는 방법들이 있습니다.

 

 

 

Python

 

그저 갓이라는 생각 밖에 들지 않는다.

표현할 수 있는 수의 제한이 없다.

그러니까 엄~청나게 큰 숫자를 다룰 땐 귀찮게 C++로 풀지말고 Python으로 풉시다 !

 

 

 

큰수 A+B
https://www.acmicpc.net/problem/10757

10757번: 큰 수 A+B

큰 수 문제들

https://www.acmicpc.net/problem/tag/%ED%81%B0%20%EC%88%98

큰 수 - 1 페이지

 

 

내용은 계속해서 추가됩니다...