[알고리즘 기초] 시간, 공간복잡도와 알고리즘에 대한 기초 설명

[실전 알고리즘] 0x01강 - 시간복잡도와 기초 코드 작성 요령

혼자 공부하는 알고리즘.

 

대략적인 설명과 간단한 내용이 대부분이니 자세한 내용은 위의 블로그에서 봐주세요.

아래의 내용은 위 블로그의 내용을 요약한 것입니다.

 

---

시간, 공간복잡도

코딩 테스트에서 PS와 CP가 명시되어 있지 않다면,
보통 명시되어있지 않으면 시간 제한은 1-5초, 메모리 제한은 128-512MB 정도라고 생각하면 된다.

 

시간복잡도

시간복잡도란?
-> 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계이다.

점근표기법 예시

문제를 해결하는데 걸리는 시간이 N에 비례한다, 혹은 lg N에 비례한다라고 하는 것을 점근표기법으로 나타낼 수 있다.

 

공간복잡도

공간복잡도란?
-> 입력의 크기와 문제를 해결하는데 걸리는 공간의 상관관계

공간복잡도보다는 시간복잡도를 해결하는 데 집중하자.

단지 공간복잡도라는 개념보다 512MB에 int변수가 대략 1.2억개 정도 들어갈 수 있다는 개념으로 접근하자.

 

** 문제에서 주어진 input의 범위를 보고 어느 정도의 시간복잡도까지 통과될 수 있는 지 잘 파악하기

 

 

 

 

---

표준 입출력

 

대부분 코딩테스트에서는 C++을 많이 사용한다.

표준 입출력 같은 경우 scanf/printf를 사용해도 된다.

하지만 cin/cout는 C++ String 자료형을 처리할 수 있기 때문에 cin/cout를 사용하도록 한다.

 

 

공백이 포함된 한 줄의 문자열을 받고 싶다면

int main(void){
	stirng s;
    getline(cin,s);
    cout << s << '\n';
    const char* t = s.c_str(); //char*로 문자열을 다루고 싶다면
    printf("%s",t);
    
    }

C++ stream에서는 getline(cin, S)라는 명령 하나로 처리가 가능하기 때문에 공백이 포함된 한 줄의 문자열은 마음 편하게 C++ stream에서 입력받는 것을 추천

그리고 char*로 굳이 변환을 하고 싶으면 이전에 설명한 것과 같이 c_str() 메소드를 사용

 

 

cin/cout 를 사용할 때 반드시 실행할 명령어

(입출력 시간초과 방지)

int main(void){

	ios::sync_with_stdio(0);
	cin.tie(0);
    
    }

** ios::sync_with_stdio(0)  - 해당 명령어 실행 후, cout만 사용해야 함

** cin.tie(0)  -  cin과 cout이 번갈아 나올 때마다 flush하지 않도록 하는 명령

                -  endl 대신 \n 사용

 

 

 

---

기초 지식 

정수 자료형의 범위

구분		크기(Byte)	범위
정수형	char	1	-128  ~ 127
	short	2	-32,768 ~ 32,767
	int	4	-2,147,483,648 ~ 2,147,483,647
	long	4	-2,147,483,648 ~ 2,147,483,647
	long long	8	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

* 정수를 표현할 때 주로 int와 long long을 사용하는데, int가 long long보다 연산 속도와 메모리 모두 우수하지만

80번째 피보나치 수를 구하는 문제와 같이 int 자료형이 표현할 수 있는 범위를 넘어서는 수를 저장해야 하면 반드시 long long 자료형을 사용

 

 

Integer overflow

자료형의 범위를 벗어날 때 생겨남

컴퓨터는 명령받은 대로 이진수 상의 계산을 했을 뿐, 그 결과가 옳지 않은 것.

이럴 때는 자료형을 바꿔주거나 for문의 범위를 변경한다.

 

 

 

실수 자료형의 범위

구분		크기(Byte)	범위
실수형	float	4	3.4*10^-37 ~ 3.4*10^38
	double	8	1.7*10^-307 ~ 1.7*10^308
	long double	8 이상

 

 

 sign field는 해당 수가 음수인지 양수인지 저장하는 필드이고, exponent 필드는 과학적 표기법에서의 지수승을 저장하는 필드이고, fraction 필드는 유효숫자 부분을 저장하는 필드입니다.

 

double이 float보다 메모리를 2배 더 차지하지만 더 정확하므로 모든 실수 관련 문제에 double을 쓰면 됩니다.

 

실수의 성질

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

float은 대략 상대 오차 10^-6까지 안전하고, double은 10^-15까지 안전
만약 문제에 절대/상대 오차를 허용한다는 단서가 있으면 실수 연산을 해도 되지만 그렇지 않다면 모든 연산을 정수에서 해결할 수 있도록 해야합니다. 그렇지 않을 경우 오차로 인해 오답이 발생할 수 있습니다.


2. double에 long long 범위의 정수를 함부로 담으면 안된다.

int 범위의 정수는 double에 담아도 되지만 long long 범위의 정수를 담으면 오차가 발생합니다.

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

둘의 차이가 극도로 작은 값, 대략 10^-12 이하면 동일하다고 처리를 하는 것이 안전합니다.

 

 

전역변수와 지역변수

코딩테스트에서는 전역변수를 사용하여 더 빠르게 코딩하는 것이 효율적(전역변수는 0으로 초기화 가능)

 

Header 사용

bits/stdc++.h : Pre-compiled header의 일종으로, 사람들이 많이 사용하는 표준 라이브러리 헤더들을 모두 한 번에 Compile될 수 있도록 해 둔 것

이 헤더에 대해서는 장/단점이 명확하니 공부하면서 익힐 것