1. 순열

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

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

sort(numbers.begin(), numbers.end());
do {
	...
	...
} while (next_permutation(arr+0, arr+배열 크기))

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

주의: next_permutation(arr+0, arr+배열 크기) 은

• int 배열이면 숫자 크기기준 오름차순으로
• char배열이나 std::string은 아스키코드기준 오름차순으로 다음 순열을 찾는다
• 항상 sort()로 오름차순 정렬 후에 next_permutation(arr+0, arr+배열 크기) 을 사용해야한다.

추가로, next_permutation(arr+0, arr+배열 크기) 은 배열에 중복된 값이 있더라도 중복되는 순열은 무시하고 알아서 중복을 제외한 순열로만 원본을 조작한다

사전순 순열의 동작 방식은 아래와 같다.

2. 조합

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

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

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

대부분의 연산이 if (b.size() == n) {...} 에서 발생한다.
해당 부분이 메인 로직이기때문에 시간복잡도는 내부로직 고려 x시 O(nCr) 이다. (시간 복잡도는 정확한 연산 시간을 추정하는 개념이 아니라, 대강 연산 시간을 추정하는 개념이다)

호출은

combi(-1,{}); 

로 하면 된다.

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

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. 중복 요소 제거

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

unique는 중복 원소를 "뒤로 밀어내고"
-> "중복 제거된 마지막 다음 위치(iterator)"를 반환한다.

주의 : unique()의 동작 특성상 sort() 후에 unique()를 사용해야한다.

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];
    }
}

이렇게 a[i] 입력받을떄 psum[i] 에 누적시킨다.

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

이때, 주의할 것은 psum과 배열 모두 인덱스를 1부터 사용한다.