[알고리즘 공부] 실전 알고리즘 1강-기초 코드 작성 요령 1

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

알고리즘을 잘 풀기 위해서는 배경지식, 문제해결능력, 구현력을 두루 갖추고 있어야한다.

배경지식이란 다양한 알고리즘, 자료구조, 기타 테크닉같은 문제를 해결하기 위한 지식을 의미한다.

문제해결능력이란 배경지식을 문제에 맞게 잘 변형해서 적용시키는 능력을 의미한다.

구현력이란 본인이 생각한 풀이를 코드로 잘 옮겨낼 수 있는 능력을 의미한다.
따라서 구현력을 올리기 위해서는 문제를 많이 풀어야며, 꼭 다른 사람의 코드를 보면서 더 효율적으로 코드를 작성하는 법을 흡수해야한다.

시간 제한

컴퓨터는 1초에 3억~5억개의 연산을 할 수 있다.
즉 시간 제한이 1초라면 코드가 1초안에 3억~5억번의 연산을 해야 한다는것을 의미한다.

시간 복잡도를 계산할때는 앞의 정수를 제외하고 말한다. 즉 코드 A의 시간복잡도가 2n+5라고 가정할때 앞의 2를 빼고 코드 A의 시간복잡도는 O(n)이며 n에 비례한다고 말한다.

최선의 경우에는 첫번째로 물어본 사람이 가나다씨인 경우로 이경우에는 1초가 걸린다.
최악의 경우에는 마지막으로 물어본 사람이 가나다씨인 경우로 이 경우에는 N초가 걸린다.
따라서 평균적으로는 N/2가 걸리고 시간복잡도는 O(N)이 된다.

이 방식은 사람이 이름순으로 정렬되어 있어서 맨 처음에 정렬된 이름의 중앙에 있는 사람에게 이름이 가나다씨인지 물어보게 된다. 물어본 사람의 이름이 가나다씨보다 앞에 있는 이름이라면 중앙에서 오른쪽으로 가서 다시 위에서부터 반복을하고 물어본 사람의 이름이 가나다씨보다 뒤에 있는 사람이라면 중앙에서 왼쪽으로 가서 다시 위에서부터 반복을 하면 된다.

최선의 경우에는 첫번째로 물어본 사람이 가나다씨인 경우로 이 경우에는 1초가 걸린다.
최악의 경우에는 마지막으로 물어본 사람이 가나다씨인 경우로 이 경우에는 logN초가 걸린다.
따라서 평균적으로는 logN이 걸리고 시간복잡도는 O(logN)이 된다.

시간복잡도(Time Complexity)는 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계를 의미한다.

빅오표기법(Big-O Notation)은 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법이다.

O(N!) > O(2^N) > O(N^2) > O(NlogN) > O(N) > O(logN) > O(1)

N의 크기에 따른 허용 시간복잡도는 대략적으로 이렇게된다.

이렇게 입력 값에 따라 내가 짠 알고리즘이 통과될 수 있는지 생각을 해야한다.

N이 10만 이하의 자연수라는 조건이 있다. 따라서 O(NlogN)보다 시간복잡도가 작은 알고리즘을 구현해야한다.

#include <bits/stdc++.h>
using namespace std;

int func1(int N)
{
	int res = 0;
	// 시간복잡도 O(N)
	for (int i = 1; i <= N; i++)
	{
		if (i % 3 == 0 || i % 5 == 0)
			res += i;
	}
	return res;
}
int main()
{
	//N이 10만 이하의 자연수 -> 
	//O(NlogN)까지의 시간복잡도만 가능
	int N;
	cin >> N;
	
	printf("%d\n", func1(N));

}

N이 1000 이하의 자연수라는 조건이 있다. 따라서 O(N^2logN)보다 시간복잡도가 작은 알고리즘을 구현해야한다.

#include <bits/stdc++.h>
using namespace std;

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;
}
int main()
{
	//N이 1000 이하의 자연수 -> 
	//O(N^2logN)까지의 시간복잡도만 가능
	int arr[101];
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	cout << func2(arr, N) << endl;
}

i는 1부터 시작하며 i의 제곱이 N과 일치하는 확인하는 방식으로 시간복잡도는 O(logN)이다.

#include <bits/stdc++.h>
using namespace std;

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

int main()
{
	//N이 10억 이하의 자연수 -> 
	//O(N)까지의 시간복잡도만 가능
	int N;
	cin >> N;
	
	printf("%d\n", func3(N));

}

N = 2^i이면 i는 logN이므로 시간복잡도는 O(logN)이다.

#include <bits/stdc++.h>
using namespace std;

int func4(int N)
{
	int res = 1;
	for (int i = 2; i <= N; i *= 2)
	{
		res *= 2;
	}
	return res;
}
int main()
{
	//N이 1024 이하의 자연수 -> 
	//O(N^2logN)까지의 시간복잡도만 가능
	int N;
	cin >> N;
	
	printf("%d\n", func4(N));
}

공간복잡도(Space Complexity)는 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계를 의미한다.

코딩테스트에서는 공간복잡도보다 시간복잡도가 중요해서 대부분 신경쓰지않지만
512MB = 1.2억개의 int형을 선언할 수 있다는 것을 기억하면 좋다.

정수 자료형

char형은 1byte(8bit)이다.
unsigned char형의 범위는 0부터 255까지이며 char형의 범위는 -128부터 127까지이다.

short (2byte) = 2^15 - 1
int (4byte) = 2^31 - 1
long long (8byte) = 2^63 - 1

Integer Overflow는 정수형의 값을 초과할 시 양수는 반대쪽 음수로 음수는 반대쪽 양수로 값이 넘어가는것을 의미한다. 즉 값이 일직선에 있는게 아니라 동그라미 형태로 되어 있다고 생각하면 이해하기가 쉽다.

실수 자료형

float (4byte)
double (8byte)

실수 자료형은 sign, exponent, fraction으로 구성된다
sign은 음수, 양수인지 정해주는 필드고 exponent 지수를 저장하는 필드고 fraction은 유효숫자를 저장하는 필드이다.

실수의 성질

1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.
   float는 유효숫자 6자리까지 안전하고 double은 유효숫자 15자리까지 안전하다.

2. double에 long long 범위의 정수를 함부로 담으면 안된다.
   double보다 long long의 크기가 크므로 오차가 섞인 값이 저장될 수 있다.

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