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

이 게시글은 바킹독님의 강의를 공부하고 개인적으로 정리한 글입니다.

blog.encrypted.gg/922?category=773649

[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

blog.encrypted.gg/923?category=773649

[실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II

 

0x01강 - 기초 코드 작성 요령 |

1. 시간, 공간복잡도

알고리즘 문제를 풀 때에는 시간제한과 메모리 제한이 주어집니다.

 

• 시간제한이 1초라고 주어졌을 때, 컴퓨터는 1초에 대략 3~5억 개 정도의 연산을 처리할 수 있고 이는 연산이 비트, 비교, 덧셈 연산과 같은 단순 연산인지, 아니면 나눗셈, 곱셈, 대입, 함수 호출과 같은 복잡한 연산인지에 따라 차이가 날 수 있습니다.
• 시간복잡도란 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미합니다. 빅오표기법은 시간 복잡도를 표현하는 방법으로 주어진 식을 값이 가장 큰 대표 항만 남겨서 나타내는 방법입니다.

 

• 대표적인 시간복잡도를 그래프로 나타낸 것입니다. 상수 시간인 O(1)이 가장 좋고, O(logN)은 로그 시간, O(N)은 선형 시간으로 부릅니다. O(logN)부터 O(N²)과 같이 logN 혹은 N의 거듭제곱끼리의 곱으로 시간복잡도가 나타내어지면 이를 다항 시간이라고 합니다. 팩토리얼의 경우 지수 시간과 마찬가지로 N이 굉장히 작지 않은 이상 시간제한을 통과하기 어렵습니다.

• 문제에서 주어지는 시간제한은 대부분 1초에서 5초 사이 정도입니다. 표가 절대적이진 않지만 입력(N)의 범위를 보고 문제에서 요구하는 시간복잡도가 최대 어느 정도인지 알 수 있습니다. 다시 말해 주어진 문제를 무턱대고 생각나는 풀이로 푸는 것이 아닌 그 풀이가 제한 시간 내로 통과할 수 있는지 확인 후 문제를 풀어야 합니다.
• 같은 문제를 다른 시간복잡도를 가지는 풀이로 풀 수 있습니다.

 

int 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)	return 1;
	return 0;
}

 

• 해당 문제는 위와 같은 알고리즘으로 작성하면 O(N²)의 시간복잡도로 문제를 풀 수 있지만 

int func2(int arr[], int N)
{
	int tmp[101] = {};

	for (int i = 0; i < N; i++)
	{
		if (tmp[100 - arr[i]] == 1) return 1;
		//if (tmp[100 - arr[i]]) return 1; 도 동일
		tmp[arr[i]] = 1;
	}

	return 0;
}

• 위와 같은 알고리즘으로 문제를 푼다면 O(N)만에 문제를 풀 수 있습니다.
• 다음은 메모리 제한과 관련된 공간복잡도입니다. 공간복잡도란 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계를 의미합니다. 예를 들어 N짜리 2차원 배열이 필요하다면 공간복잡도는 O(N²)이 되고 배열이 필요 없다면 O(1)이 됩니다. 
• 코딩 테스트에서는 공간복잡도의 문제에서 문제를 틀리는 일이 많이 없어 크게 신경을 쓰지는 않아도 되지만, 메모리 제한이 512MB일 때 int 변수를 대략 1.2억 개 정도 선언할 수 있다는 정도는 기억해 놓는 것이 좋습니다. 이때 떠올린 풀이가 5억 인 배열을 필요로 한다면 주어진 메모리 제한을 만족하지 못한 틀린 풀이라는 것을 알 수 있습니다.

 

2. 정수 자료형

• unsigned char로 표현할 수 있는 수의 최솟값은 0, 최댓값은 255입니다.
• char로 표현할 수 있는 수의 최솟값은 -128, 최댓값은 127입니다.
• short, int, long long 자료형은 각각 2 byte, 4 byte, 8byte이며 각각 표현할 수 있는 수의 최댓값은 각각 32767, 대략 2.1 ×109(21억), 9.2 ×1018입니다. (int 자료형이 표현할 수 있는 범위를 넘어서는 수를 저장해야 할 경우 반드시 long long자료형을 사용해야 합니다.)

Integer Overflow

int main(void)
{
	int a = 2000000000 + 2;
	cout << a;
}
/***result***
-294967296
*************/

• 각 자료형의 범위에 맞지 않는 값을 연산을 시켰을 때 위와 같이 컴퓨터가 이진수 계산을 하여 나타낸 결과인 integer overflow가 나타납니다. 이를 막는 방법은 각 자료형의 범위에 맞는 값을 가지게끔 연산을 시키면 됩니다.

 

3. 실수 자료형

• float, double 자료형은 각각 4 byte, 8byte입니다. 
• 컴퓨터는 실수를 IEEE -754 format의 형식으로 저장합니다.
• 실수의 저장/연산 과정에서 반드시 오차가 발생할 수밖에 없습니다. float와 double 각 자료형은 각각 유효숫자가 6자리, 15자리인데 이 말은 곧 상대오차가 각각 10^-6, 10^-15까지 안전하다는 것을 의미합니다. 이를 통해 알 수 있듯 두 자료형의 차이가 크기 때문에 실수 자료형이 필요하다면 float대신 double을 써야 합니다.
• double에 long long 범위의 정수를 함부로 담으면 안 됩니다. double은 유효숫자가 15자리인데 long long은 최대 19자리이기 때문에 double에 long long범위의 정수를 담을 경우 오차가 섞인 값이 저장될 수 있습니다.
• 실수를 비교할 때는 등호를 사용하면 안 됩니다. 대표적인 예로 0.1 + 0.1 + 0.1과 0.3이 같지 않다고 하는 것을 확인할 수 있습니다. 만약 오차 때문에 두 실수가 같은지 알고 싶을 때는 두 수의 차이가 대략 10^-12이하면 동일하다고 처리를 하는 것이 안전합니다.
• 추가적으로 1e-12(=10^-12), 1e9(=1000000000)와 같이 10의 거듭제곱을 표현할 수 있습니다. 

 

0x02강 - 기초 코드 작성 요령 ||

1. STL과 함수 인자

참조자

void swap3(int& a, int& b){
	int tmp = a;
    a = b;
    b = tmp;
}

• 위 코드와 같이 전달된 인자를 참조자(reference)로 받으면 포인터와 비슷하게 a, b의 원본의 값을 변경할 수 있습니다.

 

STL(Standard Template Library) - vector

• 배열과 비슷한 기능을 수행하는 vector STL은 일종의 가변 배열로 #include<vector>를 통해 사용할 수 있습니다.
• vector<int> v(100);와 같이 선언이 가능하고 일반적인 배열을 사용하듯이 인덱스에 접근하여 값을 바꿀 수 있습니다.

void func1(vector<int> v)
{
	v[10] = 7;
}
int main(void)
{
	vector<int> v(100);
	func1(v);
	cout << v[10];
}

• 위 코드와 같이 STL을 함수 인자로 넘길 때 출력은 0이 됩니다. STL도 구조체와 마찬가지로 복사본을 만들어 인자를 보내기 때문에 함수에서 값을 바꿔도 원본 STL에 영향을 주지 않습니다.

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

• 위 함수의 매개변수 vector의 크기가 N이라고 할 때 함수의 시간복잡도는 O(N)이 됩니다.  v1, v2이 인자로 넘겨질 때 이것들의 복사본이 만들어지므로 N개의 원소를 하나하나 복사합니다.

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

• 위와 같은 상황을 피하기 위해 참조자를 사용하였습니다. v1, v2의 type을 참조자로 만들어 참조 대상의 주소 정보만 전달합니다. 위 함수의 시간복잡도는 O(1)입니다. 

 

2. 표준 입출력

• 공백을 포함한 문자열을 입력받을 때는getline() 함수를 사용합니다. type이 C++ string이어야 하는 것을 주의합니다.

string s;
getline(cin, s);
cout << s;

 

• cin, cout을 사용할 때 입출력으로 인한 시간 초과를 막기 위해 아래의 코드를 추가합니다. 단 아래와 같은 코드를 추가하였을 때는 cout과 printf를 섞어 쓸 수 없습니다. 온라인 저지 사이트에서는 출력 글자만 확인하여 채점하기 때문에 cin.tie(0);를 사용하여 cout버퍼를 비우는 시간을 절약합니다. 

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

• endl은 사용하지 않습니다. 줄 바꿈이 필요하면 "\n"을 출력합니다.