[코딩테스트] 자주 사용하는 함수(조합/순열/중복조합/중복순열) c++

1. binary_search

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

int main() {
    vector < int > v = {1, 5, 2};
    sort(v.begin(), v.end());    //벡터 정렬 무조건 해야함 !!
    
    for (int i = 1; i <= 5; i++) {
        if (binary_search(v.begin(), v.end(), i))
            cout << i << "는 벡터에 존재" << "\n";
        else
            cout << i << "를 찾을 수 없음" << "\n";
    }
 
    return 0;
}

1-1. lower_bound

범위 내에서 value보다 크거나 같은 것(작지 않은) 중 첫번째 요소를 가리키는 iterator 반환, -v.begin()하면 idx 반환

1-2. upper_bound

범위 내에서 value보다 큰 첫번째 요소를 가리키는 iterator 반환, -v.begin()하면 idx 반환

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

int x = 2;
vector<int> v = {1, 1, 2, 2, 2, 2, 3};

int solution(int x) {
    int low = lower_bound(v.begin(), v.end(), x) - v.begin(); //iter 반환 - 주소 = 해당 idx
    int upper = upper_bound(v.begin(), v.end(), x) - v.begin();
    cout << low <<", "<<upper << endl;
    return upper - low;
}

int main() {
    vector<int>::iterator it;
    it = lower_bound(v.begin(), v.end(), x);
    cout << *it << endl; //원소 반환
    it = upper_bound(v.begin(), v.end(), x);
    cout << *it << endl; //원소 반환

    int result = solution(x); //2와 같은 것 몇개인지 구하기
    cout << result << endl;

    return 0;
}

 

2. getline : 띄어쓰기 부분까지 문자열을 저장

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

int main() { //입력 받은거 그대로 출력
    string s;

    while (getline(cin, s)) {
        cout << s << "\n";
    }

    return 0;
}

 

3. stringstream : 공백으로 문자열 자를 때 사용(문자열로부터 입력받는 것)

#include <iostream>
#include <vector>
#include <sstream> //해줘야함
using namespace std;

int main() {
    string s = "abc def ghi jkl mn opqr stu vw xyz";
    vector<string> v;
    stringstream ss(s);
    string s1;

    while (ss >> s1) {
        v.push_back(s1);
    }
    for (auto &i: v)
        cout << i << endl;
}

 

4. 올림/내림/반올림

#include <cmath>

1) 올림

result = ceil(4.2) 

=> result = 5.0

 

2)내림

result = floor(4.2)

=> result = 4.0

 

3) 반올림

round()

 

5. char to string

char i = 'c';
string tmp_string(1, i); // "c" 문자열

 

6. string 비교

==

 

7. find

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

int main() {
    string data = "딸기";
    vector<string> name_list = {"딸기", "바나나", "사과"};

    if (find(name_list.begin(), name_list.end(), data) == name_list.end())
        cout << "없음";
    else
        cout << "있음";
}

 

8. 문자열 자르기

문자열.substr(시작 위치, 길이)

 

9. next_permutation <algorithm>

1) 순열

vector<int> v = {1, 2, 3};
sort(v.begin(), v.end()); // 오름차순

1-1. 배열 사이즈자리 만큼의 순열

do {
    for (auto &it : v)
        cout << it << " ";
    cout << "\n";
} while(next_permutation(v.begin(), v.end()));

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

 

1-2. m자리 수의 순열 (+m부터 reverse 후 next_permutation) - N개 중 M(2)개 뽑아 순열

do {
    for (int i = 0; i < 2; i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
    reverse(v.begin() + 2, v.end()); // 중복제거
} while (next_permutation(v.begin(), v.end()));

1 2 
1 3 
2 1 
2 3 
3 1 
3 2

 

1-3. 모든자리수의 순열 (reverse 후 next_permutation)

int r = 0, size = v.size(); // 자릿수 cnt
while(r <= size) {
    do {
        for (int i = 0; i < r; i++)
            cout << v[i] << " ";
        cout << "\n";
        reverse(v.begin() + r, v.end()); // 중복제거
    } while(next_permutation(v.begin(), v.end()));
    r++;
}

1 
2 
3 
1 2 
1 3 
2 1 
2 3 
3 1 
3 2 
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

 

2) 조합

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> n = {1, 2, 3};
    vector<int> ind = {1, 1, 0}; //3중 2개를 뽑기 위한 0과 1을 저장한 벡터

    sort(ind.begin(), ind.end());

    do {
        for (int i = 0; i < ind.size(); i++) {
            if (ind[i] == 1) {
                cout << n[i] << " ";
            }
        }
        cout << "\n";
    } while (next_permutation(ind.begin(), ind.end()));

    return 0;
}

2 3 
1 3 
1 2 

 

2-2. 모든자리수의 조합 (reverse 후 next_permutation)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> arr = {1, 2, 3};

    int r = 1;

    while (r <= arr.size()) {
        vector<int> ind(arr.size());
        for (int i = 0; i < r; i++) {
            ind[i] = 1;
        }
        sort(ind.begin(), ind.end());
        do {
            for (int i = 0; i < ind.size(); i++) {
                if (ind[i] == 1) {
                    cout << arr[i] << " ";
                }
            }
            cout << "\n";
        } while (next_permutation(ind.begin(), ind.end()));
        r++;
    }
    return 0;
}

3 
2 
1 
2 3 
1 3 
1 2 
1 2 3

 

3) 중복순열

#include <iostream>

using namespace std;
int N, M;
int arr[8]; //완성된 순열이 저장되고 갱신됨

void backTracking(int cnt){
    if(cnt == M){ // M개 다 골랐다면
        for(int i = 0; i < M; i++){
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    
    for(int i = 1; i <= N; i++){ //배열을 만들어서 계속 값을 바꿈
        arr[cnt] = i;
        backTracking(cnt+1);
    }
}

int main(){
    cin >> N >> M;
    backTracking(0);
    
    return 0;
}

1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 1 
3 2 
3 3 

 

4) 중복조합

#include <iostream>

using namespace std;
int N, M;
int arr[8];

void backTracking(int cnt, int num){
    if(cnt == M){
        //출력
        for(int i =0; i < M; i++){
            cout << arr[i] << " ";
        }
        cout << '\n';
        return;
    }

    for(int i = num; i <= N; i++){
        arr[cnt] = i;
        backTracking(cnt + 1, i); // num, i 차이
    }

}

int main(){
    cin >> N >> M;
    backTracking(0, 1);
    return 0;
}

1 1 
1 2 
1 3 
2 2 
2 3 
3 3