[C++] 코딩테스트 잡Tips 적는 공간

라멘커비·2023년 9월 14일

TIL cpp

알고리즘

목록 보기

9/11

C++로 코테 풀이하며 기억하고 싶은 팁 적어가는 공간

뒤죽박죽 Tips

헤더

#include <bits/stdc++.h> 에 모든 표준 라이브러리가 포함되어 있기 때문에 이 헤더 하나면 충분할 것 (코테볼때 해당 헤더 지원 안 해서 하나씩 씀 ㅠ.ㅠ)
해당 헤더는 그냥 자주쓰는 라이브러리 다 선언해놓은 파일
시간이나 공간이 낭비될 수 있다.
bits/stdc++.h 헤더 추가 방법

기초 코드 작성 요령

scanf/printf와는 다르게 cin/cout에서는 입출력으로 인한 시간초과를 방지하기 위해 반드시 ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 합니다. 두 명령을 실행시키지 않으면 입/출력의 양이 많을 때 시간초과가 발생할 수 있습니다.
ios::sync_with_stdio(0)은 C++ stream과 C stream의 sync를 끄는 명령입니다. 기본적으로는 C++ stream과 C stream 간의 출력 순서를 유지할 수 있도록 sync를 유지하고 있으나, cout만 사용할 경우 sync를 유지할 필요가 없으므로 시간을 절약하기 위해 sync를 꺼야 합니다. 반대로 말하면, 해당 명령을 실행한 이후에는 반드시 printf를 쓰지 말고 cout만 사용해야 합니다.
cin.tie(0)은 cin과 cout이 번갈아 나올 때 마다 flush를 하지 않도록 하는 명령입니다. 채점 환경에서는 input buffer와 output buffer가 분리되어 있기 때문에 flush를 해줄 필요가 없습니다.
비슷한 이유로 줄바꿈을 endl로 하는 경우가 있는데, endl은 줄을 바꾸고(즉 '\n'을 출력하고) flush를 하라는 명령이므로 endl을 사용하면 불필요한 flush 명령이 지속적으로 발생해 시간초과가 발생할 수 있습니다.

STL vector

insert, erase는 시간복잡도가 O(N). push_back, pop_back은 제일 끝에 원소를 추가하거나 빼는 것이니 O(1)입니다.
vector에서 =를 사용하면 deep copy가 발생
ange-based for loop 이용 가능
int e : v1이라고 하면 복사된 값이 e에 들어가고 int& e : v1이라고 하면 원본이 e에 들어갑니다
기본적으로 vector의 size 메소드는 시스템에 따라 unsigned int 혹은 unsigned long long을 반환합니다. 그렇기 때문에 32비트 컴퓨터 기준 3번같이 쓰면 v1이 빈 vector일 때 v1.size() - 1이 unsigned int 0에서 int 1을 빼는 식이 되고, unsigned int와 int를 연산하면 unsigned int로 자동 형변환이 발생하기 때문에 (unsigned int)0 - (int)1은 -1이 아니라 4294967295이 되어버립니다. 4294967295이라는 이상한 값은 unsigned int overflow로 인해 생기게 된 값입니다.
for(int i=0; i<=v.size()-1; i++) <<이렇게 구현하면 큰일난다는 뜻

배열

배열을 전역에 선언하면 따로 초기화 안 해도 0으로 초기화 됨.(bool 배열이면 false)
int arr[10] = {0}; <<0으로 초기화

순열과 조합

next_permutation(a, a+3);
next_permutation은 현재의 수열을 사전 순으로 생각했을 때의 다음 수열로 만들고 true를 반환하는 함수, do-while문으로 딱떨어짐
조합은 오른쪽처럼 0과 1이용해서 구현하면 됨

#include <bits/stdc++.h>
using namespace std;
int main() {
	int arr[3] = { 1, 2, 3 };
	do {
		for (int i = 0; i < 3; i++)
			cout << arr[i] << ' ';
		cout << '\n';
	} while (next_permutation(arr, arr + 3));
	return 0;
}

문자열

split() 함수 직접 구현해본것

vector<string> split(string& s, string& sep) {
    int pos = 0;
    vector<string> res;

    while (pos < s.size()) {
        int nxt_pos = s.find(sep, pos); //pos부터 찾는 것
        if (nxt_pos == -1) {
            nxt_pos = s.size();
        }
        if (nxt_pos-pos>0) res.push_back(s.substr(pos, nxt_pos-pos));
        pos = nxt_pos + sep.size();
    }
    return res;
}

split() 구현 모아봤던 나의 글 (추가해야겠당...)

find() 두 가지

헤더 1

#inclue <string>

사용법

s.find(찾을 문자열 , 검색 시작 위치, 찾을 문자열 길이)
찾은 문자열의 첫 위치 반환

	string s = "My Hello World!";
	
	if (s.find("Nothing") == string::npos)
		cout << "npos\n";					// npos

	cout << s.find("Hello") << "\n";		// 3
	cout << s.find("H", 3) << "\n";			// 3
	cout << s.find(" ", 3) << "\n";			// 8 (두 번째 공백의 위치 검색되었음)
	cout << s.find("long", 3, 2) << "\n";	// 6 (long에서 2글자인 lo만 검색하기 때문)

헤더 2

#inclue <algorithm>

사용법

find(찾기 시작할 위치, 마지막 위치, 찾을 값)
find(v.begin(), v.end(), 10);
iterator로 반환

	vector<int> v = { 100, 655, 1, -40, 10, 55 };
    
	vector<int>::iterator it = find(v.begin(), v.end(), 10);
    
	cout << *it << "\n";			// 10
	cout << it - v.begin() << "\n";	// 4 (인덱스 알아내는 법)