간단한 조합 문제이다.
중첩 for문으로 구현해도되고, 재귀로 구현해도된다.
1. 중첩 for문
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N,M,input;
int ret = 0;
cin >> N >> M;
if(M > 200000) {
cout << 0;
exit(0);
}
for(int i=0;i<N;i++) { //O(N)
cin >> input;
v.push_back(input);
}
for(int i=0;i<N;i++) { //O(N(N-1)/2) 약 1억
for(int j=i+1;j<N;j++) {
if(v[i]+v[j] == M) ret++;
}
}
cout << ret;
return 0;
}우선, 이 문제를 풀때 사실 처음에 중첩 for문으로 구현하면 시간복잡도가 O(N^2) 인데, 시간 초가계산해보면 2억(시간제한 2초)을 넘겨서 불가능할 것이라고 생각했다.
근데 잘 생각해보니 상수항 날리기전의 시간복잡도가 O((N)(N-1)/2) 라서 대략 1억번 정도가 나오게되고 -> 풀이하면 시간 초과를 회피할 수 있게된다.
또한 위의 코드에
if(M > 200000) {
cout << 0;
exit(0);
}가 있는데, 애초에 문제 조건상 불가능한 값이 입력으로 들어오면 조기에 코드를 종료 시킴으로써 제한 시간을 초과할 위험을 줄일 수 있다.
2. 재귀
#include <bits/stdc++.h>
using namespace std;
int ret, N,M, input;
vector<int> v,v1;
void comb(int start, vector<int>& v2) { // O(N(N-1)/2) 약 1억
if((int)v2.size()==2) {
if(v2[0]+v2[1]==M) ret++;
return;
}
for(int i=start+1;i<N;i++) {
v2.push_back(v[i]);
comb(i, v2);
v2.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> M;
for(int i=0;i<N; i++) {//O(N)
cin >> input;
v.push_back(input);
}
comb(-1,v1);
cout << ret;
return 0;
}재귀로 조합 구현시에는 인자로 참조형을 전달해줘야 시간복잡도를 낮출 수 있다.
(매개변수를 참조형으로 선언하지않으면 재귀 호출시마다 벡터가 복사 되어서 매개 변수에 들어간다. 여기서 시간적 비용이 발생한다)
중첩for문으로 구현했을때와 시간 복잡도는 O(N^2)으로 동일하나, 매개변수를 참조형으로 선언하면 복사 비용이 SAVE 되므로 시간 초과를 피할 수 있고, 그렇지 않으면 벡터 복사 비용으로 시간 초과가 발생한다.
3. 오답노트
(1) 연산량은 상수항 날리기전을 기준으로 생각한다.
for(int i=0;i<N;i++) { //O(N(N-1)/2) 약 1억
for(int j=i+1;j<N;j++) {
if(v[i]+v[j] == M) ret++;
}
}이 코드의 시간 복잡도는
상수항 날리기 전 : O(N(N-1)/2) -> 약 1억 -> 시간 복잡도 문제 없음
상수항 날린 후 : O(N^2) 약 2억 -> 시간 복잡도 문제 있음
과 같은 결과가 나오게된다.
따라서 연산량은 항상 상수항 날리기전을 기준으로 생각하는것이 좋다
(2) 재귀 조합 코드 블럭 제대로 외우기
//nCk 구하는 경우이고 n과 k가 전역 변수로 선언되어있는 경우
void combi(int idx, vector<int>& v) {
if(v.size()==k) {
조합 만들어졌을때 처리 로직
return;
}
for(int i=idx+1; i<n; i++) {
v.push_back(i);
combi(i, v);
v.pop_back();
}
}
combi(-1, v1); //호출하는 부분. 참조 형이니 리터럴말고 변수를 넘겨줘야함 시간 복잡도는 O(nC2*메인로직 시간복잡도) 로 보면 된다.
특히 매개변수를 참조형으로 선언해야 시간복잡도를 줄일 수 있음을 잊지말자.
또한, 중요한것은 combi() 내부 벡터에는 값이 아니라 인덱스가 들어간다.
(3) 문제 조건 기준으로 조기 종료 시키기
문제 풀이에
if(M > 200000) {
cout << 0;
exit(0);
}가 있는데, 애초에 문제 조건상 불가능한 값이 입력으로 들어오면 조기에 코드를 종료 시킴으로써 제한 시간을 초과할 위험을 줄일 수 있다.
(4) 사고 과정⭐⭐⭐⭐⭐⭐⭐⭐⭐
코태는 틀리더라도, 좌절하지않고 다른 방법으로 빠르게 시도해보는 능력이 매우 매우 중요하다
어? O(n^2)? 시간복잡도가 너무 크네 -> 다른 방법 있을까? -> 다른 방법 있으면 다른 방법하고, 안떠오르면 기존 방법 그대로 ㄱㄱ -> 안되면 또 다른 방법 찾아보고, 시간 복잡도 최적화 방법 생각해보고..
(5) 조합 문제 - 중첩 반복문이 재귀보다 더 빠르다
조합 문제는 중첩 for문 혹은 재귀 함수로 풀이한다.
보통 같은 시간복잡도라도 중첩 반복문으로 푸는 것이 재귀보다 빠르다.
