1. 순열

(1) next_permuatation(arr+0,arr+베열 크기)

오름차순 순열로 원본을 조작

do {
	...
	...
} while (next_permutation(arr+0, arr+배열 크기))

모든 순열을 탐색하니, 시간복잡도는 내부로직 고려 x시 O(n!) 이다.

2. 조합

(1) combi() <--- 4개 이상 뽑는 경우

사용자가 직접 정의해서 구현한다

void combi(int start, vector<int> b) {
	if (b.size() == n) {
    	...
        return;
    }
    for (int i = start + 1; i<n;i++) { //참고로 b의 내용물은 인덱스이다.
    	b.push_back(i);
        combi(i, b);
        b.pop_back();
    
    }
}

대부분의 연산이 if (b.size() == n) {...} 에서 발생한다. 해당 부분이 메인 로직이고, 시간복잡도는
내부로직 고려 x시 O(nCr) 이다.

(2) 반복문 <--- 3개 이하로 뽑는 경우

반복문으로 구현되면, 반복문을 사용하는 것이 좋다

int n = 5;
int k = 3;
int a[5] = {1,2,3,4,5};
int main() {
	for(int i=0;i<n;i++) {
    	for(int j=i+1;j<n;j++) {
        	for(int k=j+1;k<n;k++) {
            	...				//로직 (i,j,k는 인덱스임)
                ...				//로직
            }
}

시간복잡도는 내부 로직 고려 X시 O(nCr) 이다.

3. split()

내가 원하는 구분자(delimiter)로 파싱하는 함수

vector<string> split(string const &input, string delimiter) {
	auto start = 0;
    auto end = input.find(delimiter);
    vector<string> result;
    while(end != string::npos) {
    	result.push_back(input.substr(start, end-start));
        start = end + delimiter.size();
        end = input.find(delimiter, start);
    }
    result.push_back(input.substr(start));
    return result;
}

4. 중복 요소 제거

sort() 후에 unique()를 사용한다.

vector<int> s = {4,3,3,5,1,2,3};
sort(s.begin(), s.end());
s.erase(unique(s2.begin(), s2.end()), s2.end());

unique()로 원본을 오름차순 정렬 후 중복 보장 x인 첫번째 이터레이터 반환한다.
이후, 해당 이터레이터를 이용해 중복 보장 x인 부분을 erase를 통해 지워버린다.

5. 구간합

psum[] 로 구현한다

(1) psum[]

int a [100004], psum[100004], n, m;
int main() {
	cin >> n >> m;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
        psum[i] = psum[i-1] + a[i];
    }
}

이렇게하면 psum[i] 에는 a[1]+a[2]+...+a[i] 가 저장된다.
(누적합이 저장된다는 뜻)