1. STL(Standard Template Library)

알고리즘, 컨테이너, 이터레이터, 펑터를 제공하는 라이브러리

(1) 알고리즘

정렬, 탐색등의 알고리즘

(2) 컨테이너

array, vector, deque, forward_list, list, set, map, multiset, multimap, unordered_set, unordered_map, unordered_multiset, unordered_multimap 등의 자료구조

(3) 이터레이터

&*로 주소 반환이 가능하고, 모든 자료구조에서 사용 가능한 포인터

2. scanf로 실수타입을 정수타입으로 받기

5.8 같은 double 타입을 scanf쓰면 소수점 기준으로 구분해서 int타입 2개로 받을 수 있다.

scanf("%d.%d", &a, &b);

3. getline

(1) getline(cin, 입력을 저장할 변수, 문자 1개짜리 구분자) 를 활용해 구분자를 기준으로 나누어 입력받기

예를들어 입력이 3.2.4.5.6.1.1 이런식으로 들어오는경우 .을 기준으로 나눠서 3,2,4,5,6,1,1을 따로 입력 받을 수 있다.

getline(cin, s, '.');

구분자 생략시 자동으로 '\n'으로 설정된다.

(2) cin->bufferflush->getline 순서로 사용해야한다

cin쓰고나서 바로 getline 쓰면 오류가 발생한다. cin -> buffer flush -> getline 순서로 사용해야한다.

cin >> T;
for(int i = 0; i < T; i++){
getline(cin, s);
cout << s << "\n";

예를들어, 위와 같이 코드를 작성하면 오류가 발생한다.

cin은 공백, 탭, 개행 전까지 읽으므로 라이브러리 버퍼에 '\n'이 저장되어있다.
이때 getline()을 수행하면, 개행 전까지 버퍼에서 꺼내므로 s에는 공백이 저장되버린다.

cin >> T;
string bufferflush;
getline(cin, bufferflush);
for(int i = 0; i < T; i++){
getline(cin, s);
cout << s << "\n";

위와 같이 cin -> bufferflush -> getline 순서로 사용하면 이 문제를 해결할 수 있다.

4. cout

(1) cout으로 실수 출력하기

cout으로 실수 출력시, 전체를 출력하지않고 일부만 출력한다. 하지만 내가 원하는 소수점 아래 자릿수만큼 출력하게 만드는 방법이 존재한다.

cout << fixed << setprecision(소수점 아래 자릿수) << 출력할 값 << "\n"

하면 된다.

(2) printf로 실수 출력하기, 정수 출력 형식 설정하기

printf("%.4lf\n", a); //소수점 아래 4자리까지 출력
printf("%02d\n", b); // 정수를 2자릿수 형태로 출력. 예를들어 04면 04, 18이면 18

5. std::string -> char[] 변환

s1.c_str() 하면 C++ Style 문자열인 std::string이 C Style 문자열인 char[]로 변환된다.

6. 타입과 타입 변환

(1) 값에도 타입이 존재한다. 그러나 생각하지 않는다.

예를들어 리터럴로 5를 입력한다.
그러면 이 5는 int 5 이다.
그러나 일부 경우를 제외하고는 코딩을 하는 과정에서 우리는 타입은 무시하고 5라는 값 만 생각하면된다.

(2) 값의 타입을 생각해야하는 경우

✍ vector1.size()

vector 의 size() 는 unsigned long 타입으로 벡터의 크기를 반환한다.

만약

vector1.size()-5

를 했는데, vector1.size()가 5보다 작을 경우 음수 표현이 불가하므로 -> 언더플로 발생 -> 결과가 매우 큰 양수로 나타날 수 있다.

이를 막기위해 vector1.size()-5 와 같은 연산을 수행하는 경우 int로 형 변환이 필요하다.

(int)vector1.size()-5

이러면 값이 정상적으로 음수가 나온다.

✍ cout으로 char 출력하는 경우

char 를 cout 하면 아스키코드가 아니라 그에 상응하는 문자가 출력된다. 주의하자.

(3) 암묵적 형 변환

서로 다른 타입의 수가 사칙연산으로 연산되는 경우, 암묵적으로 형 변환이 일어난다.

long double, double, float, unsigned long long, long long, unsigned long, long, unsigned int, int

순으로 강하다.

7. char

(1) 0='\0'=NULL

위의 3개는 완전히 동일하다. 왜일까?

0은 그냥 0이다. '\0' 과 NULL의 아스키코드는 0이다. 따라서 위의 3개는 전부 동일하다.

(2) 문자를 숫자로 바꾸기

char - '0'하면 숫자를 반환한다.

(3) 숫자를 문자로 바꾸기

char(한 자리 정수 + '0') 하면 한 자리 정수가 문자로 바뀐다.

(3) 몇 번째 알파벳인지 구하기

• char - 'a' 하면 몇 번째 소문자 알파벳인지를 반환한다. (0번째 부터 시작)
• char - 'A' 하면 몇 번째 대문자 알파벳인지를 반환한다. (0번째 부터 시작)

8. std::string

(1) string의 인덱스는 1바이트 단위로 메겨진다.

한글은 1 글자가 3byte, 영어는 1 글자가 1byte이다.

따라서 한글로된 string에 인덱스로 접근하면 이상한 값이 나온다.

(2) 주로 쓰는 함수 🌟🌟🌟🌟

s1.begin() //문자열의 첫 번째 요소 가리키는 이터레이터 반환, O(1)
s1.end() //문자열의 마지막 요소의 다음을 가리키는 이터레이터 반환 O(1)
s1.size() 문자열의 사이즈 반환. 시간 복잡도 O(1)
s1.insert(위치, 문자열) //s1의 특정 인덱스에 문자열 삽입.시간 복잡도 O(n+m) 최악의 경우 n개 밀고, m개 복사
s1.erase(위치, 길이) //s1의 특정 인덱스로부터 지정한 길이 만큼을 삭제.시간 복잡도 O(n). 최악의 경우 n개 당겨야함
s1.push_back(char a); // 문자열의 끝에 한 글자를 추가함.시간 복잡도 O(1)
s1.pop_back(char a) // 문자열의 끝에 한 글자를 지움.시간 복잡도 O(1)
s1.find(문자열) // 시간 복잡도 O(n) 또는 O(n*m)
s1.find(문자열, 탐색 시작 인덱스) // 시간 복잡도 O(n) 또는 O(n*m)
s1.substr(위치, 길이) // s1의 특정 인덱스로부터 전달한 길이만큼을 반환. k가 인자로 전달한 길이일때, 시간 복잡도는 O(k)
reverse(s1.begin(),s1.end()) //s1 원본을 반대로 뒤집는다. 시간 복잡도 O(n)
split() // 특정 문자열 구분자로 문자열을 구분하여 벡터로 반환하는 함수로, 사용자가 직접 정의해서 쓰는 함수이다

시간복잡도가 왜 이렇게 될까?

• s1.begin(),s1.end() :std::string 내부적으로 시작 요소를 가리키는 이터레이터가 존재하고, 내부적으로 string의 size도 유지하고있기 때문에 O(1)이다.
• s1.size() : 내부적으로 string의 size를 유지하고있기 때문에 O(1)이다.
• s1.insert(위치, 문자열), s1.erase(위치, 길이) : 위치 찾는건 바로 가능하나, 문자열 삽입 or 삭제시 공간 확보 or 축소를 위해서 기존 문자열을 뒤로 밀거나 앞으로 당겨야하기 때문에 O(n)
• s1.push_back(char a), s1.pop_back(char a) : size만 +1 하거나 -1하면 되므로 O(1)
• s1.find(s2) // 문자열 크기가 n, 찾는 문자열 크기가 m이면 최악의 경우 n번 순회하며, 각 순회에서 m번씩 비교해야함 -> 평균 O(n), 최악의 경우 O(n*m)
  • 내부적으로 문자열을 앞에서부터 순회하며 첫 글자가 같은 경우 s2를 순회하며 비교함
• s1.substr(위치, 길이) // 인자로 전달한 문자열 길이만큼 복사해야함 -> O(m)
• reverse(s1.begin(),s1.end()) // 양쪽에서 서로 바꾸면 ,, 뒤바꾸는 연산을 총 2/N번 해야함 -> O(N)

std::string 관련 함수는 s1.size()랑 s1.pop_back() 만 O(1) 이고, 나머지는 전부 O(n) 이다.

(3) std::string -> 정수 변환

atoi(s1.c_str()) <----- 추천되는 방법

s1.c_str()하면 std::string->char[]로 변환되고,
atoi() 하면 char[]->int로 변환되어 반환된다.

만약 s1이 숫자 문자열 (예를들어, "423") 면 정상적으로 int 타입의 숫자로 반환되고,
만약 s1이 숫자가 아닌 문자열 (예를들어, "hihi")면 0이 반환된다.

stoi(s1) <-------- 비추천되는 방법

std::string -> int로 변환해서 반환한다.

만약 s1이 숫자가 아닌 문자열 (예를들어, "hihi") 이면 오류를 발생시킨다.

9. int는 20억까지, 그보다 큰 수는 long long 써야한다.

4byte 자료형인 int는 약 20억까지 표현 가능하다. 이보다 더 큰 수는 long long 자료형을 사용해야한다.

10. const 키워드 -> sw적 수정 불가해짐

const 키워드는 sw적 수정을 막는 키워드로, 코딩 실수 방지 목적으로 사용한다.

11. pair와 tuple

pair와 tuple은 자주 사용되는 클래스 이다. (자료구조가 아님)

(1) pair

pair는 2개의 값을 저장할때 사용한다.

pair는 위와 같은 구조의 클래스로 first 와 second 라는 멤버를 갖는다.

초기화

pair<자료형,자료형> p1 = {1,2};

값 꺼내기

int a,b;
int a = p1.first;
int b = p1.second;
또는
tie(a,b)=p1;

(1) tuple

tuple은 3개 이상의 값을 저장할때 사용한다.

초기화

tuple<int,int,int> t1 = make_tuple(a,b,c);

값 꺼내기

int a,b,c;
int a = get<0>(t1);
int b = get<1>(t1);
int c = get<2>(t1);
또는
tie(a,b,c)=t1;

12. auto 타입

우변의 타입을 추론하여 결정되는 타입으로, 너무 복잡, 긴 타입명(튜플, 이터레이터 등..)을 대체하는 용도로 사용한다

13. 이터레이터

%*로 주소값 반환이 가능하고, 어느 자료구조에서든 사용 가능한 포인터

컨테이너에서 원하는 요소를 가리킬때 or 순회에 사용된다.

(1) 관련 함수

begin()

컨테이너의 시작 위치를 가리키는 이터레이터 반환

end()

컨테이너 끝 다음의 위치를 가리키는 이터레이터 반환

advance(이터레이터, 목표 값)

해당 이터레이터를 목표 값 까지 증가시킴

14. 배열 관련 빈출 함수

배열이란 vector (동적 배열) 와 array (정적 배열)을 의미한다.

array 는 begin() 과 end()가 존재하지 않는다.

따라서 아래에 나오는 모든 함수들에 대해서 vector의 이터레이터가 들어가는 자리에 array는 주소가 들어가면 된다.

(1) 배열 초기화 함수

vector ---> fill(첫 번째를 가리키는 이터레이터, 마지막 그 다음을 가리키는 이터레이터, 초기화 값)
array ---> fill(시작 주소, 끝 주소, 초기화 값)

특정 값으로 배열을 초기화하는 함수이다.

참고로 전달하는 인자에서 끝 주소는 초기화에 포함이 되지 않는다. 끝 주소 바로 전 주소까지 초기화된다.

fill(arr+0, arr+배열 크기, 초기화 값)

정적 배열을 사용하는 경우는 위와같이 사용하면 된다. 시간 복잡도는 O(n) 이다. (앞에서부터 순회하며 n개 채우니까)

비슷한 기능의 함수로 memset()이 존재한다.

(2) 배열 깊은 복사(Deep Copy) 함수

vector ---> copy(첫 번째를 가리키는 이터레이터, 마지막 그 다음을 가리키는 이터레이터, 목적지의 첫 번째를 가리키는 이터레이터)
array ---> copy(첫 번째 요소의 주소, 마지막 그 다음 요소의 주소, 목적지의 첫 번째 요소의 주소)

배열을 깊은 복사하는 함수 (원본을 복사해서 목적지에 저장하는 함수 -> 더이상 원본과 관련x)

만약 vector v1을 v2에다가 옮기고 싶다면 다음과 같이 코드를 작성하면된다.

vector ---> copy(v1.begin(), v1.end(), v2.begin());
array ---> copy(arr+0, arr+6, test)

이 때, 복사하는 vector와 복사당하는 vector의 크기를 맞춰주는 것이 중요하다.

비슷한 기능의 함수로 memcpy()가 존재한다.

(3) 컨테이너 정렬 함수

sort - 불안정 정렬

vector ---> sort(첫 번째를 가리키는 이터레이터, 마지막 그 다음을 가리키는 이터레이터, 커스텀 비교함수);
array ---> sort(첫 번째 요소의 주소, 마지막 그 다음의 주소, 커스텀 비교함수);

주로 배열을 정렬할 때 사용된다.

• 만약 커스텀 비교함수를 전달하지 않으면 기본적으로 오름차순으로 정렬된다.

• 커스텀 비교함수로 greater<타입>을 전달하면 내림차순으로 정렬된다.

• pair를 기반으로 만들어진 vector의 경우 따로 설정하지 않으면 first, second 순으로
  오름차순 정렬된다.

• 모든 요소들을 2개씩 잡아서 비교했을때, 커스텀 비교함수의 return 값이 참이 되도록 정렬한다.

• 시간 복잡도 O(nlogn)🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟

• cmp 기준 같은 값일때, 기존의 순서가 유지되지 않을 수 있다.🌟🌟🌟

사용자 정의 비교 함수로 정렬하기 🌟🌟🌟🌟🌟🌟🌟

bool cmp(int a, int b) {
	return a > b;
}
vector<int> v1 = {2,5,4,3,1};
sort(v1.begin(), v1.end(), cmp); // v가 5 4 3 2 1 로 정렬된다.

이렇게 사용자 정의 비교 함수로 내림차순으로 정렬도 가능하다.

stable_sort() - 완전 정렬

• cmp 기준 같은 값일때, 기존의 순서가 유지된다. 이외에는 sort()와 기능 동일하다.

(4) 중복 제거 함수

vector ---> unique(첫 번째를 가리키는 이터레이터, 마지막 그 다음을 가리키는 이터레이터);
array ---> unique(첫 번째 요소의 주소, 마지막 그 다음의 주소)

앞에서부터 2개씩 잡아서 비교해서 중복되는 요소는 제거하고 채운다. 빈 공간은 기존 값으로 그대로 채운다. 가장 마지막 중복이 없는 요소의 그 다음 이터레이터를 반환한다.(array의 경우는 포인터 반환)

vector<int> v 가 {1,1,2,2,3,3,4,4,5,5} 일때...
unique(v.begin(),v.end());
하면 {1,2,3,4,5,3,4,4,5,5} 가 된다.

앞에서부터 2개씩 잡아서 비교하므로 -> 시간 복잡도는 O(n) 이다.

주의 : sort() -> unique() 순서로 사용해야한다.🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟

sort() 없이 unique()만 사용하면 중복이 남아있을 수 있다.
(vector v 가 {1,1,2,2,3,3,4,1,5,3} 일때를 생각해보라)

(5) 특정 값이 등장하는 첫 번째 지점, 초과하는 첫 번째 지점 찾기

  v가 벡터일때...
  sort(v.begin(), v.end());
  lower_bound(v.begin(), v.end(), 특정 값) //특정 값이 나오는 첫 번째 지점을 가리키는 이터레이터 반환
  upper_bound(v.begin(), v.end(), 특정 값) //특정 값을 초과하는 첫 번째 지점을 가리키는 이터레이터 반환

주의 : sort() -> lower_bound() 또는 upper_bound() 순서로 사용해야한다.🌟🌟🌟🌟🌟🌟

주의 : 만약, 특정 값이 배열내에 존재하지 않으면 ...

upper_bound() 든 lower_bound()든 인자로 전달한 수를 초과하거나, 기존 크기를 초과한 지점을 가리키는 이터레이터를 반환한다.

(6) 배열의 합 구하기

v가 배열일때...
int sum = accumulate(v.begin(), v.end(), 0);

• 3번째 인자에는 누적에 사용할 초기값을 전달한다.
• 앞에서부터 순회하며 합을 누적하므로 시간복잡도는 O(n) 이다.

(7) 배열의 최댓값 구하기

v가 벡터일때..
int a = *max_element(v.begin(), v.end()); //이터레이터에 역참조하므로 실제 값이 나옴.

max_element(v.begin(),v.end())는 최댓값을 가리키는 이터레이터를 반환한다.

이터레이터도 일종의 포인터이다. 따라서 여기에 역참조 연산을 적용하면 최댓값에 접근할 수 있다.

앞에서부터 순회하며 더 큰값 나오면 갱신하는 방식이므로 시간복잡도는 O(n) 이다.

(8) 배열의 최솟값 구하기

v가 배열일때..
int a = *min_element(v.begin(), v.end()); 

min_element(v.begin(),v.end())는 최솟값을 가리키는 이터레이터를 반환한다.

여기에 역참조 연산을 활용해서 최댓값에 접근한다.

앞에서부터 순회하며 더 작은값 나오면 갱신하는 방식이므로 시간복잡도는 O(n) 이다.

15. 메모리 주소간의 뺄셈

C++ 에서 포인터나 이터레이터 사이의 뺄셈은 인덱스 차이 를 반환한다.