[바킹독의 실전 알고리즘] 0x01 ~ 0x02 기초코드 작성 요령 복습 -C++

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여,

필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다.

(이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...)

바킹독의 실전 알고리즘 0x01강 링크

바킹독의 실전 알고리즘 0x02강 링크

 

강의내용 복습

시간복잡도와 공간복잡도

시간 제한과 메모리 제한에 대한 내용.

 

컴퓨터는 1초에 대략 3-5억 개 정도의 연산을 처리할 수 있다.

즉, 문제에서 시간제한이 1초라고 한다면, "당신의 프로그램은 3-5억 번의 연산 안에 답을 내고 종료되어야 한다"는 의미!

 

시간복잡도

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

연산의 수행 횟수는 입력된 개수(n)에 의해 결정되므로 n의 함수로 표시된다.

(not! depends on mechine's spec, only depends on input size!)

T(n) = n² + n + 1 일 때, n이 커지면 +n이나 +1의 영향력은 무시할만 하다! n²만 고려해도 충분!!! 

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

 

[바킹독의 실전 알고리즘] 0x01강 - 기초 코드 작성 요령1

교수님 왈 : 우리에게 중요한 것은, 데이터가 어마어마하게 커졌을 때, 어느것이 더 빠른지이다 !

 

입력의 범위를 보고 문제에서 요구하는 시간복잡도가 어느 정도인지 파악할 수도 있다.

아래 표를 통해 대략적인 느낌만 가져가자.

 

[바킹독의 실전 알고리즘] 0x01강 - 기초 코드 작성 요령1

중요한 것은, 문제를 보고 풀이를 떠올린 후, 내 풀이가 이 문제를 시간 제한 내로 통과 할 수 있는가?

즉, 내 알고리즘의 시간복잡도가 올바른지 꼭 생각해 봐야 한다는 것이다.

 

공간복잡도

입력의 크기와 문제를 해결하는 데 풀요한 공간의 상관관계

512MB = 1.2억개의 int 선언 가능(int 1개가 4 byte 이용)

 

정수 자료형

char 자료형의 1byte = 8bit

-> char 자료형의 값은 8개의 0/1이 들어가는 칸을 이용해 표현된다는 의미(2진수 표기)

 

unsigned char은 8개의 칸 중 제일 왼쪽 칸이 2⁷이므로 자료형의 범위는 0 ~ 255 (0 ~ 2⁸-1)

->최솟값 00000000일때 0, 최댓값 11111111일때 255

char은 8개의 칸 중 제일 왼쪽 칸이 -2⁷이므로 자료형의 범위는 -128 ~ 127 (-2⁷ ~ 2⁷-1)

->최솟값 10000000일때 -128, 최댓값 01111111일때 127

(*자세한 내용이 궁금하면 2's complement 개념 찾아볼 것)

 

이외에도 정수자료형에는 short(2byte), int(4byte), long long(8byte) 자료형이 있음.

short : -32768 ~ 32767

int : 최댓값 약 2.1×10⁹(21억)

long long : 최댓값 약 9.2×10¹⁸

 

Integer Overflow 주의

01111111 + 1 = 10000000

127 + 1 = -128이 되는 상황

 

실수 자료형

float(4byte), double(8byte)

 

2진수를 실수로 확장해보자.

3.75 = 2 + 1 + 0.5 + 0.25 = 2¹ + 2⁰ + 2^-1 + 2^-2 == 11.11₍₂₎ 

 

2진수에서도 10진수와 마찬가지로 무한소수가 나타날 수 있다.

1/3 = 2^-2 + 2^-4 + 2⁶ + ..... = 0.010101...₍₂₎

 

*IEEE-754 format

IEEE-754 format

 

실수의 성질

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

fraction field를 보면, float은 유효숫자가 6자리, double은 유효숫자가 15자리이다.

이는 float은 상대오차 10^-6까지 안전하고, double은 상대오차 10^-15까지 안전하다는 의미.

실수 자료형이 필요하면 꼭 float 대신 double을 쓰자.

ex) 2진수 기준으로 무한소수인 수를 저장하려고 할 때....

int main(void){
	if(0.1 + 0.1 + 0.1 == 0.3) cout << "true";
    else cout << "false"; 
}	//false 출력

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

double은 유효숫자가 15자리이고, long long은 최대 19자리이기 때문.

cf. double에 int(최대 21억)는 담아도 됨.

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

두 실수가 같은지 알고 싶다면?

->둘의 차이가 아주 작을 때, 즉 오차가 아주 작은 경우(대략 10^-12이하) 동일하다 처리한다.

 

cf.

1e-12 =10^-12 

1e9 =10⁹ 

 

함수인자와 STL

1. 함수 인자로 값을 복사해서 넘겨주는 경우(call by value) : 원본의 값이 바뀌지 X

ex)int를 넘김, 구조체를 넘김, STL을 그냥 넘김

 

2. 함수 인자로 주소를 넘겨주는 경우(call by reference) : 원본의 값이 바뀜

ex) int 배열 arr의 주소를 넘김

void swap(int* a, int* b){
	int tmp = *a;
    *a = *b;
    *b = *tmp;
}

*부족한 부분은 C언어의 함수인자와 포인터 부분 복습할 것

 

C++의 경우 참조자(reference)를 이용한 함수 작성 가능

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

 

STL(Standard Template Library)?

STL은 C++에서 제공되는 라이브러리로, 필요한 자료구조들을 직접 구한할 필요 없이 가져다 쓸 수 있게 해줌.

ex)배열과 비슷한 기능을 하는 vecter STL : 일종의 가변 배열로, 배열의 크기를 마음대로 늘렸다 줄였다 할 수 있음

 

STL을 쌩으로 함수 인자에 넣으면 복사해서 보낸다는 것에 주의! ->하나하나 복사한다는 점에서 시간복잡도 커질수도

따라서 참조자를 이용해 함수 인자로 넘긴다. ->복사X, 주소가 넘어감

 

표준 입출력

1. 문자열 처리할 때, C++ string 사용 가능 *cin/cout 사용할 경우임

 

2. cin은 공백 앞까지만 입력 받으므로 공백을 포함한 문자열을 입력받을 때 주의 

(해결법 : type이 C++ string 한정일때, getline 이용)

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

 

3. cin/cout을 사용할 때, 입출력으로 인한 시간초과를 막기 위한 두가지 명령

ios::sync_with_stdio(0)

C++ stream과 C stream의 동기화를 끊는 명령.

cout과 printf 섞어쓰기 불가. 여기서 0은 false와 같음.

cin.tie(0)

cout 버퍼를 비우지 않도록 하는 코드.

기본적으로는 cin명령을 수행하기 전에 cout 버퍼를 비우는데, 온라인 저지 사이트에서는 채점을 할 때 출력 글자만 확인하므로, 출력 글자 사이사이가 꼬여도 채점에 영향X기 때문. 여기서 0은 nullptr을 의미.

 

4. endl(개행문자를 출력하고 출력 버퍼를 비우라는 명령) 사용X. 차라리 개행문자("\n")를 사용 !

 

코드 작성 Tip

1. #include <bits/stdc++.h> 사용

제한된 시간 안에 정답을 받아야 하는 코딩테스트에서의 효율을 위해...^^

 

2. 출력 맨 마지막에 공백 혹은 줄바꿈이 추가로 있어도 정답처리되므로 별도의 예외처리는 필요하지 않음

 

연습문제 복습(C++)

강의 후반부 및 아래 링크로 들어가면 나오는 문제들 중 해당 강의에 맞는 연습문제들을 풀고

정답코드와 비교하며 얻은 내용들을 간단히 정리한 내용입니다.

연습문제 링크

 

 x & 1

비트연산자 AND

x가 홀수인지 짝수인지 확인할 때 사용 가능 ( x % 2 와 유사)

x가 홀수일때 true/1를 반환, x가 짝수일때 false/0을 반환

cf. x >> 1 은 오른쪽으로 1만큼 시프트라는 비트연산자로, x / 2와 유사