record logo record

Algorithm

C++로 알고리즘 시작하기

update: 08 June 2020

알고리즘 시작하기

  1. 알고리즘 종류, 자료구조 종류
  2. 시간 복잡도, 공간 복잡도, 자료형
  3. C++ STL, 표준 입출력

알고리즘 종류

자료구조 종류

시간, 공간복잡도

시간복잡도(Time Complexity)

빅오표기법(Big-O Notaion)

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

O(1) < O(lgN) < O(N) < O(NlgN) < O(N^2) < O(2^N) < O(N!)

N의 크기
허용 시간복잡도
N <= 11 O(N!)
N <= 25 O(2^N)
N <= 100 O(N^4)
N <= 500 O(N^3)
N <= 3,000 O(N^2lgN)
N <= 5,000 O(N^2)
N <= 1,000,000 O(NlgN)
N <= 10,000,000 O(N)
그 이상 O(lgN), O(1) 
// 1. O(log(n))
while(n)
	n/=2;

// 2. O(sqrt(n))
for(int i=0;i*i<=n;i++);

// 3. O(n)
for(int i=0;i<n;i++);

// 4. O(nlog(n))
for(int i=0;i<n;i++)
	for(int j=i;j;j/=2);

// 5. O(nsqrt(n))
for(int i=0;i<n;i++)
	for(int j=0;j*j<=i;j++);

// 6. O(n^2)
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++);

// 7. O(n^3)
for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
		for(int k=0;k<n;k++);

// 8. O(2^n)
int function(int n){
	if(n==0||n==1)
		return 1;
	return function(n-1)+function(n-2);
}

// 9. O(n!)
// n개의 데이터를 나열하는 방법의 수
void function(int x, vector<int> pick, vector<bool> picked){
	if(x==n){
		for(int i=0;i<pick.size();i++)
			printf("%d\n", pick[i]);
		return;
	}
	for(int i=0;i<n;i++){
		if(picked[i])
			continue;
		pick.push_back(i);
		picked[i]=true;
		function(x+1, pick, picked);
		pick.pop_back();
		picked[i]=false;
	}
	return;
}

공간복잡도

정수, 실수 자료형

정수 자료형

실수 자료형

연습 코드

#include <iostream>

using namespace std;

// O(n)
int func1(int num) {
	int sum = 0;
	for(int i = 1; i <= num; i++) {
		if(i % 3 == 0 || i % 5 == 0) {
			sum += i;
		}
	}
	return sum;
}
// O(N^2)
int func2(int *arr, int num) {
	int sum = 0;
	for(int i = 0; i < num; i++) {
		for(int j = i+1; j < num; j++) {
			if(arr[i] + arr[j] == 100) return 1;
		}
	}
	return 0; 
}
// O(n^1/2)
int func3(int N) {
	for(int i = 1; i*i <= N; i++) {
		if(i*i == N) return 1;
	}
	return 0;
}
// O(lgN)
int func4(int N) {
/* my sol */  
//	int max = 0;
//	for(int i = 1; i*i <= N; i*=2) {
//		if(i*i > max) { // 1 2 4
//			max = i*i;
//		}
//	}
//	return max;

	int val = 1;
	while(2*val <= N) val *= 2;
	return val;
}

int main(void) {

//	cout << func1(16) << endl;
//	cout << func1(34567) << endl;
//	cout << func1(27639) << endl;
	
//	int arr[3] = {1, 52, 48};
//	cout << func2(arr, 3) << endl;
//	int arr2[2] = {50, 42};
//	cout << func2(arr2, 2) << endl;
//	int arr3[4] = {4, 13, 63, 87};
//	cout << func2(arr3, 4) << endl;
	
//	cout << func3(9) << endl;
//	cout << func3(693953651) << endl;
//	cout << func3(756580036) << endl;
	
	cout << func4(5) << endl;
	cout << func4(97615282) << endl;
	cout << func4(1024) << endl;
	
	
	return 0;
}



C++, 알아두면 좋은 팁 모음

STL과 함수 인자

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

표준 입출력

// 1. scanf의 옵션: \n(줄바꿈)이 나올때까지 입력받기
char a1[10];
scanf("%[]^\n", a1);
// 2. gets 함수: 보안상 이슈로 c++14 이상에서는 제거됨
char a2[10];
gets(a2);
puts(a2);
// 3. getline 함수: 타입이 c++ string 여야한다.
string s; 
getline(cin, s);
cout << s;

// 이걸 안해두면 입/출력 양이 많을 때 시간초과가 날 수 있다.
ios::sync_with_stdio(0), cin.tie(0)

보통 printf와 scanf등에서 쓰는 C stream과 cin/cout 등에서 쓰는 C++ stream은 분리가 되어있다.

printf와 cout을 번걸아하면 사용하는 상황을 생각해보자

cout << "11111\n";
printf("22222\n")
cout << "33333\n";

사용자 입장에서는 C stream와 C++ stream 분리 되어있음은 상관없이 원하는 대로 출력이 된다. 이렇게 코드의 흐름과 실제 출력이 동일하기 위해서 기본적으로 프로그램에서는 C stream와 C++ stream를 동기화 시키고 있다. 만약 내가 C++ stream 만을 사용할 것이라면 굳이 2개의 Stream을 동기화 할 필요가 없다. 쓸때 없이 시간만 잡아먹으니까… 그렇기 때문에 C++ stream 만 쓸꺼면 동기화를 끊어버려서 프로그램 수행 시간에서 이득을 챙길 수 있고 명령어는 아래이다.

cin.tie(0) 는 버퍼의 개념을 이해해야한다. cin 명령을 수행하기 전에 cout 버퍼를 비우지 않도록 하는 코드이다.

endl 쓰지마라!!!!!

endl은 개행문자(\ㅜ)를 출력하고 출력 버퍼를 비워라는 명령이다.

References