[ 알고리즘 ] OT, 기초 코드 작성 요령

1)  시간 복잡도

 

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

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

ex. O(N) : 5N+3 , 2N+2

연습문제

/*
문제1
N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라.
N은 10만 이하의 자연수이다.
*/

void func1(int N) {
	int sum = 0;
	for (int i = 1; i < (N + 1); i++) {
		if (i % 5 == 0 || i % 3 == 0) {
			sum += i;
		}
	}
	cout << sum;
}

// 시간복잡도 O(N)

 

/*
문제2
주어진 길이 N의 int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 존재하지 않으면 0을 반환하는 함수 func2(int arr[],intN)을 작성하라.
arr의 각 수는 0이상 100이하이고 N은 1000이하이다. 
*/

void func2(int arr[], int N) {

	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (arr[i] + arr[j] == 100) {
				cout << 1;
				return;
			}
		}
	}
	cout << 0;

}

//시간복잡도 = (n-1)+(n-2)+...+3+2+1 = N(N-1)/2 = O(N^2)

 

/*문제3
N이 제곱수이면 1을 반환하고 제곱수가 아니면 0일 반환하는 함수 func3(int N)을 작성하라. N은 10억 이하의 자연수이다.
*/

void func3(int N) {
	for (int i = 0; i * i <= N; i++) {
		if (i * i == N) {
			cout << 1;
			return;
		}
	}
	cout << 0;

}

//시간복잡도 : O(루트N)

 

//문제4
//N 이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 func4(int N)을 작성하라. N은 10억 이하의 자연수이다.

void func4(int N) {

	int num=2;

	do {
		num *= 2;

	} while (num <= N);

	cout << num/2<<endl;
}

//시간복잡도 : O(로그N)

 

2)  공간복잡도

공간복잡도 : 입력의 크기와 문제를 해결하는데 필요한 공간의 상관간계

512MB = 1.2억개의 int

 

 

3)  정수자료형

char -  1byte =8bit (255)

short - 2byte (32767)

int - 4byte (21억 쯤)

long long - 8byte

 

3)  실수자료형

float - 4byte

double - 8byte

 

*특징

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

float : 10^-6

double : 10^-15

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

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

 

3)  STL과 함수 인자

vector STL -  가변배열

vector<int> v(100);  //int 100칸 배열 선언
v[20]=10;
v[60]=-4;

* 함수 인자로 사용하면 복사해서 전달됨!! 

bool cmp1(vector<int> v1,vector<int> v2,int idx){
	return v1[idx]>v2[idx];
}
// 시간 복잡도 O(N) -> 각 인자들을 복사


bool cmp2(vector<int>& v1,vector<int>& v2,int idx){
	return v1[idx]>v2[idx];
}
// 시간 복잡도 O(1)

 

4)  표준 입출력

cin, cout 사용시 주의할점 (시간 지키기 위해)

1. ios::sync_with_stdio(0) :  stream C와 stream C++ 모두 동기화 하면 오래걸림으로 streamC 버림

사용하면 C stream 사용 금지

2. cin.tie(nullptr)

 

*endl : \n + 버퍼비우기 - 사용 권장 X

 

 

5) 코드작성 팁

  코딩테스트와 개발은 완전히 다르다

출력내용 뒤에 공백이나 줄바꿈은 상관없다