c++ more upgrade

setprecision

⇒ 유효숫자를 결정해준다.

c++

#include <iomanip>
#include <iostream>

using namespace std;
int main(){

double f =3.14159265358979;

// 반올림해서 출력
cout<< setprecision(5)<<f<<<"\n"; // 유효숫자 5자리  3.1416
cout<< setprecision(8) << f<< "\n";// 유효숫자 8자리 3.1415927
cout <<setprecision(10)<<f<<"\n";
// 소숫점 몇쨰 자리 까지 출력해라.
cout<<fixed<<setprecision(5)<<f<<<"\n"; // 유효숫자 5자리  3.14159
cout<< fixed<<setprecision(8) << f<< "\n";// 유효숫자 8자리 3.14159265
cout <<fixed<<setprecision(10)<<f<<"\n";

return 0;

}

• 항상 "\n"쓰고 endl 쓰지 말것

#include <iostream>
using namespace std;
int main()
{
//cin cout 속도 높이기
ios_base::sync_with_stdio(false);
// 별찍기
    int N;
    cin >> N;
    for (int i = 1; i < N + 1; i++)
    {
        cout << i <<"\n";// 36MS
// 이것 보다도 printf 가 제일 빠르다.
printf("%d\n",i); // 20MS
    }
}

ios_base::sync_with_stdio(false)는 scanf/printf와 같이 쓰면 절대 절대 절대 안 됩니다!!

auto

컴파일러가 타입을 추론해서 타입을 결정한다.

변수의 타입을 명확하게 알 수 있어야한다.

아래 코드는 컴파일 에러가 난다. 선언할 당시에는 a와 b 타입을 모르기 떄문

auto a=0,b=0; //int 라는 것을 알려줌.
//auto 로 선언한다해도  형변환이 자유롭지 못하다.
//auto a.b;

cin >>a>>b;
cout<< a+b<<"\n";

auto 는 이터레이터를 사용할 때 매우 편리하다.

map<pair<int, int>, vector<pair<int, string>>>d;
for(map<pair<int, int> , vector<pair<int, string>>>::iterator it = d.begin();it != d.end(); ++it){
}

// 이런 코드를 
map<pair<int, int> , vector<pair<int, string>>> d;
for(auto it = d.begin(); it != d.end(); ++it){

}
// 이렇게 줄일 수 있다.

range-based for : foreach 문과 유사

#include <vector>

vector<int> a= {1,2,3,4,5};

for(int x:a){
            cout<< x<<" ";
}
cout<<"\n";

range based for

pair

vector<pair<int, int>> a ={{1,2}, {3,4}, {5,6}};
for(int i =0; i<a.size(); i++){
cout<<a[i].first +a[i].second<<" ";
}
cout<<"\n";

for(auto &p: a){
cout<< p.first + p.second << " ";
// 이런식으로 &를 붙이면, 배열 안에 배열에도 접근이 가능하다.
}
cout<<"\n";

int sum =0;
for(auto x: {1,2,3,4}){
    sum+=x;
}
cout<<"sum= "<<sum<<"\n";
int a[] = {1,2,3,4,5};
sum =0;
for(auto x:a){
    sum +=x;
}
cout<<"sum="<<sum<<"\n";

const char cstr[] = "string"; // null 이 배열 끝에 포함되게 됨. 7
sum =0;
for( auto x:cstr){
sum+=1;
}
cout<< "sum = "<<sum <<"\n";
string str = "string"; //6
sum =0;
for(auto x: str){
sum +=1;
}
cout<<"sum ="<<sum<<"\n";

초기화 리스트

vector<int> a;
a.push_back(1);
a.push_back(3);
a.push_back(7);
a.push_back(13);
a.push_back(50);
// 이게 가능

vector <int> a = {1,3,7,13,50};

struct Person{
    string name;
    int age;
}

set<int> s ={1,2,3,4,5};
map<int, string> m ={ {20, "a"}, {10,"hi"}};
Person p = {"you", 20}
    map<int, vector<pair<int,int>>> m2 ={ASXAz{10,{{1,2},{3,4}}},
{20,{{5,6},{7,8},{9,10}}}
};

람다 함수

익명함수라고 함. 이름이 없는 함수

[캡처](함수 인자) { 함수 내용}

람다 함수 밖의 변수를 사용하고 싶은 경우 캡처 자리에 & 를 붙여 넣어주면 된다.

캡처에 & 를 넣으면, 선언하는 시점에서 바깥에 있는 변수를 모두 사용할 수 있다.

&x 와 갗이 어떤 변수를 사용할 것인지 적을 수도 있다.

&는 참조이고, = 는 값 복사이다.

여러 개는 , 를 이용할 수 있다.

int sum(int x, int y ) {
retur x+y;
}
// 람다 1
cout << sum(1,2) << "\n" ;
cout << [](int x, int y){
return x+ y;
}(1,2) << "\n";
// 람다 2
auto sum2 = [](int x, int y) {
return x+y;
};
cout <<sum2(1,2)<< "\n";

#include <iostream>
//https://www.acmicpc.net/submit/2555
using namespace std;
int main(){

    auto print =[]{
        cout<< "10/14"<<"\n";
    };
    print();

}

함수의 변수 타입은 #include <functional> 에 선언되어있다.

function < 리턴타입(콤마로 구분한 인자의 타입들)>

function<void()> print = [] {
};
function<void(int)> print2 = [](int x){

};
function<int(int, int)>sum = [](int x, iny y ){
return x+y;
}

피보나치수 5

재귀 호출을 사용할 경우에는 람다에 auto 가 아니라 형 지정을 해줘야한다.

#include <functional>
#include <iostream>
using namespace std;

int main() {

    int n;
    cin >> n;

    function  <int(int)> f = [&](int n) {
        if (n <= 1) return 1;
        else return f(n-1)+f(n-2);
    };
    cout << f(n) << "\n";
    return 0;
}

사칙연산

vector<function<int(int, int)>>d;
d.push_back([], (int x, int y ){
return x+y;
});
d.push_back([](int x, int y){
return x-y;
});
d.push_back([](int x, int y) {
return x+y;
});
d.push_back([](int x, int y) {
return x/y;
});
d.push_back([](int x, int y) {
return x%y;
});

for (auto &f: d){
cout <<f(a.b) << "\n";
}

STL(1)

• STL container 구성요소
  • standard template libaray
  • 알고리즘
  • 컨테이너
  • 함수
  • 이터레이터

pair

• pair 을 사용하면 두 자료형 T1과 T2 를 묶을 수 있다.
• 항상 두 개로 묶는다
• 첫 번째 자료는 first
• 두 번째 자료는 second로 접근할 수 있다.

#include <utility>

에 있는데, algorithm, vector와 같은 헤더파일에서 이미 include 하고 있기 때문에 따로 include 하는 경우는 거의 없다.

make_pair 를 이용하거나, 생성자를 이용해서 만들 수 있다.

pair<int, int> p1;
cout<< p1.first << " "<<p1.second<<"\n";

p1 = make_pair(10,20);
cout<<p1.first << " "<< p1.second <<"\n";
p1 = pair<int, int>(30, 40);
cout<< p1.first <<" " <<p1.second<< "\n";
pair<int, int> p2(50,60);
cout<<p2.first<<" "<<p2.second<<"\n";

pair 은 2개 까지만 저장할 수 있기 때문에 4개를 저장하려면 pair 에 pair 을 해야한다.

pair<pair<int, int>, pair<int, int>> p 
= make_pair(make_pair(10, 20), make_pair(30,40))

cout<<p.first.first << " "<<p.first.second;
cout<<p.second.first<<" "<<p.second.second;

// 10 20 30 40

tuple

• tuple 은 pair 과 같지만, 여러개를 묶을 수 있다.
• .first, .second, .third, .fourth .. 가 아니고 get 을 이용해서 인덱스로 접근해야한다.
• tuple 은 #include <tuple> 에 정의되어있다.

tuple<int, int, int> t1 = make_tuple(1,2,3);

cout<< get<0>(t1) <<" ";
cout<< get<1>(t1) <<" ";
cout<< get<2>(t1) <<"\n";

/*
for (int i =0; i<3; i++)
{
    cout<<get<i>(t1)<<"\n";
}
*/

tie

묶어준 값들을 한방에 변수에 넣기 위해 사용함.

auto t = make_tuple(10,20,30);

int x = get<0>(t);
int y = get<1>(t);
int z = get<2>(t);

cout<< x<<" "<<y <<" "<<z <<"\n";

x=y=z=0;
tie(x,y,z) = t;
cout<<x<<" "<<y<<" "<<z<<"\n";

// tie는 pair 에서도 사용할 수 있다.
// 변수값을 무시해야하는 경우에는 ignore 을 사용해야한다.
auto t = make_tuple(1,2,3);

int x, y;
tie(x,y,ignore) = t;

cout<< x<<" "<<y<<"\n"; 

// 한줄로 선언하고 끝내버리기
tie(a,b) = make_pair(b,a);

vector

• vector은 배열이다.
• 길이를 변경할 수 있는 배열이다.
• #include <vector>

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> v1;  // 길이가 0 인 벡터 만들기
    vector<int> v2(10); // 길이가 10인 벡터 
    vector<int> v3(15,1); // 길이가 15인 초기값 1 의 벡터
    vector<int> v4 = {1,2,3,4,5};
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;
int main(){

    vector<pair<int, int>> v5;
    vector<pair<int, int>> v6 = {{1,2}, {3,4}};
    vector<vector<int>> v7;

    int n = 10, m = 20;
    vector<vector<int>> v8(n, vector<int>(m));
// int v8[n][m]
    return 0;

}

vector 에 추가 삭제하는 법

vector<int> a ={1,2,3,4,5};

a.push_back(6); // [1,2,3,4,5,6]
a.push_back(7); //[1,2,3,4,5,6,7]

a.pop_back(); //[1,2,3,4,5,6]
a.pop_back(); //[1,2,3,4,5]
a.pop_back(); //[1,2,3,4]

a.clear(); //[]

a.resize(5); //[0,0,0,0,0]

a.clear(); //[]
a.push_back(1); //[1]
a.push_back(2); //[1,2]

a.resize(5); //[1,2,0,0,0]
a.resize(3); //[1,2,0]
a.clear(); //[]

vector<int> a = {1,2,3,4};
cout<<"size = "<<a.size()<<"\n"; //4

a.push_back(5);
cout<<"size= "<<a.size() <<"\n";
cout<<"empty="<<a.empty() <<"\n";

a.clear();

vector<int> a = {1,2,3};
cout<< "front= "<<a.front()<<"\n";
cout<<"a[1]=" <<a[1]<<"\n";
cout<<"back="<<a.back()<<"\n";

a.push_back(4);

for (int i =0; i<a.size() ; i++){

    cout<<a[i]<<" ";

}
cout<<"\n";

for(int &x:a){
    cout<<x<< " ";
}

cout<<"\n";

vector<int> a= {1,2,3,4,5,6};
for(vector<int>::iterator it = a.begin(); it !=a.end(); ++it)
{
    cout<<*it <<" ";
}
cout<<"\n";

for(auto it = a.begin(); it!=a.end(); ++it)
{
    cout<<"a["<<(it - a.begin()) <<"]="<<*it<<"\n";
}

vector<pair<int, int>>  = a;
a.emplace_back(1,2);
a.push_back({3,4});
a.push_back(make_pair(5,6));

for (auto &x : a){
    cout<<x.first<<" "<<x.second<<"\n";
}
for(auto it = a.begin() ; it!=a.end(); ++it)
{
    cout<<it->first <<" "<<it->second<<"\n";
}

// INSERT

vector<int> a = {1,2,3};
print(a);
//1 2 3
auto it = a.begin();

a.insert(it, 4);
print(a);
//4 1 2 3
it = a.begin() +1;
a.insert(it, 5, 0); print(a);
// 4 0 0 0 0 0 1 2 3
it = a.begin() +2;

vector<int> b = {10,20};
a.insert(it, b.begin(), b.end()); print(a);

//// 4 0  10 20 0 0 0 0 1 2 3

void print(vector<int> &a){

    for(int x: a){

cout<< x<< " ";

}
cout<<"\n";

}

// ERASE

vector<int> a = {1,2,3,4,5};
print(a);

a.erase(a.begin()+2);
print(a);

a.erase(a.begin() +1, a.begin() +3);
//[begin , end)
print(a);

/*
1 2 3 4 5
1 2 4 5
1 5
*/

deque( 포인터 두개인 큐를 의미함)

double ended queue

deque<int> d;
d.push_back(1); print(d); //1
d.push_front(2); print(d);//2, 1
d.push_back(3); print(d);//2,1,3
d.pop_back(); print(d);//2, 1
d.pop_front(); print(d);//1

list

이중 연결 리스트를 의미한다.

중간에 있는 것을 뽑아오기 위해서는 이중연결리스트로 해야한다.

자체 내장 sorting 을 해야함.

리스트 기본 함수

iterator(반복자)

• begin() : beginning iterator를 반환
• end() : end iterator를 반환

추가 및 삭제

• push_front(element) : 리스트 제일 앞에 원소 추가
• pop_front() : 리스트 제일 앞에 원소 삭제
• push_back(element) : 리스트 제일 뒤에 원소 추가
• pop_back() : 리스트 제일 뒤에 원소 삭제
• insert(iterator, element) : iterator가 가리키는 부분 “앞”에 원소를 추가
• erase(iterator) : iterator가 가리키는 부분에 원소를 삭제

조회

• *iterator : iterator가 가리키는 원소에 접근
• front() : 첫번째 원소를 반환
• back() : 마지막 원소를 반환

기타

• empty() : 리스트가 비어있으면 true 아니면 false를 반환
• size() : 리스트 원소들의 수를 반환

list<int> l = {2,1, -5, 4, -3 , 6, -7};
print(l);
l.sort();
print(l);

l.sort(greater<int>());
print(l);
l.sort([](int &u, int&v){
    return abs(u) <abs(v);
});

print(l);

l.reverse();
print(l);

acpc 2346.cc 풍선터뜨리기 문제

Baekjoon/BOJ

n=int(input())
a=[*map(int,input().split())]
b=list(enumerate(a))
i=0
c=[]
while 1:
    c.append(b[i][0]+1)
    x=b.pop(i)[1]
    if not b: 
            break
    if x>0: 
        i=(i+x-1)%len(b)
    else: 
        i=(i+x)%len(b)

print(*c)

#include <iostream>
#include <vector>
using namespace std;
int N;
vector<pair<int, int>>v;
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        v.push_back({ x,i });
    }
    int cur = 0;
    while (1) {
        cout << v[cur].second << '\n';
        auto p = v[cur];
        v.erase(v.begin() + cur);
        if (v.empty())break;
        if (p.first > 0)cur = (cur - 1 + p.first) % v.size();
        else cur = (cur + p.first + v.size() * 1111) % v.size();
    }
    cout << '\n';
    return 0;
}

boj 1406 에디터 문제

1406번: 에디터

이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다.

벡터나 배열로 구현할시, 문자열 에서 끝에나 처음을 빼는 것은 관계(o(1)) 없지만, 중간에 삽입, 삭제 과정이 일어나면, O(n)이라는 시간이 걸린다. 중간에 빼줄떄는 링크드 리스트를 생각하자.

• 링크드 리스트인 이유
  • 왼쪽, 오른쪽으로 한 칸씩만 움직인다.
  • 삽입삭제가 문장 중간에서 일어난다.

Baekjoon/BOJ

파이썬은 링크드 리스트가 없으니, 방법은 두 개의 스택을 이용해 편집기의 문자열을 땠다 붙였다 하는 방법이다. 이 두 개의 스택은 다음과 같이 문자열을 잘라서 가지게 될 것이다.

[백준] 알고리즘 1406번 - python 풀이

# 시간초과 나온다. 이거 그대로 쓰면 
from sys import stdin

sentence= stdin.readline().strip()
sentence+=" "
commands =int(input())
cursor=len(sentence)-1

for command in range(commands):
    comment = stdin.readline().strip()
    len_sentence = len(sentence)
    if comment[0]=='L':
        if cursor ==0:
               continue
        else:
            cursor -=1
            cursor= cursor %  len_sentence
    elif comment[0]=='D':
        if cursor==len_sentence-1:
            continue
        else:
            cursor +=1
            cursor= cursor %  len_sentence
    elif comment[0]=='B':
        if cursor ==0:
            continue
        else:
            sentence = sentence[:cursor-1]+sentence[cursor:]
            cursor -=1
            cursor= cursor % len_sentence 

    elif comment[0]=='P':
            sentence = sentence[:cursor]+ comment[2]+sentence[cursor:]
            cursor +=1
            cursor= cursor % len_sentence

print(sentence)

#include<list>
#include<stdio.h>
#include<string.h>
using namespace std;
char init[100003];
int len =0;
int main(){

    scanf("%s",init);
    len = strlen(init);
    list<char> L;
    for(int i =0; i<len; i++)
        L.push_back(init[i]);

    auto cursor 

}

• vector , list, deque 는 순서가 있는 어레이와 유사한 구조이다.

03 STL Container (2)