C++-PS용 팁, 기본기

TonyHan·2020년 9월 28일
0

알고리즘

목록 보기
4/23
post-thumbnail

반드시 한 번에 하나의 일만 처리하기

1. 입력

백준 11718 %\n 이 있을때 까지 읽기

#include <cstdio>
char s[101];
int main() {
    while (scanf("%[^\n]\n",s)==1) {
        printf("%s\n",s);
    }
    return 0;
}

[^\n]의 의미는 \n이 있을 때까지 읽는 것이고
이게 없을때는 0을 반환하여 탈출하게 된다.

단 반드시 배열만 사용해야 한다.

문자와 숫자가 함께 있는 입력

문자와 숫자가 혼용되어서 입력으로 들어온다면 무조건 String으로 받아들인다음 변환하는 게 빠르다.

예를 들어 이렇게 생긴거

긴 문자열 한 번에 읽기

#include <string>
string s;
getline(cin,s);
cin.ignore();

반드시 cin.ignore() 해주어야 \n문자 무시

2. 출력

cout 소숫점 정의

cout<<fixed;
cout.precision(2);

6. 구조체

묶어서 성분 받기

#include <functional>
struct point{
	intx,y;
}
queue<point> q;
q.push({1,1});
tie(s,e) = q.front();

7. 자료구조

스택

추가 및 삭제
push(element): 스택에 원소를 추가
pop(): 스택에 있는 원소를 삭제
조회
top(): 스택 제일 앞에 있는 원소를 반환
기타
empty(): 스택이 비어있으면 true 아니면 false를 반환
size(): 스택 사이즈를 반환

O(1)

추가 및 삭제
push(element): 큐에 원소를 추가(뒤에)
pop(): 큐에 있는 원소를 삭제(앞에)
조회
front(): 큐 제일 앞에 있는 원소를 반환
back(): 큐 제일 뒤에 있는 원소를 반환
기타
empty(): 큐가 비어있으면 true 아니면 false를 반환
size(): 큐 사이즈를 반환

우선순위 큐(힙)

#include <queue>

priority_queue<int> q;
q.push();
q.top();
q.empty();
q.pop();

---
## string
### string에 같은 문자가 포함되었는지 확인
```c
str1.find(str2)

성공시 위치(0부터 시작) 반환
실패시 string::npos 반환

하지만 cpp에서의 우선순위 큐는 맥스힙이기 때문에 이것을 민힙으로 바꾸는 과정이 필요하다.

방법은 두가지가 있다.
1. 모든 성분을 음수로 입력한다.(코딩이 간단, 입력이 음수면 대응못함)
2.

추가 및 삭제
push(element): 큐에 원소를 추가(뒤에)
pop_front(): 큐에 있는 원소를 삭제(앞에)
pop_back(): 큐에 있는 원소를 삭제(앞에)
조회
front(): 큐 제일 앞에 있는 원소를 반환
back(): 큐 제일 뒤에 있는 원소를 반환
기타
empty(): 큐가 비어있으면 true 아니면 false를 반환
size(): 큐 사이즈를 반환
  1. 연산자 우선순위
  2. 계산결과 큰거
  3. 좌측

8. STL 라이브러리

cmath 라이브러리에 있는 M_PI 사용하기

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <math.h>
#define ll long long
using namespace std;
int main(void) {
	freopen("input.txt", "r", stdin);

	double r;
	scanf("%lf", &r);
	printf("%.6lf\n", r * r * M_PI);
	printf("%.6lf\n", 2 * r*r);
	
}

#define _USE_MATH_DEFINES 필수로 선언
하면 이제 M_PI를 사용 가능

memset 사용시 주의점(PS용)

memset은 배열이든 벡터든 원하는 행열은 모두 채워주는 함수이다.

//오직 c언어에서 사용하던 string 라이브러리만이 
//memset을 사용할 수 있게 해준다.
#include <cstring>
#include <string.h>

int arr[40][2];

int main(void){
	memset(arr,0,sizeof(arr))
}

으로 초기화 해줄 수 있다.

rotate 함수 사용하기(시뮬레이션)

rotate(시작위치 이상, 회전 시킬 범위 끝 미만, 위치 어디로)
[이상, 미만) 으로 데이터를 어딘가의 위치로 이동시킨다.

이것을 위해 표준형태 두가지가 존재하니 두개다 알고 있자

참고로 아래와 같이 사용안하고 제멋대로 쓰면 에러뜬다... 젠장

#include <algorithm>

vector<int> a = {1,2,3,4,5};
rotate(a.begin(), a.begin()+1, a.end()); // 첫번째 성분을 끝 위치로 옮기겠다. == 왼쪽으로 한칸식 데이터 이동
rotate(a.rbegin(), a.rbegin()+1, a.rend()); // 맨 끝의 데이터를 가장 앞으로 옮기겠다. == 오른쪽으로 한칸식 데이터 이동

http://www.cplusplus.com/reference/algorithm/rotate/?kw=rotate


벡터(vector)

기본 사용법

#include <vector>

int main(void){
	vector<int> a;
    //그냥 행렬용 벡터
    vector<int> a();
    //연결 리스트용 벡터
    vector<int> a[]
}

2차원 벡터 선언하기

맨날 까먹는다

#include <vector>
using namespace std;


vector<vector<int>> d(90, vector<int>(2, 0));

90 x 2 크기의 0으로 초기화 된 2차원 벡터 생성

벡터 중복 제거(unique)

반드시 sort를 먼저 한다음 진행 왜냐하면 앞뒤 문자를 비교하고 제거하는 방식으로 진행되기 때문

unique(a.begin(),a.end())

반환되는 값은 중복제거 후의 벡터 쓰래기값의 첫번째 인덱스 값

따라서 아래의 erase와 콜라보 필요

a.erase(unique(a.begin(),a.end(),a.end())

원리는

102020303040

unique 실행후

102030403040

위와 같이 만들어 지며 unique함수의 원리는 중복되지 않은 값을 앞에서부터 채워나가는 원리이고 채우지 않은 부분(위에서는 40다음의 30)의 위치를 반환해 준다.

벡터 정렬(sort)

#include <algorithm>
answer.erase(unique(answer.begin(), answer.end()),answer.end());
 
//기본
sort(a.begin(),a.end()); //오름차순
//임시객체사용
sort(a.begin(),a.end(),greater<>()); //내림차순
sort(a.begin(),a.end(),less<>()); //오름차순

//람다식 사용-람다에서는 참조형을 안써도 됨
sort(a.being(),a.end(), [](j u,j v){return u.v>v.v});

//함수사용-함수에서는 참조형으로 변수를 받아야 함
sort(a.begin(),a.end(), cmp);

벡터 데이터 삭제(erase)

erase(int position)
해당하는 위치의 원소를 지운다.
v.erase(v.begin()+4)는 벡터 v의 다섯 번째 원소를 지운다.(0+4 인덱스)

erase(int start, int end)
해당하는 범위의 원소를 지운다. start는 포함하고, end는 포함하지 않는다.
v.erase(v.begin()+2, v.begin()+5)는 세 번째부터 다섯 번째 까지의 원소를 지운다.

다른 벡터를 뒤에 붙이기, 중간에 삽입하기(insert)

vector<int> v;
//처음 위치에 1 삽입, 삽입되는거지 기존위치의 값을 삭제하는게 아닌 밀어내고 그자리에 들어간다.
v.insert(v.begin(), 1); 
// 3번쨰 위치에 1 삽입
v.insert(v.begin() + 3, 1); 

vector<int> tmp;
//vector 붙이기
v.insert(v.end(), tmp.begin(), tmp.end());

lower_bound, upper_bound

#include <iostream>
//lower_bound는 찾으려 하는 key값이 "없으면" key값보다 큰 가장 작은 정수 값을 찾습니다.
auto it=lower_bound( begin(), end(), value);

//upper_bound는 key값을 초과하는 가장 첫 번째 원소의 위치를 구하는 것 입니다.
auto it=upper_bound( begin(), end(), value);

해서 그 위치를 iterator 형태로 반환해 준다.

최대, 최솟값

안타깝게되 vector은 최대, 최솟값을 구하는 함수가 다르다.

	vector<int> vec = { 3, 4, 2, 6, 8, 10 };
	int min = *min_element(vec.begin(), vec.end());
	int max = *max_element(vec.begin(), vec.end());
	cout << "min : " << min << endl;
	cout << "max : " << max << endl;
    
    // 최댓값 위치
    int max_pos = max_element(vec.begin(), vec.end()) - vec.begin();

max_element와 min_element만을 받는다. 이거가 아닌 max, min 함수를 사용하면 함수가 작동을 안한다.

다른 벡터 복사하기, 벡터에 인자값 넣기

int main(int idx)
{
	vector<int> a = {idx}; //값 넣기
    vector<int> b = (a); //값 복사하기값 복사하기
}

범위기반 반복문(ranged-based for statement : C++11)

https://blockdmask.tistory.com/319

for (element_declaration : array) statement;


//이런식으로 벡터안에 있는 값을 건드릴수도 있다.
vector<int> tmp;
for (int &i : tmp)
{
	i = (i + 1) % 4;
}

for(vector<int>::it = tmp.begin(); it < tmp.end(); ++it)

emplace_back

https://shaeod.tistory.com/630

※ 참고 사항

  • push_back으로 하여도 컴파일러 내부적으로 최적화 하기 때문에 emplace_back으로 하는 것과 별차이가 없을 수 있다. 고로 개인 프로젝트가 아니라면 호환성이 더 좋은 push_back 사용이 더 나을 수도 있다.

  • push_back함수로 할 수 있는 모든 것을 emplace_back으로 할 수 있다.

  • push_back함수보다 emplace_back 함수가 대체로 효율적이다.(무조건적인건 아님 반대로 push_back이 더 효율적일 때도 있음)

  • 중요한건 vector가 tuple을 쓸때는 push_back을 사용할 수가 없음

vector<tuple<int,int,int>> cctv;
cctv.emplace_back(a[i][j],i,j);

String

String 입력

기본적으로 String 입력은 개같다.

  • 덧셈 나눗셈 형태

    이 경우는 숫자를 10의 자리로 따로 또 처리를 해주어야 한다.
string str;
cin>>str;
int num = 0;
for (int i = 0; i < str.size(); ++i) {
//문자 따로, 숫자 따로 if 문을 만든다.
		if (str[i] == '+' || str[i] == '-') {
			sign.push_back(str[i] == '+' ? 1 : -1);

			val.push_back(num);
			num = 0;
		}
        
        //특히나 이런식으로 알고리즘을 짜면 10,100자리도 충분히 받아올 수 있다.
		else {
			num += num * 10 + (str[i] - '0');
		}
	}

긴 문자열 한 번에 읽기

#include <string>
string s;
getline(cin,s);
cin.ignore();

반드시 cin.ignore() 해주어야 \n문자 무시

string을 int로 바꾸기

ans=stoi(str1);

string 문자 하나를 int로 바꾸기

얘는 함수가 따로 존재하지 않는다.

ans=str1[0]-'0'

string 문자 하나 빼기

str.erase(0,0)

단 str이 아예 바뀌기 때문에 원래대로 돌려주는 과정이 필요

string 비교하기

a.compare(b) < 0

strcmp와 비슷한 역활 수행

pair

변수가 두개이면 pair을 사용하고 변수가 3개이면 구조체를 사용하기
사실 그냥 구조체가 조금 더 편한거 같음

#include <algorithm>
pair<int,int> a;
queue<pair<int,int>> q;
q.push(make_pair(0,0));

입력을 한 번에 받을 때
int s,e;
tie(s,e)=q.front();

tuple

#include <algorithm>
tuple<int,int,int> a;
queue<tuple<int,int,int>> q;
q.push(make_tuple(x,y,z));
tie(nx,ny,nz)=q.front();

BST 이진트리, 이진탐색트리

#include <algorithm>

순열

#include <algorithm>
vector<int> a;
next_permutation(a.begin(),a.end());

multiset

set과 구별되는 multiset의 가장 큰 특징은 key값이 중복된다

#include <set>

multiset<int> ms;
ms.insert();
ms.pop();

//값이 가장 먼저 나오는 곳 [폐구간]
ms.lower_bound();

//값이 가장 마지막에 나오는 곳 바로 다음(개구간)
ms.upper_bound();
multiset<int>::iterator iter;
for(iter = ms.begin(); iter != ms.end(); iter++){
    cout << *iter << " " ;
}

auto로 반복문 돌리기

//참조형 사용
for (auto &it : a){
	it==10;
}
profile
신촌거지출신개발자(시리즈 부분에 목차가 나옵니다.)

0개의 댓글