1. c++ 기본

본 카테고리는 마크다운 언어로 되어있으며, typora같은 마크다운 뷰어를 다운받아서 보는걸 추천드립니다.

1.md

0.01MB

1. c++ 기본

#include <iostream>

using namespace std;

int main(void){
    int A, B;
    cin >> A >> B; // scanf("%d %d", &A, &B); 과 같은 코드
    cout << A + B << '\n'; // printf("%d\n", A + B);
}

문제 참고 : [boj.kr/1000]

2. vector

#include <iostream>
#include <vector> // 가변 길이 배열

using namespace std;

int main(){
    vector<int> arr; // <>는 c++의 새로운 문법
    //vector에 들어갈 타입을 int로 하겠다는 의미, 즉 타입 명시
    //long long, double, vector<int> 등등 아무거나 다 넣을 수 있음.


    //arr.resize(30); // 사이즈 바꾸기
    //arr.erase(10); // 원소 지우기

    for(int i=10; i>0; --i)
        arr.push_back(i);
    for(int i=0; i<arr.size(); ++i)
        cout << arr[i] << ' ';

    cout << '\n';
}

3. queue

할 수 있는게 두가지. push, pop

push를 하면 데이터를 쌓고, pop하면, 들어간 순서대로 데이터를 뽑는다.

4. stack

할 수 있는게 두가지. push, pop

push를 하면 데이터를 쌓고, pop하면 마지막으로 들어간 데이터를 우선으로 뽑는다.

참고 문제 : [boj.kr/9012]

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

int main(){
    stack<int> st;
    queue<int> q;
    for(int i=0; i<=10; ++i) {
        st.push(i);
        q.push(i);
    }

    while(!st.empty())) {
        cout << st.top() << ' ' ;
        st.pop();
    }
    cout << '\n';

    while(!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << '\n'; 
}

5. string

int main(){
    char buf[100];
    scanf("%s", buf);

    string str;
    cin >> str;
    cout << str << '\n'

    string a = "cat";
    string b = "dog";
    if(!strcmp(a, b)) {}
    if(a == b) {}

    if(a == b) {}
    else(a > b) {} // 사전순

    a += "cat" // catcat
    a += " is so beautiful" // catcat is so beautiful

    a = b; // dog

    for(int i=0; i<a.size(); ++i){
        cout << a[i];
    }
    cout << '\n';

    cout << a << '\n';

}

6. 시간 복잡도

time complexity, 주로 big-O 표기법을 쓴다.
문제에 적합한 알고리즘을 찾을 때 사용한다.

현대적인 일반 컴퓨터의 cpu 하나가 1초에 10의 7~8승의 계산을 할 수 있을 때,
문제에서 1≤N≤100000 이라는 조건이 주어졌으면, N의 2승짜리 알고리즘을 사용하면 가망이 없다.
즉, 제시간 안에 돌아가지 않는다.

9012번 예시코드를 보면,
처음 T번 돌아가는 while문 안에 str.size()번 돌아가는 for문 하나가 있다.
str.size()의 길이를 L이라고 하면, O(TL)의 시간복잡도를 가진다고 할 수 있다.

참고 문제 : [boj.kr/13900]

7. algorithm

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int arr1[10];
    vector<int> arr2;
    for(int i=10; i>0; --i)
        arr1[10-i] = i, arr2.push_back(i);
    sort(arr1, arr1+10);
    sort(arr1+3, arr1+5); // [3]..<[5] 즉 [3,5)
    sort(arr2.begin(), arr2.end());

    for(int i=0; i<10; ++i){
        cout << arr1[i] << " " << arr2[i] << '\n';
    }
}

bubble : N^2
quick : NlogN ~ N^2
merge : NlogN
heap : NlogN

algorithm의 std::sort는 merge랑 quick이랑 짬뽕시켜서 돌린다.
그래서 대부분의 경우 최적의 알고리즘으로 알아서 정렬시켜준다.

sort가 for문 안에 있으면 시간복잡도를 다시 계산 해주어야한다.

참고 문제 : [boj.kr/2751, boj.kr/2750]

8. (부록) 문제풀이

//1000.cpp
#include <iostream>

using namespace std;

int main(void){
    int A, B;
    cin >> A >> B; // scanf("%d %d", &A, &B); 과 같은 코드

    cout << A + B << '\n'; // printf("%d\n", A + B);

}

//9012.cpp
#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main(){

    int T;
    cin >> T;
    while(T--){
        stack<int> st;
        string str;
        bool fail=false;
        cin >> str;
        for(int i=0; i<str.size(); ++i){
            if(str[i] == '(') st.push(1);
            else {
                if(st.empty()) {
                    fail = true;
                    break;
                }
                st.pop();
            }
        }
        if(!st.empty()) fail=true;
        if(fail) cout << "NO" << '\n';
        else cout << "YES" << '\n';

    }
}

//예시 : (()())
/*
풀이 :
'('를 만나면 push, ')'를 만나면 pop
도중에 에러가 나면(데이터가 남거나 부족하면) 실패.
끝까지 에러가 안나고, 스택이 비어있으면 성공.
*/

//13900.cpp
#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
int main(){
    int N;
    cin >> N;
    vector<ll> v;
    vector<ll> hap;
    ll cnt=0;
    for(int i=0; i<N; ++i){
        ll a;
        cin >> a;
        v.push_back(a);
        if(i==0) hap.push_back(a);
        else hap.push_back(hap[i-1]+a);
    }

    for(int i=v.size()-1; i>=1; --i){
        cnt+=v[i]*hap[i-1];
    }

    cout << cnt << '\n';
}
/*
우선 문제에 나온 그대로 짜면 어떻게 될까?
N + N-1 + N-2 + N-3 + ... + 1의 시간복잡도를 갖는다. O(N^2)이다.
최악 100000*100000 을 하면 1초 안에 안되므로 다른 방법을 생각해야 한다.

다르게 생각해보자.
2*3 + 2*4 + 2*5 는 2*(3+4+5)이다. 
즉, 합을 미리 구해놓고 풀면 된다.

hap[0]에는 v[0]이,
hap[1]에는 v[0]+v[1]이,
hap[2]에는 v[0]+v[1]+v[2]이,
...
hap[N-1]에는 v[0]+v[1]+...+v[N-1]이 들어가게 된다.
이 때, 답은 v[N-1]*hap[N-2] + v[N-2]*hap[N-3] + .. + v[1]*hap[0]이 된다.

또는 그냥 hap을 쓰지 않고, 변수 하나에 v의 모든 값을 합한 값을 넣고, 해도 된다.
*/

//2750.cpp, 2751.cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    int N;
    vector<int> v;
    cin >> N;
    for(int i=0; i<N; ++i){
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());
    for(int i=0; i<v.size(); ++i){
        cout << v[i] << '\n';
    }
}