[5-L] 시간복잡도 계산 코멘트 요청

작성한 질문수 23

1

안녕하세요 진살라님 ㅎㅎ

최대치로 가정하고 계산한다면, 20C10이 되는데요.

>> 네 맞습니다.

선생님은 비트마스킹을 써야 한다는 것을 조합과 어떻게 구분하셨는지 코멘트 주시면 감사하겠습니다..!

>> 뽑는데 순서가 상관이 없죠? ㅎㅎ 그래서 조합입니다. / 비트마스킹은 이러한 조합을 하나의 수로 나타낼 수 있는 트릭같은 거라고 생각하시면 되요. 비트마스킹으로 하셔도 되고 조합으로 하셔도 됩니다. 단지 저는 비트마스킹이 편리해서 비트마스킹으로 했습니다.

앞에 aass0930님 질문글을 읽어보아도 제가 생각했던 로직에 대한 답을 찾을 수 없어서 이렇게 추가적으로 질문 드렸습니다!

>>

조합으로 설정하고 하셨다는거 아닌가요?? 조합으로 하셔도 됩니다. 조금만 더 응용하면 되요.

한번 조합 COMBI 재귀를 이용해 풀어볼까요?

원래 조합 combi는 vector로 뽑는데 이거는 뽑아져있는거 외의 안 뽑아져있는 것도 배열에다가 집어넣어야 하기 때문에 visited 배열을 만들면 좀 더 쉽게 할 수 있어요.

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;
int s[24][24], ret = INF, n; 
int k = 10, visited[24];
vector<int> v; 
int go(vector<int>& a, vector<int> & b){
	pair<int, int> ret;  
	for(int i = 0; i < n / 2; i++){
		for(int j = 0; j < n / 2; j++){
			if(i == j)continue;
			ret.first += s[a[i]][a[j]];
			ret.second += s[b[i]][b[j]]; 
		}
	}
	return abs(ret.first - ret.second);
} 
void combi(int start, vector<int> b){ 
    if(b.size() == k){ 
        vector<int> start, link; 
        for(int i = 0; i < n; i++){
        	if(visited[i])start.push_back(i);
        	else link.push_back(i);
		} 
		ret = min(ret, go(start, link)); 
        return;
    }
    for(int i = start + 1; i < n; i++){ 
        visited[i] = 1;
        b.push_back(i);
        combi(i, b);
        visited[i] = 0; 
        b.pop_back();
    }
    return;
}  

int main() { 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> s[i][j];
        }
    } 
    k = n / 2;
	vector<int> v;  
    combi(-1, v);  
    cout << ret << '\n';
} 

이렇게 말이죠.

(visited 배열 안 만들면 vector<int> b를 기반으로 계속해서 find를 걸어서 i가 들어가 있나 안 들어가있는 확인해야 하는 로직이 +로 들거든요 find는 O(n)시간복잡도라 visited배열을 만들어서 시간복잡도를 O(1)로 한것도 눈여겨 봐주세요)

추가 질문) 경우의 수로 접근한다면, 스타트 팀에 인원을 먼저 배정한다고 했을 때 20 * 19 의 경우의 수가 나오는건가요?

>> 음.. 아니죠. 20C10 곱하기 20 곱하기 20이 됩니다. 10개 뽑고 뽑을 때마다 맵 전체 탐색이니까요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.