헷갈렸던 내용들 정리하는 이슈

[SHEWANTSME]

비트 & STRING!

#include <iostream>
#include <bitset>
#include <string>
using namespace std;
// using sublime text without debugging sounds okay..? 
int main() {
    unsigned char items_flag = 0;

    //cout << bitset<8>(items_flag)<<endl; // 8비트 사이즈로 00000000이 찍히겠지?
    // make each bit on flags
    const unsigned char opt0 = 2 << 0; -> 데이터 변경이 필요 없을때 쓰는 안전장치!! -> CONST
    const unsigned char opt1 = 2 << 1;
    const unsigned char opt2 = 2 << 2;
    const unsigned char opt3 = 1 << 3;
    const unsigned char opt4 = 4 << 1;
    // 보면 알겠지만 2<<2랑 1<<3 이랑 4<<1은 값이같음 
    // 조금만 생각해보면 알 수 있음

    cout << bitset<8>(opt0) << endl;
    cout << bitset<8>(opt1) << endl;
    cout << bitset<8>(opt2) << endl;
    cout << bitset<8>(opt3) << endl;
    cout << bitset<8>(opt4) << endl;

    items_flag |= opt0;  --> i_f = i_f | opt0 -> 둘의 범위를 합친 범위가 곧 내 범위다.
    cout << "Item0 obtained" << bitset<8>(items_flag) << endl;
    items_flag |= opt2;
    cout << "Item2 obtained" << bitset<8>(items_flag) << endl;
    items_flag &= ~opt3;  --> 드모르간을 생각해보셈 -> opt3이 아닌부분과 i_f와의  교집합이면 i_f에서 opt3을 뺀 부분
    cout << "Item3 lost" << bitset<8>(items_flag) << endl;

}

여기까지 bit 내용! 조금 더 추가해 보자면~

~ -> NOT -> 0000 to 1111

& -> AND -> 1111&0101 = 0101(비교한둘이 모두 1일때 1)

| -> OR -> 1111 | 0101 -> 1111 (둘중하나라도 1일때 1)

^ -> XOR -> 1110 ^ 0100 -> 1010(같으면 거짓이라는 씹변태규칙)

----i 번째 비트 구하기

1. x & (1 << i)

ex) 0 1 0 1 1 에서 3번째 비트를 구하려면 0 1 0 0 0 과 & 연산자를 취해주면 됨. 단, 이 때는 결과가 0이면 i번째가 0이고 0이 아니면 i번째가 1이구나로 판단

2. (x >> i) & 1

ex) 같은 예제에서 0 1 0 1 1 을 3만큼 right shift 해준 값과 & 연산을 취하면, 0 0 0 0 1 즉, 1과 & 연산을 취하게 된다.

그럼 전체 결과가 1인지 0인지로 판단 가능하다.

----- i번째 비트를 0/1로 설정하기

1. 1로 설정하기 x | (1 << i)

x | (1 << i), 해당 자리에 1과 OR 연산 취해주면 1로 바뀌는 것 이용

만약 원래 그 자리가 0 인걸 알고 있다면 x + (1 << i) 를 사용해도 된다.

2. 0으로 설정하기 x & ~(1 << i)

ex) 0 1 0 1 1 에서 3번째를 0으로 바꾸고 싶을 때, 1 0 1 1 1 즉, 해당자리에 0을 주고 & 연산을 취하면 0으로 바뀌게 된다. 그러면 1 0 1 1 1 을 어떻게 찾느냐?

-> 해당 자리만 1로 만든 0 1 0 0 0 에서 ~(NOT) 연산을 취한 값이다.

즉, x & ~(1 << i)

만약 원래 그 자리가 1인걸 알고 있다면, x - (1 << i) 로 사용할 수 있다.

----- 마지막 n 비트 구하기

x & ((1 << n) - 1)

ex) 0 1 0 1 1 에서 마지막 3 비트를 구하고 싶다면 0 0 1 1 1 과 &를 취해주면 된다.

0 0 1 1 1 은 무엇이냐?

-> 0 1 0 0 0 에서 1을 뺀 값이다.

따라서, x & ((1 << n) - 1)

------ i번째 비트 반전

x ^ (1 << i)

ex) 0 1 0 1 1 에서 3번째 1을 0으로 바꾸고 싶다면 0 1 0 0 0 과 XOR 연산을 취해주면 된다.

=========================================

    string str1("one");
    string str2 = str1; -> 솔직히 string은 이런식으로 붙여써도 되나? 싶을정도로 해도 되는부분이 많음 -> 개꿀
    str2.assign("two").append(" three");
    for (int i = 0; i < 3; i++) { -> 이것도 시도해본건데 되더라구
        string s;
        cin >> s;
        str2.append(s);
    }
    //cout << str2 << endl;
    std::swap(str1, str2); -> string끼리 swap,도 됨
    cout << str1 << " " << str2 << endl;

    str1.swap(str2);  --> 이런식으로 써도 되구

    str1.push_back('A'); // 문자열은 안되고 char만 가능

    str1 += "three"; -> 이것도 되고
    str1 = str2 + "for";

        string stt("aaaa");
    stt.insert(2, "Bbb"); // insert는 2번째 인덱스 자리에 Bbb를 넣겠다라는 거임 string("Bbb")해도 되긴함
    cout << stt << endl; // aaBbbaa
}

---

    string my_str = "0123456789";  -> 사이즈 10이 찍히겠지?
    cout << my_str.size() << endl;  -> string은 Cstyle문자열처럼 null캐릭터가 숨어있지 않아요! -> string은 클래스
        -> 직접 길이를 가지고 있기 때문에 null을 찾을 필요 ㄴㄴ하다구

    //cout << std::boolalpha; -> 불알파는 bool을 true나 false로 찍을 수 있게 해주는 함수임
        -> 무조건 cout 을 붙인 상태에서 cout << std::boolalpha; 로 해야 그다음 cout에서 출력해주지
    cout << my_str.empty() << endl;

---

cout << std::boolalpha<<my_str.empty() << endl; 도 될듯? --> ㅇㅇ 되넹

참고로 my_str("")해도 empty하다고 나옴!! -> C랑 다른부분!

참고로 my_str.length, size는 같고! capacity는 알아서 길이 조금 늘린 상태로 나오고!(cout 해보면)

cout << my_str.max_size() << endl; 하면 꽤 큰 사이즈가 나옴

만약
string my_str = "01234567";
my_str.reserve(1000); -> 최소한 1000정도의 capacity가 되게 하라!!
cout << my_str.length() << endl; // 8
cout << my_str.size()<< endl; // 8
cout << my_str.capacity() << endl; // 1007 -> 왜 7인지는 모르겟다

---

아 참고로 string my_str ( "abcdefg"); my_str[100] = 'X' -> 개 미친짓

할려면 try{ my_str.at(100) = 'X';} catch(std::exception &e){ cout << e.what()<<endl;} 해야함,,, -> 굳이?

at이 []바로 접근보단 느리지만 위의 경우같을때는 필요함. -> 벡터랑 비슷한듯?

---

    string hisstr = "abcdefg";
    cout << hisstr.c_str() << endl; // C STYLE //abcdefg
    cout << hisstr << endl;//abcdefg
    const char *arr = hisstr.c_str();// 뭔지 알지?
       /* same as  -> const char* arr = hisstr.data(); */
    cout << arr[6] << endl; // g
    cout << arr[7] << endl;// null (안보임)
    cout << (int)arr[6] << endl; // 103 (ascii)
    cout << (int)arr[7] << endl; // 0 (ascii) -> nullcharacter
    cout << hisstr[6] << endl; // g
    cout << hisstr[7] << endl; // 없엉  -> 엥 근데 hisstr[6,7] 
아스키 찍으면 그냥 똑같이 103 0 나오는딩?

https://blockdmask.tistory.com/338 -> 적기 귀찮으니까 자세한건 여기서 보도록!

substr이랑 compare는 자주 나오므로! 알아둘것!

// string::substr
#include <iostream>
#include <string>

int main ()
{
  std::string str="We think in generalities, but we live in details.";
                                           // (quoting Alfred N. Whitehead)

  std::string str2 = str.substr (3,5);     // "think"

  std::size_t pos = str.find("live");      // position of "live" in str

  std::string str3 = str.substr (pos);     // get from "live" to the end

  std::cout << str2 << ' ' << str3 << '\n';

  return 0;
}
--------------------------------
think live in details.

strcmp (string1, string2) -> 같으면 0 string1이 더 먼저와 -> 음수 string2가 먼저 -> 양수

string1.compare(string2) -> same as strcmp(string1, string2)

비트랑 string 관련내용 review 해보았다!

[SHEWANTSME]

EOF에 관하여

EOF(End of File): 파일의 끝, 더 이상 읽을 데이터가 없다

cin으로 입력을 받으려고 할 때, EOF라면 입력이 취소되고 cin.eof()는 true를 반환한다. 이를 이용하여 파일이 종료될 때까지 입력을 받는 코드를 작성할 수 있다.

터미널(콘솔)에서는 EOF를 수동으로 넣어 주어야 한다.

Windows: Ctrl+z / Unix: Ctrl+d

#include<iostream>
using namespace std;
int main(){
while(true){
cin >> n >> x;
if(cin.eof() ) break; // eof가 true면 break;
cout << n+x << endl;
}

return 0;
}

이 정 도 는 알 거 라 고 생 각 합 니 다!

[SHEWANTSME]

ASCII CODE에 대하여

외어두자

---

int ceta = (alpha > beta) ? alpha : beta; cout << ceta << endl;

[SHEWANTSME]

백준 1002번 문제를 풀면서 느낀 점

아니 ,, 이건 잘 알아둬야 할것 같아서.

오늘도 맞왜틀을 시전중이던 나는 이번 문제에서도 "아니 ㅅㅂ 왜 또 맞는데 틀리다고 나오는거야 ㅅㅂ"라고 궁시렁댔지만

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int testcase, x1, y1, x2, y2, r1, r2; //radsq, pp, mm;
    int lenxy, lenradadd, lenradsubt;
    cin >> testcase;
    for (int i = 0; i < testcase; i++) {
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        lenxy = std::pow((x1 - x2), 2) + std::pow((y1 - y2), 2);
        lenxy = std::sqrt(lenxy);
        //radsq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
        lenradadd = abs( r1 + r2);
        lenradsubt = abs(r1 - r2);
        //pp = (r1 + r2) * (r1 + r2);
        //mm = (r1 - r2) * (r1 - r2);

        if (lenxy == 0) {
            if (lenradsubt == 0) cout << -1 << '\n';
            else cout << 0<< '\n';
        }
        else if (lenxy == lenradadd|| lenxy == lenradsubt) cout << 1 << '\n';
        else if (lenradsubt < lenxy && lenradadd > lenxy) cout << 2 << '\n';
        else cout << 0 << '\n';
    }
}

전혀 틀린게 없는데 왜그럴까? 싶어서 질문검색에 들어가보니,,

---

sqrt 함수의 인풋은 다양한 자료형으로 오버로딩이 돼있고

반환형 자체가 DOUBLE로 알고있어요. (자바 기준)(c++도 포함)

그래서 sqrt(2) 를 하게되면 double형으로 1.41~~~이 나오구요.

그래서 d변수에 넣을 때 int로 선언해도 반환은 double로 되는데, 질문자님께서 애초에 d변수를 int형으로 선언하셨다면 캐스팅에 의해 소수점 부분이 버려질것!

-->그래서 double형의 소수점부분까지 다 받은 뒤 비교가 시작되야 되는데 int로 하면 그러질 못하는것!

[SHEWANTSME]

재귀함수 내용 정리

재귀 함수는 직접,간접적으로 자기 자신을 호출하는 함수임! 재귀에서 가장 중요한 2개가 뭐냐?

1. 종료조건 : 재귀 함수는 항상 하나 이상의 종료조건이 있음. 함수에서 간단한 경우를 처리하고 자기 자신을 호출하지 않는다는 조건.

2. 본문 : 재귀함수의 주요 로직은 본문에 있음. 이 본문에는 지 자신을 호출하는 재귀 확장 구문또한 존재함.

   --> 결론 : 1. 재귀 알고리즘은 종료조건 must need

   2. 재귀 알고리즘은 종료 조건에 도달하게끔 상태를 변경해야함
   3. 재귀 알고리즘은 지 자신을 호출해야함.

etc) 보통 스택 오버헤드 때문에 재귀가 반복문보다 느림. 알고있으셈.

void recur(int n) {
    if (n == 0) return;
    else {
        cout << n << endl;
        recur(n - 1);
    }

}

int main() {
    int n; cin >> n;
    recur(n);

}

이러면 n 부터 역순으로 찍힘 ( 당연하지?)) 하지만

void recur(int n) {
    if (n == 0) return;
    else {
                recur(n-1);
        cout << n << endl;
    }

}

int main() {
    int n; cin >> n;
    recur(n);

}

이러면 1부터 찍힘 ( 생각해보면 당연) 근데 스택 오버플로우 생길 수 있음. 맨밑의 스택에 main의 recur(6)이 있으면 (매개변수, 지역변수, 주소 다 있겠지) recur(5) ,4,3,2,1 까지 쌓이고 1부터 print 하는거니까

void recur(int n) {
    if (n/2 == 1) {
        cout << n / 2;
        cout << n % 2;
        return;
    }   

    recur(n / 2);
    cout << n % 2;

}
void recur2(int n) {
    if (n == 0) return;
    recur(n / 2);
    cout << n % 2;
}

int main() {
    int n; cin >> n;
    recur(n);
    recur2(n);

}

이렇게 짜도 됨

예제 1 ) factorial

void DFS(int n) {
    if (n > 7) return;
    else {
        cout << n << endl;
        DFS(n * 2);
        DFS(n * 2 + 1);

    }
}
int main() {
    DFS(1);
    return 0;
}

                                                   1
                                              2         3
                                        4         5  6       7   

cout가 맨앞이면 전위 순회 1 2 4 5 3 6 7
중간이면 중위순회 4 2 5 1 6 3 7
마지막이면 후위순회 4 5 2 6 7 3 1

예제 2) fibonacci

---

예제 3) Hanoi

#include <iostream>
#include <cmath>
#define fastio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;

bool hanoi(int from, int to , int n){
    if(n ==1){ // 맨밑기둥이면 (맨밑기둥 역할을 하면)  시작기둥에서 파이널기둥으로 옮겨주고
        cout << from << " "<< to << endl;
        return false;
    }
    else{
        hanoi(from, 6-from - to , n-1); // 일단 맨밑에꺼 제외하고 나머지애들(in 시작기둥)을 중간기둥으로
        cout << from << " "<< to << endl; // 그 과정을 찍고
        hanoi(6-from-to, to , n-1); //  나머지 애들을 중간기둥에서 파이널기둥으로 옮기면 끝!
        return 0;
    }
}

int main(){
    fastio; --> 다른사람 코드 보니까 이렇게 하더라고?
    int n; cin >>n;
    cout << static_cast<int>(pow(2,n)) - 1 << endl;  
    hanoi(1,3,n);

    return 0;
}

--> 하노이 문제에서 잘 알아둬야 하는게,, #include 나 #include 같은 애들 쓸때, 항상 반환형태의 자료형을 잘 알아둬야함. 여기서도 pow가 float를 반환하기 때문에, int값이 필요한 나로써는 static_cast 로 강제로 바꿔줘야 제대로된 출력값이 나옴. 비주얼 스튜디오 같이 잘 만들어진 ide는 그냥 알아서 int 로 바꿔주지만 백준은 그러지 않단 말이지 후후

--> 호출되는 순서를 차근차근 다시 봐보자. 처음엔 이해가 잘 안갔는데 이제 알겠음

1 단계 Hanoi(1,3,3) ㄴ Hanoi(1,2,2) ㄴ Hanoi(1,3,1) -> print( 1,3)

2 단계 Hanoi(1,3,3) ㄴ Hanoi(1,2,2) 로 돌아와서 print (1,2) ㄴ Hanoi(3,2,1) -> print(3,2)

3 단계 Hanoi(1,3,3) -> 다시 여기로 오는데, Hanoi(1,3,3)이 재호출되기 이전에 끝난 지점인 Hanoi(A, 6-A-B, n-1) 다음부터 계속 진행 그래서 cout<<A << B니까 print(1,3)

Hanoi(1,3,3) -> print(1,3) ㄴ Hanoi(2,3,2) ㄴ Hanoi(2,1,1) -> print(2,1)

4단계 Hanoi(1,3,3) ㄴ Hanoi(2,3,2) -> 다시 돌아오고나서 찍히는 print(2,3) 그다음 호출되는 Hanoi는 ㄴ Hanoi(1,3,1) -> print (1,3)

여기까지 재귀호출 되었다면 종료됨.

자 이번에는 n값이 커질때 하노이의 탑을 생성하는 방식을 생각해보쟈

#include <iostream>
#include <cmath>
#include <string>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
int Hanoi(int A, int B, int n) {
    if (n == 1) {
        cout << A << " " << B << "\n";
        return 0;
    }
    Hanoi(A, 6 - A - B, n - 1);
    cout << A << " " << B << "\n";
    Hanoi(6 - A - B, B, n - 1);
    return 0;
}

int main() {
    fastio;
    int n; cin >> n;
-----------------------------------------------------
    string s = to_string(pow(2, n) );  -> 여기서부터 내용 달라짐
        // to_string은 int를 string형태로 바꿔주는놈임
    int c = s.find('.');    // find는 '.'의 인덱스 반환
    int len = s.length();
    while (len!= c) { // len이 c가 아닐때 까지 계속 뒤애놈들 지워줌
        s.pop_back(); // 소수점을 지워야되거덩 (pow때매)
        len--;
    }
    s[s.length() - 1] -= 1; // 밑에서 따로 정리
    cout << s << "\n";

    if(n<=20){
       Hanoi(1, 3, n);
    }
    else{
       exit(0);
    }

    return 0;
}

자 대체 왜 s[s.length() - 1] -= 1; 가 성립이 되느냐?

처음에 4 를 입력했다고 칠때, 
        cout << s.length() << endl;  // 4의 제곱은 16인데 STRING이니까 2만큼의 사이즈가 나올거시고
    cout <<typeid( s[s.length() - 1] ).name()<< endl; //  -> 아니 왜 자꾸 까먹냐고 ㅅㅂ TYPEID().NAME까지 써줘야된다고오 여기선 CHAR겠지
    cout << s[0] << endl; // 1
    cout << s[1] << endl; // 6 물론 자료형은 CHAR
    cout << s[1] - 1 << endl; // char 6의 dec 54에서 1 뺀 53
    cout << s[1] - '1' << endl; // char 6에서 char 1 빼니 5
    cout << s[s.length() - 1] << endl; // 6 -> S[1]이니까
    cout << s[s.length() - 1] - 1 << endl; // 53

    s[s.length() - 1] -= '1'; // 아 모르겠다 ㅅㅂ  
    cout << s << endl; // 1 | 가 찍히는데 왜그런거임??

---

예제 4) 재귀함수가 뭔가요? -> 백준 17478번

#include<iostream>
#include <string>
using namespace std;
int cnt = 1;
string s = "\"재귀함수가 뭔가요?\"";
string ss = "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.";
string sss = "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.";
string ssss = "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"";
void recur(int n) {
    if (n == -1) return;
    if (n == 0) {
        if (cnt > 1) {
            int i = 0;
            while (i < 4 * (cnt - 1)) {
                cout << "_";
                i++;
            }
        }
        cout << s << "\n";
        if (cnt > 1) {
            int i = 0;
            while (i < 4 * (cnt - 1)) {
                cout << "_";
                i++;
            }
        }
        cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"" << "\n";
        return;
    }
    if (cnt > 1) {
        int i = 0;
        while (i < 4 * (cnt-1)) {
            cout << "_";
            i++;
        }       
    }
    cout << s << "\n";
    if (cnt > 1) {
        int i = 0;
        while (i < 4 * (cnt-1)) {
            cout << "_";
            i++;
        }
    }
    cout << ss << "\n";
    if (cnt > 1) {
        int i = 0;
        while (i < 4 * (cnt-1)) {
            cout << "_";
            i++;
        }
    }
    cout << sss << "\n";
    if (cnt > 1) {
        int i = 0;
        while (i < 4 * (cnt-1)) {
            cout << "_";
            i++;
        }
    }
    cout << ssss << "\n";
    cnt++;
    recur(n - 1); 
    if (cnt > 1) {
        int i = 0;
        while (i < 4 * (cnt - 1)) {
            cout << "_";
            i++;
        }
    }
    cnt--;
    cout << "라고 답변하였지." << "\n";
}

int main() {
    int n; cin >> n;
    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." << "\n";
    recur(n);
    cout << "라고 답변하였지." << "\n";
    return 0;
}

문제가 좀 재미있는데, 재귀 호출이 어떻게 이루어지는지 알면 쉽게 풀 수 있음!

하지만 저 문제는 이렇게 푸는게 훨씬 깔끔하단것!

//17478 재귀뭐임?

#include<iostream>
#include<string>
using namespace std;
void str(string st, int cnt) {
    for (int i = 0; i < cnt * 4; i++) cout << "_";
    cout << st << endl;
}
void rec(int n,int cnt) {
    str("\"재귀함수가 뭔가요?\"", cnt);
    if(cnt==n) str("\"재귀함수는 자기 자신을 호출하는 함수라네\"", cnt);
    else {
        str("\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.", cnt);
        str("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.", cnt);
        str("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"", cnt);
        rec(n,cnt + 1);
    }
    str("라고 답변하였지.", cnt);
}
int main() {
    int n; cin >> n;
    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다." << endl;
    rec(n, 0);
    return 0;
}

재귀는 항상 생각해줘야 하는것이 있다.

1. n/2, n/3으로 나뉘어 생각해도 분명 같은 논리로 반복된다.
2. 이차원배열에 뭔가 사분면마다 쪼개진다? -> 재귀함수도 4개로 쪼개지게 만들어야한다! ex)

           int half = n / 2;
       rec(x, y, half,1);
       rec(x, y + half, half,2);
       rec(x + half, y, half,3);
       rec(x + half, y + half, half,4);

   이렇게 말야 ( 차례대로 1,2,3,4사분면) 사분면으로 작아지고 나서 다시 리턴될때 어느 사분면으로 가는지도 생각해주고, 그때의 n은 얼만지도 확인하고,

[SHEWANTSME]

PAIR를 잘 쓰기 위해 사용해야 하는 기법,, pair , vector, map 등등.. 클래스도 다시 봐야하고 아 존나 하기싫다,, 내일 정리해야겟다

[SHEWANTSME]

UPPER BOUND, LOWER BOUND 쩡리

이분탐색은 -> 원하는 값 k를 찾는 과정 LowerBound -> 원하는 값 k 이상이 처음 나오는 위치를 찾는 과정 UpperBound -> 원하는값 k 를 초과한 값이 처음 나오는 위치를 찾는과정

이분탐색에서 조건을 약간 비틀면 나온당!

이분탐색과 마찬가지로 정렬이 되어 있어야 한다!(오름차순)

빡대가리인 나에게 유용한 이미지

STL에서는 #include에 있고

사용 방식은

그냥 코드 구현하면 이렇다.

1. Upperbound

   
   int UpperBound(const vector<int>&arra, int value) { 
   int low = 0;
   int high = arra.size();
   while (low < high) {
       int mid = low + (high + low) / 2;
       if (value >= arra[mid]) low = mid + 1;
       else high = mid;
   }
   return low;
   }

-----------
참고로 배열을 함수 인자로 받을 때 -> 벡터를 받으면 위에처럼 하면 되고 ( 참조형+ 벡터 가변이 아니라면 const)
그냥 일반배열을 하려면 
```c
int ceta(int ia[], int value,int ialength) {
    int low = 0;
    int high = ialength;
} 

이렇게 아예 배열의 사이즈를 인자로 받아버려야 한다. (자바처럼 안됨)

각설하고

2. Lowerbound

int lowerBound(int array[],  int value,int arraylength) {
        int low = 0;
        int high = arraylength;
        while (low < high) {
            int mid = low + (high - low)/2;
            if (value <= array[mid])  high = mid;
            else  low = mid + 1;
        }
        return low;
    }

STL 사용하면

일반 배열
#include <iostream>
#include <algorithm> // 요기 안에 있당
using namespace std;

int main() {

    int arr[6] = { 1,2,3,4,5,6 };
    cout << "lower_bound(6) : " << lower_bound(arr, arr + 6, 6) - arr; 
       // lower_bound(배열, 배열+사이즈, 찾고자하는숫자의 인덱스번호) 에서
// 첫번째 주소 를 가리키는 배열 원소만빼주면 됨 ( 인덱스니까)

    // 결과 -> lower_bound(6) : 5

    return 0;
}

벡터형은 이렇게 하면 됨

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

int main() {

    vector<int> arr = { 1,2,3,4,5,6,6,6 };
    cout << "lower_bound(6) : " << lower_bound(arr.begin(), arr.end(), 6) - arr.begin();

    // 결과 -> lower_bound(6) : 5

    return 0;
}

upperbound도 똑같음

관련 문제 👍 (예) {1,3,5,5,7,8,8,10,10,11,13} 에서 5 이상 11 이하의 숫자가 몇 개인지 구할 때

int main() {

    vector<int> arr = { 1,3,5,5,7,8,8,10,10,11,13 };
    cout << "5 이상 11 이하의 갯수 : " << upper_bound(arr.begin(), arr.end(), 11) - lower_bound(arr.begin(), arr.end(), 5);

    return 0;
}

예) 오름차순 정렬된 자료에서 특정한 숫자가 몇 번 나오는지 탐색하고자 할 때

int main() {

    vector<int> arr = { 1,3,5,5,5,8,8,10,10,11,13 };
    cout << "5의 갯수 : " << upper_bound(arr.begin(), arr.end(), 5) - lower_bound(arr.begin(), arr.end(), 5);

    return 0;
}

출처 : https://chanhuiseok.github.io/posts/algo-55/

새로 정리해둔 이분탐색 내용.. 어렵긴 드럽게 어려운듯

문제가 괴랄하지 않은이상 이런 방식으로 푸는게 효과적이더라구 (근데 예전엔 그냥 while문 돌렸는데 지금은 재귀로 보는게 더 이쁜거같기도?)

//랜선짜르기
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n;
ll k, ans;
ll arr[1000001];
void Binary(ll start, ll end) {
    if (start <= end) {
        ll mid = (start + end) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; i++) {
            cnt += arr[i] / mid;
        }
        if (cnt < k) {
            end = mid - 1;
            Binary(start, end);
        }
        /*
         반비례, 비례관계를 생각해보면 된다. 
         지금 cnt랑 k랑 = 들어가는 위치랑 ans 어디다 써야되냐 때문에 헷갈리는거같은데
         cnt가 k 보다 작은상태라는 뜻은 mid가 큰상태라는 뜻( mid가 나뉘어지는 형태니까)
         분모에 있는 mid가 커지면 cnt는 작아지지 그러니까 
         mid 가 작아져야 지금 cnt가 커지는 상황이자나? mid가 작아지려면 end가 mid-1로 가야되고
         다시 binary를 돌리고,
         만약 cnt>k이면 mid가 작다는 소리임 그래서 mid가 커져야하는데 
         mid 커지려면 start = mid+1로 오면 되고, 여기서 cnt>=k까지 해줘야하는데 그 이유는
         여기서 ans를 둬야 start, end가 뒤바뀌기 직전의 mid값이 답이기 때문이지.
        */
        if(cnt >= k) {
            start = mid + 1;
            ans = mid;
            Binary(start, end);
        }
    }
    else return;
}
int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    Binary(1, 2e9); // 아예 2147483648 넣어야 맞았습니다 뜨던데 ㅇㅅㅇ..
    cout << ans << endl;
    return 0;
}

[SHEWANTSME]

https://github.com/SHEWANTSME/FENDER/issues/4#issuecomment-960454906

--> REREAD!!

ABOUT MAP , set, other STLs

[SHEWANTSME]

Pair 정리

Pair? -> 두개의 자료형을 묶어주는 놈 ( 보통은 구조체를 써야 하지만 몇개 없을때는 pair를 사용한다) -> #include 에 있다 ( 실은 그냥 #include 에도 있으니 그냥 알고리즘을 쓰면 된다)

선언 : pair<자료형, 자료형 > 이름 -> ex) pair<int , string> p;

값 저장 : 이름 = make_pair(변수1, 변수2); -> ex) p = make_pair(3,"fuckyou"); // 위에서 pair을 p라고 선언했으니

값 출력 : cout << 이름.first << 이름.second << endl; -> ex) cout << p.first << p.second << endl;

중첩pair? - > 말 그대로 중첩되게 pair 사용

선언 : pair<int, pair<int, int > > 이름 -> ex) pair<int, pair<int, string>> good;

값 저장 : make_pair( 값, make_pair(값, 값)) ;

근데 선언을 꼭 저렇게 해야 하는건 아니고,,

pair<pair<string, int> , pair<int, double>> whatthe; 이렇게 괴랄하게 할 수도 있음 그러면 whatthe.first.first , whatthe.first.second, whatthe.second.second, whatthe.second.first 도 되는거임

아 그리고 값 저장 할때 make_pair 안써도 됨 -> 그니깐

원래는 이렇게 했자나
int main(){
   pair<int , pair<int, int>> fuck;
   fuck = make_pair( 3,(3,2)); 
}

근데

int main(){
   pair<int , pair<int, int>> fuck;
   fuck = {3,{3,2}}; 이렇게 중괄호 써서 해도 됨 (C++11부터) // 그냥 처음부터    pair<int , pair<int, int>> fuck = {3,{3,2}}; 이래도됨
   cout << fuck.first << fuck. second.first << fuck.second.first<< endl; 이렇게 도 되구
}

---

이번엔 다른 자료형과 섞어서 사용하는 pair을 알아보자.

1. vector -> 실은 이거만 알아도,, ㅋㅋ 어지간하면 다 쓰이기 때문에

   int n;
   cin >>n;
   vector<int>v(n);
   vector<pair<int, int>>p(n);
   for(int i = 0; i<n; i++){
   cin >> v[i];
   p[i] = {v[i],i};// 이게 make_pair안쓰고 쓰는 경우
   }

   번외로, 조금 헷갈렸었던 구문

   vector<int>v[] = {{1},{2},{3}};
   vector<vector<int>>v2= {{1},{2},{3}};
   두개 다 이중 배열이지만 쓰임새가 다르다.
   v.push_back(4);   ->이건 쌉오류임. v는 벡터가아닌 배열이라서 
   미리 정해져있는 배열의 사이즈를 바꿀순 없기때문
   대신에
   v[1].push_back(4); -> 이건 됨. 벡터부분을 바꾸는거니깐
   위에처럼 한다면 v = {{1},{2,4},{3}}이 되겠네
   v2.push_back(4); - > 이건 됨 둘다 벡터니깐

vector<pair<int, pair<int, string>>> what;
    what.push_back({ 3,{3,"apple"} });
    cout << what.front().second.second;
    cout << what.front().second.first;
    cout << what.front().first;

이렇게 쓰는것도 가능하다!

pair<int, int> func(pair<int, int>f1, pair<int, int>f2) {
    int a1 = f1.first*f2.second + f1.second*f2.first;
    int a2 = f1.second * f2.second;
    return { a1,a2 };
}
int main(){
        pair<int, int>p;
    p = func({ 3,4 }, { 7,9 });
    cout << p.first << " " << p.second << endl; // 55 36 나옴 
}

[SHEWANTSME]

와 진짜 안쓴지 오래되었네,, 그동안 백준풀면서 정리를 안해두었더니 그냥 노답상태가 된거같아서 다시 정리가 필요한듯

생성자에 대한 내용

#include <iostream>
using namespace std;

class Fraction {
public:
    int m_numerator; // these things must be initialized
    int m_denominator;
public:
    void print() {
        cout << m_numerator << " / " << m_denominator << endl;
    }
};

// 자 , 원래대로 다시 보자면
class Frac {
private:
    int m_numerator; // = 0; 이렇게 바로 해도 해도 됨
    int m_denominator;// = 1;
public:
    Frac() // this is 생성자 (constructor)
    { 
        m_numerator = 0;
        m_denominator = 1;
        cout << "when does this work?" << endl;
    }
    Frac(const int& num_in, const int & den_in)
    {
        m_numerator = num_in;
        m_denominator = den_in;
        cout << "Frac() constructor 여러개 가능?" << endl;
    }
    Frac(const double &x, const double &y) {
        m_numerator = x + 10;
        m_denominator = y + 100;
    }
    void print() {
        cout << m_numerator << " / " << m_denominator << endl;

    }
};
int main() {

/* if you wanna do like this -> this memebers should be announced as public(which is not what I wanted
    Fraction frac;
    frac.m_numerator = 0;
     frac.m_denominator = 1;
     그리고 항상 이렇게 모든 멤버변수에 이럴수는 없어

    //Fraction frac{ 0,1 };
    // public 인 상태에서 이렇게 uniform initialization 해도 됨
*/
    Frac frac; // 생성자는 선언과 동시에 실행이 되는 형태임.
    // 그래서 Frac의 생성자 안에 있는 whendoesthiswork 가 먼저 실행되짐
    frac.print();
    Frac what(1, 5); // 생성자가 여러개가 가능한듯 보인다.
    what.print();
    Frac hey(3.0, 7.0); // 여러개 되넹 존나신기
    hey.print();

    /*
    when you make no any constructors
    still, there is a constructor(default constructor)
    which looks like this 
    Frac(){} -> 내가 굳이 안써도 있는 애임
    근데 생성자를 하나라도 만들었으면 더이상 default는 없어짐

    */  return 0;
}

#include <iostream>
using namespace std;
class Scnd {
public:
    Scnd() {
        cout << "second class constructor() " << endl;
    }
};
class First {
    // 아무것도 안쓰면 자동 private이고
public: // 근데 생성자를 생성할때 무조건 public 안에 있어야함
    Scnd sec;

    First()
    {
            cout << "first class constructor() " << endl;
            }
};
int main() {
    First fir;
    /*
    class First {
    public: 
       First() {
    cout << "first class constructor() " << endl;
    Scnd sec;
}
};
이럴때만 first가 먼저 출력이고 
Scnd sec가 저 상황일때 제외하고 어디에있던
(public 밖이던 public안에서 First()보다 앞이던 뒤던)
second가 먼저 출력됨
세컨드가 first의 멤버로 들어가 있어서 먼저 초기화 해줘야 하기 떄문
    */
    return 0;
}

#include <iostream>

using namespace std;
class Something {
private:
    int m_i;
    double m_d;
    char m_c;
    int m_arr[10];
public:
    //Something() {
    //  m_i = 1;
    //  m_d = 3.14;
    //  m_c = 'a';
    //  m_arr[0] = 1;
    //}
    Something()
        :m_i(2),/* m_d = 3.14  안됨*/ m_d(3.14), m_c('a'), m_arr{ 1,2,3,4,5,6,7,8,9,10 }{} // 뒤에 {}있어야해!! 생성자니깐
// 암튼 저게 constructor initializer list임
};
struct dele {
private: 
    int x=100 ;
    int y=1000;
public:
    dele()
        : x{ 1 }, y{ 2 }
    {
        cout << "does this work?" << endl;
        x = 7;
        cout << x << " " << y << endl;

    }

};

int main() {
    dele del;
    // 지금 dele의 생성자에 좆도 없는 상황인데 
    //dele del(); 이러면 프로토타입 함수가 호출되지 않았습니다 라고 뜸
    // private 구간에 변수를 초기화 해도 생성자에서 초기화한게 우선이 돼서
    // 7 2 가 찍힘 만약 생성자에서 초기화를 안했으면 private에서 초기화한게 찍히구
    // 생성자 initializer list ( : 쓰는거)로 일빠따 초기화 -> 그다음 생성자 내부에서 초기화 
    /*
    결론 : 
    constructor initializer list
    constructor 내부
    ---- 만약 construtctor 에 초기화목록없다?
    그럼 private에 있는 초기화값 use
    */

    return 0;
}

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

class Student {
private :
    int m_id;
    string m_name;
public:
    Student(const string&name)
        : m_id(0),m_name(name){}

    Student( const int& id_in,const string& name_in)
        : m_id(id_in), m_name(name_in) {} // constructor initializer list
    void print() {
        cout << m_name << " " << endl;
    }
    void init(const int& id_in, const string& name_in) {
        m_id = id_in;
        m_name = name_in;
        // 별도의 초기화 함수 make
    }
};
int main() {
    Student st(0, "jack");
    st.print();

    return 0;
}

#include <iostream>
using namespace std;

class Simple {
private : 
    int m_id;
public:
    Simple(int id) {
        this->setID(id);//화살표 operator는 class , struct가 포인터일때 member selection operator
    //  (*this).setID(id);
        // (*this).setID(id) == this -> setID(id);
        //this->m_id;
        cout << this << endl; // self 주소
    /*  this->getID(); simple안의 함수면 
        cout << this << endl; this를 찍어도 같은주소로 찍힘
        this->Simple::getID();  이거나 그냥 getID()나 같음*/ 
    }
    void setID(int id) { m_id = id; }
    int getID() {
        return m_id;
    }
};
int main() {
    Simple s1(1), s2(2);
    s1.setID(2);
    s2.setID(4);
    /*Simpel s1(1),s2(2) 에서 바로 생성자로 들어가는데(디버깅할때)
    그러면 this 를 통해서 s1,s2의 주소가 찍힘
    */
    cout << &s1 << " " << &s2;

    return 0;
}

#include<iostream>
using namespace std;
class Calc {
private:
    int x;
public:
    Calc(int init_x)
        :x(init_x)
    {} // this is how you init your constructor
    void add(int a) { x+=  a ; }
    void sub(int a) { x -=a ; }
    void multi(int a) { x *= a; }
    void div(int a) { x /= a; }
    void print() {
        cout << x << endl;
    }
};
int main() {
    Calc cal(10);
    cal.add(3);
    cal.multi(3);
    cal.print(); // 이렇게 하든가
    return 0;
}

위의 calc가 밑에처럼 할수도 chaning member function.

#include<iostream>
#include <string>
using namespace std;
class Calc {
private:
    int x;
public:
    Calc(int init_x)
        :x(init_x)
    {} // this is how you init your constructor
    Calc& add(int a) { x += a; return *this; }
    Calc& sub(int a) { x -= a; return *this; }
    Calc& multi(int a) { x *= a; return *this; }
    Calc& div(int a) { x /= a; return *this; }
    void print() {
        cout << x << endl;
    }
};
int main() {
    int  y;
    string x;
    Calc cal(10);
    while (1) {
        cin >> x;
        if (x == "add") {
            cin >> y;
            cal.add(y);
        }
        if (x == "sub") {
            cin >> y;
            cal.sub(y);
        }
        if (x == "multi") {
            cin >> y;
            cal.multi(y);
        }
        if (x == "print") {
            cal.print();
            break;
        }

    }
    //cal.add(10).sub(1).multi(3).print(); 연쇄호출가능
    return 0;
}
이렇게 하면 재밌게 할 수 있당

그니깐 DEC_16.cpp 가 있고, Calculator class 를 담은 calc.cpp도 있고 calc.h도 있음 각각의 역할이 뭐냐면

calc.h에서는

calc클래스의 뼈대만

class Calc{

private :

     int m_val;

public : 

     Calc(int init_val);

     Calc&add(int value);

     Calc&sub(int value);

     Calc&multi(int value);

      void print();

};

이렇게만 써주고

calc.cpp에서는  Calc 클래스의 주요 내용을 담는다!

#include "calc.h"를 해주고

using namespace std;

Calc:: calc(int init_val)

     : m_val(init_val){} // 생성자

Calc& Calc::add(int value){ m_val +=value; return *this;}

이전에 배운 무한히 .붙여서 쓸 수 있는 cal인데

이놈들을 calc.cpp에 넣고 ( 귀찮으면 다 header file에 짱박아둬도됨 실제로 template 관련된거는 그냥 다 header file에 때려박아둠 )

DEC_16.cpp에서는

#include "calc.h"

int main(){

Calc cal(10).add(10).sub(1).multi(3).print();

return 0;

}

이게 다임

#include <iostream>
class Sth {
private :
    int value=0;
public : 
    //int value = 0;
    void setvalue(int invalue) {
        value = invalue;
    }
  int getvalue() const { return value; }
};

int main() {
    const Sth some;
    //some.setvalue(30); sth를 const로 한다는게 내부값을
    //안바꾸려고 그러는건데 왜 바꾸냐고 그니까 오류뜨지
    some.getvalue();
    // some.getvalue()가 되려면 const Sth some; 에서 const를 뺴던가
    // int getvalue(){ return value}에서 getvalue는 값을 바꾸지 않는 함수이다
    //라고 명확히 말할 수있는 키워드 const를 넣어줘야함(c++빡대가리라 말 안하면
    //setvalue처럼 생각하기때문에 써줘야함
    return 0;
}

[SHEWANTSME]

ABOUT MODERN C++

1. 여러개의 RETURN 가능?

#include <iostream>
#include <tuple>
using namespace std;
튜플의 성능이 뭐 문제풀때 그닥이라고는 하지만 일단 내용을 적어보자.

이게 오리지날 형태임!!
tuple<int,int> my_func() {
    return tuple<int, int>(123, 456);
}
int main() {

    tuple<int, int> result = my_func();
    cout << get<0>(result) << " " << get<1>(result) << endl;
    return 0;
}

하지만 달라진점이 뭐냐?

#include <iostream>
#include <tuple>
using namespace std;
 auto my_func() {
    return tuple(123, 456);
    // auto가 아니면 return {{123},{456}}해도 됨 -> 중요 ㅎ
}
int main() {
    auto result = my_func();
    cout << get<0>(result) << " " << get<1>(result) << endl;
    return 0;
}

아니면 아예 이렇게 받아도 됨

#include <iostream>
#include <tuple>
using namespace std;
 auto my_func() {
    return tuple(123, 456,789);
    // auto가 아니면 return {{123},{456}}해도 됨 -> 중요 ㅎ
}
int main() {
        auto[alpha,beta,gamma] = my_func();
        cout << alpha<<" " << beta <<" "<< gamma << endl;
    return 0;
}

2. 함수 포인터에 관한 내용

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/
#include <iostream>
#include <functional> // when do we use this?
#include <vector>
using namespace std;

// let us use the function pointer
bool checkeven(const int & number){
    if(number %2 ==0) return true;
    else return false;
}
bool checkodd(const int &number){
    if(number %2 !=0) return true;
    else return false;
}
typedef bool (*hello)(const int&);
//                     함수type(*함수포인터이름)(함수type의 자료형)
void printNum(vector<int>v , hello checkfunc ){ // function pointer의 형태는 저런식임 
// bool (*checkfunc)(const int&) = checkeven이면 
//main에서 printNum(vec); 이렇게만 하면 default로 checkeven이라서 짝수만찍힘
for(auto &ele : v){
        if(checkfunc(ele) ==true){
            cout <<ele<<" ";
        }
    }cout <<endl;

}
void printN(const vector<int>&v, function<bool(const int&)>hi){
    for(auto &ele : v){
        if(hi(ele) == true)cout << ele;
    }cout << endl;
}
int main(){
    vector<int>vec{1,2,3,4,5,6,7,8,9,10};
    printNum(vec,checkeven);
    printNum(vec,checkodd);
    //       <returntype (parametertype)>
    function<bool(const int&)> fcnptr = checkeven;
    printN(vec,fcnptr);
    fcnptr = checkodd;
    printN(vec,fcnptr);
    return 0;
}

헷갈릴수도 있는데, 자세히 보면

1. 가장 기본적인 함수포인터의 생김새 함수type (*함수포인터이름)(함수 type의 자료형)

말 그대로 함수인 포인터를 다른 함수에 인자로 넘길 수 있음

void printNum(vectorv , ^^^^){}

만약 저 ^^^^자리에 함수 포인터를 넣고싶어 근데 넣고싶은 함수포인터의 자료형이 bool이야 , 그 함수 포인터의 인자가 const int야, 그러면 위의 공식대로 집어 넣으면 됨

bool (JohnKim)(const int) 이러면 됨 (아 참고로 함수포인터의 인자가 참조형이면 참조까지 붙여야함 ) -> 그래서 위의 예제에서는 bool (hello)(const int&)이 된거고

그리고 c++에서 편리한게 뭐냐? -> 길면 typedef 시킬수 있자나 그래서 저놈을 그냥 typedef bool(*hello)(const int&) 를 하면 함수의 인자로 넘길때 void printNum(vector , hello checkfunc) 이러면 된다고

물론 가장 편한건 #include 해서

std::function<bool(const int&)> whatthe = checkeven; 하면 구냥 존나 쉬워진다 이말이지

[SHEWANTSME]

ABOUT LAMBDA FUNCTION. -> 아직 어려우니 내용 추가하고싶음 하쟝

기본 형태 :

[captures] (parameters) -> return type{body}

captures : 콤마로  구분된 캡쳐들이 들어감
parameters : 함수의 인자들이 들어감
  return type : 함수의 반환형
  body : 함수 몸통

 (1) 매개 변수가 없을 때

      []{};  or  [](){};

    (2) 매개 변수가 있을 때

      [](int a){}:

    (3) 매개 변수가 있고 리턴 값이 있을 때

      [](int a)->int { return a; }:

    (4) 즉시 실행 방법

      - Lambda함수 생성 후 마지막에 ()를 사용하여 호출합니다.

      [](){}(**요 부분에서 즉시 실행 가능하게 호출 ㄱㄴ**);

#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;
void goodbye(const string &s) {
    cout << "Goodbye" << s << endl;
}
class Object {
public : 
    void hello(const string &s) {
        cout << "Hello " << s << endl;
    }
};
/*
[captures] (parameters) -> return type{body}

captures : 콤마로  구분된 캡쳐들이 들어감
parameters : 함수의 인자들이 들어감
  return type : 함수의 반환형
  body : 함수 몸통
*/
int main() {
    auto func = [](const int& i) -> void {cout << "hello world!" << endl; };
    // 굳이 auto func = 을 안붙여도 사용가능한 lambda
    //[](const int& i) -> void {cout << "hello world!" << endl; }(1234);
    func(123);

    {
        string name = "john";
        [&]() {cout << name << endl; }();
    }
    vector<int>v;
    v.push_back(1);
    v.push_back(2);

    auto func2 = [](int val) { cout << val << endl; };
    //auto func2 = [](int val)-> void { cout << val << endl; }; void일땐 안써도됨

    for_each(v.begin(), v.end(), func2);
    // for_each(v.begin(), v.end() , [](int val){cout << val << endl; }); 가능
    cout << []() -> int {return 1; }() << endl;

    function<void(int)> func3 = func2;
    func3(123);
    //#include <functional> 써서
    // function<함수타입(함수type의인자)> ~~ 하면 됨
    function<void()> func4 = bind(func3, 456); // func3가 int만 받고
    // func4가 bind로만 묶여있으니까 func4자체는 void임
    func4();
    {
        Object instance;
        auto f = bind(&Object::hello, &instance, std::placeholders::_1);
        f(string("World"));
        // can be used as f("World");
        auto f2 = bind(&goodbye, std::placeholders::_1);
        f2(string("World"));
    }

    return 0;
}
/*
hello world!
john
1
2
1
123
456
Hello World
GoodbyeWorld
*/

BIND랑 PLACEHOLDERS에 대한 내용!!

std::bind(함수 주소, 함수인자1, 함수인자2, 함수인자3, ...)

함수인자에 초기값을 설정한수 있고

bind로 생성한 함수의 인자로 받을 것이면

std::placeholders::_1, std::placeholders::_2, std::placeholders::_3, ... 등을 새로운 함수 인자와 맵핑 시킬수있다.

void Func( int iA, float fB, bool bC );

라는 3개의 인자를 가지는 함수가있다면

auto funcA = std::bind( Func, 10, 2.0f, true );

funcA();

다음과 같이 단일 함수로 사용가능하고

그중 float 인자값을 새로운 함수의 인자로 받으려면

auto funcB = std::bind( Func, 10, std::placeholders::_1, true );

funcB( 2.0f );

처음인자는 float 두번쩨 인자는 int를 받고 싶으면

auto funcC = std::bind( Func, std::placeholders::_2, std::placeholders::_1, true );

funcC( 2.0f, 10 );

3번쩨 인자에 bool 값을 받고 싶으면

auto funcD = std::bind( Func, std::placeholders::_2, std::placeholders::_1, std::placeholders::_3 );

funcD( 2.0f, 10, true );

[SHEWANTSME]

SET, MAP 관련 정리.. 어우 존나 귀차낭

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <tuple>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#define endl "\n"

using namespace std;

int main() {
    string s = "music is my life";
    cout << s << endl;
    cout << s.substr(3, 4) << endl; -> 뭐가 찍히겠니? ic i 가 나오겠징
    reverse(s.begin(), s.end()); // reserve랑 다른거임! reserve는 벡터크기제한할때 쓰는거고
// 얘는 말그대로 리버스
    cout << s << endl;

그냥 map 들은 이렇게 ㄱㄴ함
    multimap<int, int>mp1;
    map<int, int>mp2;
    unordered_map<int, int>mp3;
    unordered_multimap<int, int>mp4;
물론 set도 마찬가지임

    pair<int, int>p = { 3,4 }; // 한방선언 much easier
    pair<int, pair<int, int>>pp = { 6,{7,8} }; // tuple보다 이게 더 낫다고 생각함. 더 쓰기 쉽달까
    tuple<int, int, int> tup = { 1,2,3 };
    //p = { 3,4 };
    //tup = { 1,2,3 };

    cout << pp.first << " " << pp.second.first << " " << pp.second.second << endl; // 이렇게 하면 되니깐

    cout << p.first <<" "<< p.second << endl;
    cout << std::get<2>(tup) << get<1>(tup) ;
 // tuple일때 tie안쓰면 이렇게 get써야함

    int a, b, c;
    tie(a, b) = p;
    cout << a << " " << b << endl; // pair일때 굳이 tie를 써야 하나 라는 생각이 듬
    tie(a, b, c) = tup;
    cout << a << " " << b << " " << c << endl;
    // tuple일때는 tie를 하는게 더 효과적이라고 생각함.

    cout << sizeof(int) << endl;
    int arr[8] = { 0, };
    cout << sizeof(arr) << endl;
    //fill(arr+3 , arr+sizeof())
    return 0;
}

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>

#define endl "\n"
using namespace std;

int main() {
    map<int, int>m;
    m.insert({ 5,10 });
    m.insert(pair<int, int>(8, 2)); // 위에처럼 하는게 편함
    m[5]++;// 이거는 배열의 인덱스가 아니고, map의 key에 해당하는
    // value를 ++한다는 얘기임
//  map<int, int>m{ {5,2},{9,3},{10,32} }; 선언과 동시에 초기화할때 이런식으로 구현 가능
    map<int, int>::iterator iter;
    //이터레이터 쓸때는 이런식으로 선언해줌
//--------------------------------------------------//

    // map, set은 처음 값 넣을때 insert로 넣지만,
    // 값을 바꿀때는 emplace같은거보단 그냥 바꿔주는게 편함
    m[8] = 4; // 물론 중복허용되는 multimap에선 안됨 ㅎ

    for (iter = m.begin(); iter != m.end(); iter++) {
        cout << (*iter).first << " " << iter->second << endl;
    } // 정렬 되어서 나옴

    for (auto &ele : m) {
        cout << ele.first << " " << ele.second+1 << endl;
    } // same result above

    unordered_map<int, string> k;
  //    k.insert({ 1,"data" }, { 0,"kata" }); 이렇게는 안됨 insert는 하나씩
// 선언과 동시에 초기화할때는 가능
    unordered_map<int, string>kk{ {1,"data"}, {3,"kata"} , {0,"mata"} };
    k.insert({ 1,"data" });
    k.insert({ 3,"pp" });

unordered_map<int, string>::iterator ii; // map의 성격에 따라 이터레이터 make
for (ii = k.begin(); ii != k.end(); ii++) {
    cout << (*ii).first <<" "<< ii->second << endl;
    }

multimap<int, string>mm;
multimap<int, string>::iterator iti;
// 아까도 말했지만 multimap은 중복허용이고 정렬됨

mm.insert({ 32,"kk" });
mm.insert({ 33,"kk2" });
for (iti = mm.begin(); iti != mm.end(); iti++) {
    cout << (*iti).first << " " << iti->second << endl;
}

mm.erase(33);
for(auto &ele : mm){
    cout << ele.first << " " << ele.second << endl;
}
    return 0;
}

아 참고로 map이랑 set은 정렬할때 기준이 있음

1. Key에 의한 정렬

map과 set은 자동으로 정렬된다. 이 map과 set의 정렬 기준은 선언할 때 결정할 수 있다. (디폴트는 Key를 기준으로한 오름차순 정렬)

map<int, int> m1;   // Key 오름차순 정렬
map<int, int, greater<int>()> m2; // Key 내림차순 정렬
struct cmp {
    bool operator()(const int& a, const int& b) const {
        return a < b;
    }
};

// ...
map<int, int, cmp> m3;  // Key 를 커스텀 비교 함수로 정렬 (priority_queue처럼 () 연산자 오버로드로 사용)

2. value에 의한 정렬

map은 Key를 기준으로 정렬하기 때문에 Value로 정렬하려면 map과 모든 원소들을 pair를 원소로 가지는 Vector로 복사한 후 이 Veter를 Value (second)기준으로 정렬하면 된다.

bool compare(pair<int, int> a, pair<int, int> b)
{
    return a.second > b.second; // Value로 정렬
}

//...
map<int, int> count;

//...

vector<pair<int, int>> sortByValue(count.begin(), count.end()); // count map을 vector sortByBalue에 복사
sort(sortByValue.begin(), sortByValue.end(), compare); // Value로 정렬

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>

#define endl "\n"
using namespace std;
int main() {
    unordered_map<string, int>um;
    um.insert({ "test1" ,9 });
    um.insert(make_pair("test2", 2));
    um.insert(pair<string, int>("test3", 5));
    um["test4"] = 7;
    for (auto &ele : um) {
        cout << ele.first << " : " << ele.second << endl;
    }
    auto search = um.find("test4");
    if (search == um.end()) {
        cout << "not found" << endl;
    }
    else {
        cout << "found " << search->first << " : " << (*search).second << endl;
    }
    um["test1"]++; // value가 int니까 ++가능

    //map<string, string>q;
    //q.insert({ "alpha" , "beta" });
    //q["alpha"]++;  보다시피 안되는 짓임

    cout << um["test1"] << endl;
    cout << "um's size" << um.size() << endl;
    um.erase("test1");
    cout << um.size() << endl;

    // set 정리!!
    set<string, int>st;
    set<pair<string, int>>stt;
    // st.insert({ "tes1" , 1 }); -> 절대 안되는짓임! pair로 먼저 묶어서 선언한게 아닌 이상, 이러면 안됨
        왜냐하면 set은 원래 원소로 key 하나만 저장하기 때문임!

    stt.insert(pair<string, int>("tes5", 3)); //st.insert로는 안됨 pair로 안묶어놨기 때문임
    stt.insert(make_pair("tes2", 2)); // 얘도 마찬가지. st.insert로는 안됨
    //st.insert({ "tes3" , 23 });
    //cout << st.size() << " st.size" << endl;
    cout << stt.size() << "stt.size" << endl;

    return 0;
}

다시 하나의 예제를 보쟈면

#include <iostream>
#include<set>
#include <algorithm>
#define endl "\n"
using namespace std;

int main() {
    multiset<int>s; // 원래 set은 이런것이얌
    s.insert(12);
    s.insert(10);
    s.insert(2);
    s.insert(10);
    s.insert(90);
    s.insert(85);
    s.insert(45);
    cout << "multiset elements after sort" << endl;
   이렇게 auto를 써서 iterator써도 되고

    for (auto it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }cout << endl;

       아까처럼 따로 multiset에 대한 iterator를 만들어도 됨

    multiset<int>::iterator ite;
    for (ite = s.begin(); ite != s.end(); ite++) {
        cout << (*ite) << endl; // map때 처럼 '->' 이건 안됨! 원소가 하나니깐 오직 pointer만 가능!
    }

    auto it1 = s.find(10);
    auto it2 = s.find(90);

    // elements from 10 ~90전까지 지워짐
      90 은 안 지워진다 이말이야!

    s.erase(it1, it2);
    cout << "multiset elements after sort" << endl;

    for (auto &ele : s) {
        cout << ele << " ";
    }
    s.erase(s.begin());
    for (auto&ele : s) cout << ele << endl;
    return 0;
}

[SHEWANTSME]

분할정복

https://blog.kakaocdn.net/dn/bzykxw/btq5YpGGRoa/jcf1LIViMnKoh9xmbOogBK/img.gif

위의 이미지들을 보면 병합정렬이 어떻게 진행되는지 알 수 있다.

분할 정복은 dp 랑 비슷하지만 다른 개념이다.

비슷한점 : 분할 정복과 동적 프로그래밍 은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다.

다른 점 : 1. 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복 이 일어나면 동적 프로그래밍 을 쓴다는 것

2. 분할 정복은 TOP-DOWN만 가능 DP 는 BOTTOM-UP, TOP-DOWN다 됨

예를들면 :> 병합 정렬을 수행 시에 작은 하위 문제로 쪼개지지만 중복하여 하위 문제가 발생하지 않는다. 무슨 말이냐면, 분할된 부분 부분은 모두 독립적이고, 동일한 부분을 중복하지 않는다 -> 그래서 분할정복을 사용한다.

피보나치 수열은 -> Fn = Fn-1 + Fn-2 이잖아 이렇게 n이 어떤 수던 , 그 하위 수 를 구하는 부분은 중복이 된다. 위와같이 점화식으로 나타낼 수 있으면 십중팔구는 DP이다. (즉, n=5일 때, n-1은 4이고, n-2는 3인데, 3을 구하기 위해선 n-2가 1인 경우까지 하위 문제로 내려가야 하쟈낭)

--> 참고로 피보나치는

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll memo[100]; // for memoization
ll fibo(int n) {
    if (n < 3) { 
        memo[n] = 1;
        return memo[n]; 
    }
    else if (memo[n] > 0)return memo[n]; // memo배열의 값이 0보다 크면 그냥 이걸 리턴!
        // 이부분이 중요하징
    else {
        //memo[n] = memo[n - 1] + memo[n - 2]; // 이렇게 하지말고
        memo[n] = fibo(n - 1) + fibo(n - 2); // 이렇게 해야지
        return memo[n];
    }
    //else return fibo(n - 1) + fibo(n - 2);
}
int main() {
    cout<<fibo(10);
    return 0;
}

----
f(10) -> f(9) -> f(8) -> f(7) -> f(6) -> f(5) -> f(4) -> f(3) ->f(2)=1
                                                            ->f(1) = 1
n=4로 리턴되서 f(3)호출-> elseif문 들어가서 2 리턴
 f(2)호출 -> elseif문 들어가서 1 리턴
이런식으로 쭉 되는거임!
----

백트래킹

그냥 말그대로 완탐 + 가지치기 이다.

가지를 어떻게 치느냐에 따라 알고리즘의 속도 차이가 갈리게 된다.

1. promising 하지 않아 -> 이전 단계로 back -> next 자식으로 ㄱㄱ

완탐 -> 말 그대로 싹다 모든 경우 탐색 ( 재귀를 쓰거나 무식하게 for 오지게 돌려도 됨)

[SHEWANTSME]

About 재귀

예전에도 정리 해뒀지만, 여전히 사고하는 방식이 까다로운건 여전하다.

하노이의 탑을 다시 생각해보자.

Very well-known이라서 "이런 개꿀딱 문제도 못푸는놈이 있단말야? " 할게 아니고

처음에 어떻게 재귀가 돌아가는지를 보면 상당한 난이도를 자랑한다.

일단 일반항 구하는건 개껌이니까 패스하고

문제를 보니

백준 11729 하노이 문제

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll poww(int a, int b) {
    if (b == 1) return a;
    else if (b % 2 == 0) {
        return poww(a, b / 2)*poww(a, b / 2);
    }
    else return poww(a, b - 1)*a;
}

void move_hanoi(int from, int to, int n) {
    cout << from << " " << to << endl;
}
void Sum_hanoi(int from, int to,int sum_number) {
    if (sum_number == 1) {
        move_hanoi(from, to, sum_number);
        return;
    }
    Sum_hanoi(from,6-from-to,sum_number-1);
    move_hanoi(from,to, sum_number);
    Sum_hanoi(6-from-to, to, sum_number - 1);
}

int main() {
    int n; cin >> n;
    cout << poww(2, n) - 1 << endl;
    Sum_hanoi(1,3, n);
    return 0;
}

하나씩 뜯어보면,

ll poww(int a, int b) {
    if (b == 1) return a;
    else if (b % 2 == 0) {
        return poww(a, b / 2)*poww(a, b / 2);
    }
    else return poww(a, b - 1)*a;
}

이건 뭐 그냥 pow 체크하는 놈인데 예전 곱셈문제 에서도 이러한 분할정복이 쓰였었다. a^b을 구하는데 b=1이면 그냥 a 를 리턴하면되고,
짝수면, poww반띵을 리턴하면되고 홀수면 poww(a,b-1)*a 를 리턴하면 되는 아주 생각하면 할수록 이걸 왜 생각 못했지 ? 라는 생각이 물씬 든다.

void move_hanoi(int from, int to, int n) {
    cout << from << " " << to << endl;
}

move_hanoi 함수다. 그냥 출력용 함수임

void Sum_hanoi(int from, int to,int sum_number) {
    if (sum_number == 1) {
        move_hanoi(from, to, sum_number);
        return;
    }
    Sum_hanoi(from,6-from-to,sum_number-1);
    move_hanoi(from,to, sum_number);
    Sum_hanoi(6-from-to, to, sum_number - 1);
}

가장 중요한 sum_hanoi 함수다. 처음에 어떻게 구현해야 하는지 굉장히 막막했다. 그래서 힌트를 들어봤는데

1. n-1번째까지의 hanoi덩어리를 2번째 자리로 옮긴다.
2. 1번째 자리에 있는 젤 밑의 타일을 3번째 자리로 옮긴다.
3. 2번째 자리에 있던 hanoi덩어리를 3번째 자리로 옮긴다.

적어보면 당연한 얘기지만 막상 구현할때는
sum_hanoi(int left, int mid, int right , int num) 이렇게 해야되나 아니면 다른 방법이 있나 계속 생각했었다.

근데 최종 출력을 보니까 옮겨지기전 위치, 옮긴 후 위치만 출력하면 되어서 굳이 mid가 필요 없겠구나 싶었다.

그래서 Sum_hanoi(int from , int to , int num) 이렇게 두었다.

최종적으로 구하고 시픈건 Sum_hanoi(1,3,num)이니까 (만약 n ==3이면) SH(1,3,3) -> SH(1,2,2) -> SH(1,3,1) 이 되어야 1->3으로 되는건데,,

저 중간에 값이 커지는 상황을 어떻게 설정해야하나,, 고민을 많이 했다.

결론은 6-from - to를 하면 from , to에 따른 나머지 하나의 숫자가 자동적으로 결정이 되어서 풀기 쉬워졌다.

num이 줄어들고, 재귀를 빠져나오면 n도 다시 원상복구되기 때문에 로직이 수행될 수 있다!

1.  n-1개 원판을 기둥1 에서 기둥 2로 옮긴다.
2. n번째 원판을 기둥 1에서 기둥 3 으로 옮긴다.
3. n-1개 원판을 기둥 2에서 기둥 3 으로 옮긴다.

이걸 젤 중요하게 생각한 후, from, to를 어떻게 잘 조절할수 있을까? 를 생각하면 된다.

int main() {
    int n; cin >> n;
    cout << poww(2, n) - 1 << endl; // 이거를 (1<<n) -1 해도 됨 비트연산으로
    Sum_hanoi(1,3, n);
    return 0;
}

메인함수는 존나 간단한데, 2^n승 구할때만!!

(1<<n) = 2^n 을 쓰는게 훨씬 편하다! (빠르기도 하고)

암튼 뭐 그게 다임. ㅎ

재귀적 사고!

-> ex)

void func(int n){
   if(n==0) return;
   cout << n<<endl;
   func(n-1);
}

절차적 사고 : func(3) -> '3' -> func(2) -> '2' -> func(1) -> '1' -> func(0) 끝

귀납적 사고 : 1. func(1)은 1을 출력한다.

2. 만약 func(k)가 k , k-1, k-2 ... 1을 출력하면 func(k+1) 은 k+1 , k , k-1 ,.... 1을 출력한다. 둘다 참이므로, func(3)은 3,2,1을 출력함.

---

[SHEWANTSME]

        int cur = 3;
    for (int nxt : {cur - 1, cur + 1, 2 * cur}) {
        cout << nxt << endl;
    } // 2 4 6나옴!!! 기억해두자

i%2 ==0 (짝수)
I%2 !=0 (홀수)
i&1==0 (짝수)
i&1 !=0 (홀수)  //이게 홀수 ex ) 13 & 1 -> 1101 & 1 = 1 -> 1 
1<<2 (2의제곱)
1<<3(2의 세제곱)
1<<4(2의 4승)

[SHEWANTSME]

정렬 정리

잡다한 O(N^2)은 집어 치우고

1. MERGE SORT

이놈이다.

생각해보면 간단하다.

1. 배열을 반띵으로 쪼갠다.
2. 쪼개져있는 반띵을 다시 반띵으로 쪼갠다.
3. 반복해서 쪼갠다. 다만 크기가 1일때는 멈춰줘야한다.-> 크기가 1이면 그 자체로 정렬된거니까

이제 그만 쪼개고 합친다.

배열을 쪼갤때, -> O(N) 배열을 합칠때 -> O(NlgN) 따라서 병합정렬은 -.> O(NlgN)이다.

암튼 정리해둔 내용을 올리면 이렇다

참고로 빈칸은 이런거임

#include <bits/stdc++.h>
using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};
int tmp[1000001]; // merge 함수에서 리스트 2개를 합친 결과를 임시로 저장하고 있을 변수

// mid = (st+en)/2라고 할 때 arr[st:mid], arr[mid:en]은 이미 정렬이 되어있는 상태일 때 arr[st:mid]와 arr[mid:en]을 합친다.
void merge(int st, int en){
  int mid = (st+en)/2;
  int lidx = st; // arr[st:mid]에서 값을 보기 위해 사용하는 index
  int ridx = mid; // arr[mid:en]에서 값을 보기 위해 사용하는 index
  for(int i = st; i < en; i++){
    if(ridx == en) tmp[i] = arr[lidx++];
    else if(lidx == mid) tmp[i] = arr[ridx++];
    else if(arr[lidx] <= arr[ridx]) tmp[i] = arr[lidx++];
    else tmp[i] = arr[ridx++];
  }
  for(int i = st; i < en; i++) arr[i] = tmp[i]; // tmp에 임시저장해둔 값을 a로 다시 옮김
 이 윗줄이 중요한데, 애초에 merge는 각각이 정렬된 상태에서 하는건데
윗작업(tmp를 arr로 옮겨주는 작업)을 안하면 말짱 도루묵임
}

// a[st:en]을 정렬하고 싶다.
void merge_sort(int st, int en){
  if(en == st+1) return; // 리스트의 길이가 1인 경우
  int mid = (st+en)/2;
  merge_sort(st, mid); // arr[st:mid]을 정렬한다.
  merge_sort(mid, en); // arr[mid:en]을 정렬한다.
  merge(st, en); // arr[st:mid]와 arr[mid:en]을 합친다.
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  merge_sort(0, n);
  for(int i = 0; i < n; i++) cout << arr[i] << ' '; // -53 3 12 15 16 22 23 25 46 357
}

이렇게 우선 순위가 같은 원소가(21살이 여러명이라서 21살중엔 랜덤하게 나올 수 있음) 여러 개일 땐 정렬한 결과가 유일하지 않을 수 있습니다. 그런데 그 중에서 우선 순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬이 Stable Sort입니다. -> MERGE SORT는 STABLE함!

-->머지 소트는 Stable Sort인데 이 성질을 만족시키려면 앞에서 본 것 처럼 앞 리스트에서 현재 보는 원소와 뒤 리스트에서 현재 보는 원소의 우선 순위가 같을 때 앞 리스트의 원소를 먼저 보내줘야 합니다. 이 부분은 우리가 코드로 구현할 때 자연스럽게 처리를 했습니다.

2. Quick sort

#include <bits/stdc++.h>
using namespace std;

int n = 10;
int arr[1000001] = {15, 25, 22, 357, 16, 23, -53, 12, 46, 3};

void quick_sort(int st, int en) { // arr[st to en-1]을 정렬할 예정
  if(en <= st+1) return; // 수열의 길이가 1 이하이면 함수 종료.(base condition)
  int pivot = arr[st]; // 제일 앞의 것을 pivot으로 잡는다. 임의의 값을 잡고 arr[st]와 swap해도 상관없음.
  int l = st+1; // 포인터 l
  int r = en-1; // 포인터 r
  while(1){
    while(l <= r && arr[l] <= pivot) l++;
    while(l <= r && arr[r] >= pivot) r--;
    if(l > r) break; // l과 r이 역전되는 그 즉시 탈출
    swap(arr[l], arr[r]);
  }
  swap(arr[st], arr[r]);// break 탈출하면 맨앞놈(피벗)이랑 r의 인덱스의 arr값과 swap한다
  quick_sort(st, r);// swap을 했으니 정렬된 r위치의 arr값빼고 그 앞을 quick재귀
  quick_sort(r+1, en); // 그 뒤 재귀
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  quick_sort(0, n);
  for(int i = 0; i < n; i++) cout << arr[i] << ' ';
}

Mergesort보다 훨씬 쉽게 구현 가능하다. 시간복잡도는 O(N^2) 도 나올수 있다.. (이미 정렬된 상태의 배열에서는)

이렇게 구현을 해낸 것 까지는 좋은데 퀵 소트의 시간복잡도는 얼마일지 고민해봅시다. 일단 퀵 소트의 과정을 풀어헤쳐보면 그림과 같습니다. 맨 처음 pivot은 6이고 6을 기준으로 양쪽이 나뉩니다. 양쪽에서 따로 따로 pivot을 제자리로 보내고, 이렇게 계속 반복합니다.

pivot을 제자리로 보내는 시간복잡도는 그 리스트의 크기에 비례하니 각 단계마다 O(N)이 필요하다고 생각할 수 있습니다. 첫 번째 줄이 O(N)인건 자명하고 두 번째 줄을 보면 왼쪽 리스트는 4에 비례하고 오른쪽 리스트는 3에 비례하니 합치면 대략 N에 비례합니다. 이런 식으로 그 단계에서 pivot을 제자리로 보내야 하는 리스트들의 길이의 합은 N이어서 각 단계마다 O(N)이 필요하다고 생각할 수 있습니다. 그러면 pivot이 매번 완벽하게 중앙에 위치해서 리스트를 균등하게 둘로 쪼갠다면 단계의 개수는 머지 소트때와 같이 lg N이 될거고 이 경우에는 퀵 소트의 시간복잡도가 O(NlgN)입니다.

물론 늘 pivot이 중앙에 위치하는 이상적인 상황이 생기지는 않겠지만 pivot이 매번 어느 정도로만 잘 자리잡는다면 시간복잡도는 여전히 O(NlgN)입니다. 예를 들어 pivot이 매번 리스트를 1대 99의 배율로 쪼개더라도 시간복잡도는 O(NlgN)이란걸 수학적으로 보일 수 있습니다. 또 앞에서 말한 cache hit rate이 높다는 점 덕분에 퀵 소트는 속도가 굉장히 빠릅니다.

그런데 퀵 소트에는 아주 치명적인 단점이 있습니다. 1, 2, 3, 4, 5, 6, 7, 8을 퀵 소트로 정렬하면 시간복잡도가 얼마일지 생각해봅시다. 안타깝게도 매번 선택되는 pivot은 중앙에 가는 대신 제일 왼쪽에 위치하게 되고 그로 인해 단계는 lg N개가 아닌 N개가 됩니다. 그리고 시간복잡도를 계산하면 O(N2)입니다. 이 경우에서 볼 수 있듯이 퀵 소트는 평균적으로 O(NlgN)이지만 최악의 경우 O(N2)입니다. 그리고 단순히 제일 왼쪽의 값을 pivot으로 선택해보면 지금처럼 리스트가 오름차순이거나 내림차순일 때에 바로 O(N2)이 됩니다.

[SHEWANTSME]

STL SORT 주의사항

비교 함수에서 가장 실수하기 좋은게 있는데, a가 b의 앞에 와야할 때만 true를 반환해야 하니 두 값이 같을 때 혹은 우선순위가 같을 때에는 반드시 false를 반환해야 합니다!

그리구

함수의 인자로 STL이나 구조체 객체를 실어서 보내면 값의 복사가 일어나는데 지금 이 비교 함수를 생각해보면 굳이 복사라는 불필요한 연산을 추가로 하면서 시간을 잡아먹을 필요가 없습니다. 그래서 복사를 하는 대신 reference를 보내는게 더 바람직합니다.

[SHEWANTSME]

N이 커서 O(N^2)은 통과가 안될 상황이고 원소의 대소 관계가 필요한데 삽입 혹은 삭제가 빈번하다면 이진 검색 트리 (set multiset, map multimap)가 유용하게 쓰일 수 있습니다.

[SHEWANTSME]

Heap and BST 차이

이게 차이점!

Heap -> for the Max , Min (fast) BST -> (set,multiset, map,multimap) for lots of push and pops..

생긴것의 차이 heap

BST

** about heap

참고로 pq가 set보다 2~4배 빠름.

How to make HEAP(최소 힙)

#include <bits/stdc++.h>
using namespace std;

int heap[100005];
int sz = 0; // heap에 들어있는 원소의 수

void push(int x){
  heap[++sz] = x;
  int idx = sz;
  while(idx != 1){
    int par = idx/2;
    if(heap[par] <= heap[idx]) break;
    swap(heap[par], heap[idx]);
    idx = par;
  }
}

int top(){
  return heap[1];
}

void pop(){
  heap[1] = heap[sz--];
  int idx = 1;
  // 왼쪽 자식의 인덱스(=2*idx)가 size보다 크면 idx는 리프
  while(2*idx <= sz){
    int lc = 2*idx, rc = 2*idx+1; // 왼쪽 자식, 오른쪽 자식
    int min_child = lc; // 두 자식 중 작은 인덱스를 담을 예정
    if(rc <= sz && heap[rc] < heap[lc])
      min_child = rc;
    if(heap[idx] <= heap[min_child]) break;
    swap(heap[idx],heap[min_child]);
    idx = min_child;
  }  
}

void test(){
  push(10); push(2); push(5); push(9); // {10, 2, 5, 9}
  cout << top() << '\n'; // 2
  pop(); // {10, 5, 9}
  pop(); // {10, 9}
  cout << top() << '\n'; // 9
  push(5); push(15); // {10, 9, 5, 15}
  cout << top() << '\n'; // 5
  pop(); // {10, 9, 15}
  cout << top() << '\n'; // 9
}

int main(void){
  test();
}

MAX HEAP

#include <iostream>

#define ROOT_NODE 1 // 계산의 편의를 위해 1번부터 데이터 추가

using namespace std;

int arrIndex = 1;   // 계산의 편의를 위해 인덱스도 1번부터 시작
int heap[100001] = { 0, };  // 1번 노드부터 시작

// heap에 데이터 추가
/*
    최대힙에 데이터를 추가하는 방법
    1. 가장 마지막 인덱스에 데이터 추가
    2. 부모값과 비교하여 부모가 값이 더 작을경우 값 교제
    3. 부모값과 교체 후, 2번조건을 만족하지 않을때까지 반복
*/
void push(int num)
{
    heap[arrIndex] = num;   // 마지막 자리에 데이터 추가
    int cur = arrIndex, parent;     // 현재 위치 cur -> 마지막 인덱스
    arrIndex++; // 데이터 추가하였으니 index 증가
    while (cur != ROOT_NODE)
    {
        parent = cur / 2;   // 부모 인덱스는 현재 인덱스를 2로 나누어주면 됨
        if (heap[parent] < heap[cur])   // 자식이 더 클경우 값 교체
        {
            int temp = heap[parent];
            heap[parent] = heap[cur];
            heap[cur] = temp;
        }
        else
        {
            break;
        }

        cur = parent;
    }
}

int pop()
{
    if (arrIndex == 1) return 0;

    arrIndex--;
    int top = heap[ROOT_NODE];
    heap[ROOT_NODE] = heap[arrIndex];   // 마지막 원소를 0번째에 추가
    heap[arrIndex] = 0; // 마지막 원소 0으로 초기화

    int cur = ROOT_NODE;
    int child = cur * 2;
    while (child < arrIndex)
    {
        if (child < arrIndex && heap[child] < heap[child + 1])
            child++;

        if (heap[child] > heap[cur])
        {
            int temp = heap[child];
            heap[child] = heap[cur];
            heap[cur] = temp;
        }
        else
        {
            break;
        }
        cur = child;
        child = cur * 2;
    }

    return top;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, num;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> num;
        if (num == 0)
        {
            // pop
            cout << pop() << "\n";
        }
        else
        {
            // push
            push(num);
        }
    }
    return 0;
}

[SHEWANTSME]

-N의 범위가 500인 경우 : 시간복잡도가 O(N^3) 인 알고리즘을 설계 해야한다.

-N의 범위가 2,000인 경우 : 시간복잡도가 O(N^2) 인 알고리즘을 설계 해야한다.

-N의 범위가 100,000인 경우 : 시간복잡도가 O(NlogN) 인 알고리즘을 설계 해야한다.

-N의 범위가 10,000,000인 경우 : 시간복잡도가 O(N)인 알고리즘을 설계 해야한다.

-int a[1000] : 4KB

-int a[1000000] : 4MB

-int a[2000][2000] : 16MB

---- Think of memory!

[SHEWANTSME]

최단거리 GRAPH 경로 알고리즘

--> union find 관련 그림

--> 최단 그래프 경로 알고리즘 정리해둠

union find 구현

// 초기화
for (int i=1 ; i<=v ; i++){
   parent[i] = i;
}
// Find함수
int find(int a){ // a가 속한 트리의 루트를 반환함
    if( a ==parent[a]) return a; // 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
    //각 노드의 부모를 찾아 올라간다.
    else parent[a] = find(parent[a]); 
    return parent[a];
}

// union 함수 -> a와 b가 속한 트리를 하나로 합친다.
void Union(int a, int b){
    // 각 원소가 속한 트리의 루트노드를 찾는다.
    int rootA = find(a);
    int rootB = find(b);
    // 루트가 동일하지 않다면 서로 다른 두개의 트리를 합친다.
    if(rootA != rootB) parent[rootA] = b;
    // 같은 트리면 종료
    else return;

}

Kruskal 구현

vector<int> p(10005,-1);

int find(int x){
  if(p[x] < 0) return x;
  return p[x] = find(p[x]);
}

bool is_diff_group(int u, int v){
  u = find(u); v = find(v);
  if(u == v) return 0;
  if(p[u] == p[v]) p[u]--;
  if(p[u] < p[v]) p[v] = u;
  else p[u] = v;
  return 1;
}

int v,e;
tuple <int, int , int> edge[100004];
sort( edge , edge+ e);
int cnt = 0;
for(int i = 0; i< e ; i++){
    int a,b,cost;
    tie(a,b,cost) = edge[i];
    if( !is_diff_group(a , b)) continue;
    else cnt ++;
    if(cnt  == v-1) break;
}

Prim 구현

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int v, e;
vector<pair<int,int>> adj[10005]; // {비용, 정점 번호}
bool chk[10005]; // chk[i] : i번째 정점이 최소 신장 트리에 속해있는가? 

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> v >> e;
  for(int i = 0; i < e; i++){
    int a, b, cost;
    cin >> a >> b >> cost;
    adj[a].push_back({cost, b});
    adj[b].push_back({cost, a});
  }

  int cnt = 0; // 현재 선택된 간선의 수
  int ans = 0;
  // tuple<int,int,int> : {비용, 정점 1, 정점 2}
  priority_queue< tuple<int,int,int>,
                  vector<tuple<int,int,int>>,
                  greater<tuple<int,int,int>> > pq;

  chk[1] = 1;
  for(auto nxt : adj[1])
    pq.push({nxt.X, 1, nxt.Y});

  while(cnt < v - 1){
    int cost, a, b;
    tie(cost, a, b) = pq.top(); pq.pop();
    if(chk[b]) continue;
    ans += cost;
    chk[b] = 1;
    cnt++;
    for(auto nxt : adj[b]){
      if(!chk[nxt.Y])
        pq.push({nxt.X, b, nxt.Y});
    }
  }
  cout << ans;
}

벨만포드, 다익, 플로이드 구현 밑에다 할것!