인프런 커뮤니티 질문&답변
작성한 질문수
시간복잡도가 궁금합니다.
해결된 질문
작성
·
405
0
해당 코드에서는 말 4개와 주사위 수 10개를 완탐해서 구했는데요, 이는 4^10으로 약 100만의 시간 복잡도를 갖으리라 생각했습니다.
#include <bits/stdc++.h>
using namespace std;
int a=0;
void func(vector<int> v, int n)
{
++a;
if (n == 10)
{
for (auto i : v)
cout << i << ",";
cout << endl;
return;
}
for (int i=0; i<4; ++i)
{
v.push_back(i);
func(v, n+1);
v.pop_back();
}
}
int main()
{
vector<int> v;
func(v, 0);
cout << a;
}이 코드로 a를 확인해보면 func은 약 139만회 정도 호출됐다고 나옵니다.
강사님이 완전탐색을 하겠다고 한 이유는 if (n==10)인 시점에서 (로직을 진행할 경우의 수가 완성됨) 호출할 함수가 최대 4^10의 횟수를 가지니까 1억 미만이므로 괜찮다고 생각하신건가요?
여기까진 저도 납득했습니다. 조합을 만드는 함수의 호출도 139만 정도에, 로직을 실행할 함수도 105만정도니까 가능하겠구나~ 라고 생각했습니다.
하지만 만약 말의 개수가 4개가 아니라 5개였다면? 조합을 만드는 함수는 1220만번 호출되고 로직을 실행하는 함수는 5^10회, 약 976만회가 호출됩니다. 합하면 약 2천만인데 이런 경우에도 완탐으로 실행해도 괜찮을까요??
말의 개수가 4일때의 실행시간은 약 200ms대를 기록했지만 말이 5개가 되면 실행시간은 약 1800ms까지 꽤나 큰 차이를 보였습니다. 애초에 함수 호출이 139만에서 1220만회로 약 10배 늘었으니 당연하겠지만.. 보시면 func는 단순히 조합을 만드는 함수이고 로직을 실행하는 함수가 없는데도 시간이 꽤나 걸립니다.
글이 두서가 없어서 죄송합니다;; 궁금한 점을 정리하자면 다음과 같습니다.
조합을 만드는 함수와 로직을 실행하는 함수 중, 로직을 실행하는 함수의 호출순서로 시간복잡도를 계산하면 될까요? (로직실행 함수가 조합만드는 함수보다 무거우니까)
아니면 두 함수의 호출 횟수를 더해서 생각하는게 맞을까요?
참고로 저는 처음에 말이 5갠줄알고, 조합을 만드는데도 시간이 많이 걸리길래 완탐이 아닌 중복조합을 다 제거하고 실행시켰습니다.. 하지만 실행시간은 강사님 코드의 실행시간과 동일하게 나왔네요.. (이틀동안 고민했는데 허탈합니다ㅠ)
답변 1
0
안녕하세요 Maruche님 ㅎㅎ
강사님이 완전탐색을 하겠다고 한 이유는 if (n==10)인 시점에서 (로직을 진행할 경우의 수가 완성됨) 호출할 함수가 최대 4^10의 횟수를 가지니까 1억 미만이므로 괜찮다고 생각하신건가요?
>> 네 맞습니다.
하지만 만약 말의 개수가 4개가 아니라 5개였다면? 조합을 만드는 함수는 1220만번 호출되고 로직을 실행하는 함수는 5^10회, 약 976만회가 호출됩니다. 합하면 약 2천만인데 이런 경우에도 완탐으로 실행해도 괜찮을까요??
>> 네 5개라면 좀.. 힘들 것같긴 합니다. 다만, 그렇게밖에 풀 수 없다라고 생각이 든다면 그렇게 해야합니다. 즉, 2천만인데 ->> 너무 크지 않나? ->> 생각해봐도 완탐밖에 답이 음슴... -> 완탐 드가자~
이렇게 하시면 됩니다.
중요한 것은 이러한 생각의 흐름입니다.
천만이상이다? 1억이상이다? 아 좀 안될 것 같은데? 하고 고민하는 것과
그냥 냅다 완탐으로 드가는 것은 하늘과 땅차이입니다.
보통의 경우 완탐으로 시간복잡도가 빡셈 -> DP 나 그리디 또는 그냥 완탐
이렇게 되곤 합니다.
완탐 -> DP or 그리디라고 생각하셨을 때
상태값을 담기가 어렵거나 암만 생각해봐도 중복되는 경우의 수가 없고, 그리디로 하기에는 명제자체가 안떠오를 때는 보통은 완탐으로 풀린다고 보시면 됩니다.
조합을 만드는 함수와 로직을 실행하는 함수 중, 로직을 실행하는 함수의 호출순서로 시간복잡도를 계산하면 될까요? (로직실행 함수가 조합만드는 함수보다 무거우니까)`
>> 음.. 둘 다 고려하긴 해야 합니다. 두개가 독립적이라면 그 중 큰걸 기반으로 시간복잡도를 잡아야 합니다.
보통의 문제는 파스칼의 삼각형을 만들라고 하지는 않습니다. 즉, nC1, nC2, nC3 .. 이런식의 모든 조합을 만들어서 푸는 문제는 드뭅니다. 제 기억상은.. 없는 것 같습니다.
따라서 만약 저렇게 파스칼의 삼각형을 만들어야 할까? 라고 생각이 된다면 재고해보시는 것이 좋습니다.
또한 완탐으로 하거나 모든 경우의 수 자체를 조합으로 만들어서 하는 것은 시간복잡도상 사실 차이가 그렇게 많지는 않습니다. 어차피 모든 경우의 수를 고려하는 것이기 때문이죠.
아니면 두 함수의 호출 횟수를 더해서 생각하는게 맞을까요?
>> 더한다는 것은 독립적인데요. 독립적이라면 둘 중 최대치만 하시면 됩니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 Maruche님 ㅎㅎ
음...
예를 들어
oox, ooo ... 이런식으로 어떤 idx에서 o또는 x를 골라야 하는 모든 경우의 수를 생각하면.
2^3이 되겠죠?
이는 사실 x를 고르는 걸 기반으로.
nC1, nC2, nC3으로 나타낼 수도 있습니다.
nC1 = oox, oxo, xoo
nC2 = oxx, xox, xxo
nC3 = xxx
이렇게 말이죠.
그리고... nC0를 통해 결국 모든 경우의 수를 구하게 됩니다. 2^3이 되는 것이죠.
이걸 단순히 재귀함수로
go{
go()
go()
}
이렇게 완탐 - 재귀로 할 수도 있습니다.
물론 함수호출 등에서 차이가 있을수도 있지만, 경우의 수 자체가 2 ^ 3으로 동일하기 때문에 조합이나 완탐 - 재귀가 별 차이가 없다는 의미입니다.
시간복잡도는 경우의수 * 해당 경우의 수의 메인로직으로 결정이 됩니다.
경우의 수 자체가 동일하고 해당 경우의 수마다 해야 하는 메인로직이 동일하다면 거의 같은 시간복잡도가 되는 것이죠.
다만, 함수호출은 되도록 줄이는게 좋습니다. 예를 들어 1 에서 1000까지의 수를 더할 때 for문과 재귀함수로 그걸 구현한 것은 시간차이가 많이 납니다. 시간복잡도는 O(N)으로 동일하지만 함수호출은 코스트이기 때문에 그걸 기반으로 시간초과가 날 수도 있기 때문에 Maruche님이 하신 것처럼 함수호출을 줄이려는 노력은 훌륭합니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
네 말씀해주신 부분 맞습니다.
o,x를 총 3개 뽑아 순열을 만드는 건 2^3=8가지가 존재하죠. 하지만 제가 말씀드리고 싶은건, 여기서 o와 x는 구분되는 인자일뿐 oox와 xxo는 동일하다는 가정하에 로직을 짠겁니다. 즉 예로 들어주신 nC1과 nC2는 중복입니다.
주사위 수가 1,2,3,4이렇게 4개가 있을 때 말 a,b가 있다면 aaaa와 bbbb는 동일하며 aabb와 bbaa는 동일한 결과를 낳을겁니다. 즉 중복된 경우를 전부 탐색하게 되기에
1) aaaa부터 bbbb까지 전부 탐색한다 -> 완탐 2^4=16의 경우의 수
2) 4C0+4C1+(4C2)/2까지만 탐색한다 -> 중복없는 완탐 1+4+3=8의 경우의 수
이렇게 2배의 차이가 날거라고 생각합니다. 이건 말이 2개니까 2!만큼의 배수 차이가 난 것이고 본 문제처럼 4개의 말이라면, 4! 배수만큼의 차이가 더 날 것 같네요.
논리상으론 제가 맞았다고 생각하는데요, 강사님 코드 역시 이를 생각한 부분이 있는데 제가 놓친건지 아니면 1)번 예제처럼 구현하신게 맞고, 보통의 문제는 1)의 풀이로도 충분하다. 인지 궁금합니다.
안녕하세요 Maruche님 ㅎㅎ
네 수강생님 말씀이 맞습니다. nCr = nCn - r 특징을 이용해서 중복되는 부분을 제거한다면 좀 더 효율성이 증대될 것 같습니다. 다만 보통의 문제의 경우 제코드 - 1)의 풀이로도 충분합니다.
이렇게 2배의 차이가 날거라고 생각합니다. 이건 말이 2개니까 2!만큼의 배수 차이가 난 것이고 본 문제처럼 4개의 말이라면, 4! 배수만큼의 차이가 더 날 것 같네요.
>> 혹시 이부분 왜 4!인지 설명가능할까요?
예를 들어
상태값이 2개가 아니라 3개라면 3! 만큼 차이가 난다는 말씀이시죠?
간단한 예제를 만들어봤는데요.
n = 3으로 가정하고..
3^3 에서 중복되는 부분을 제거하게 되면 10이 되는데 이는 3!을 나누는 것과는 달라서요. 어떻게 3!이 나온건지 설명가능할까요?
#include <bits/stdc++.h>
using namespace std;
string a = "abc";
vector<string> v;
int main() {
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
for(int k = 0; k < 3; k++){
string ret = "";
ret += a[i];
ret += a[j];
ret += a[k];
sort(ret.begin(), ret.end());
v.push_back(ret);
}
}
}
sort(v.begin(), v.end());
cout << v.size() << "\n";
for(string a : v) cout << a << "\n";
v.erase(unique(v.begin(),v.end()),v.end());
cout << v.size() << "\n";
for(string a : v) cout << a << "\n";
return 0;
}
만약 2개의 상태값을 가진다면 / 2는 맞습니다.
#include <bits/stdc++.h>
using namespace std;
string a = "ab";
vector<string> v;
int main() {
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < 2; k++){
string ret = "";
ret += a[i];
ret += a[j];
ret += a[k];
sort(ret.begin(), ret.end());
v.push_back(ret);
}
}
}
sort(v.begin(), v.end());
cout << v.size() << "\n";
for(string a : v) cout << a << "\n";
v.erase(unique(v.begin(),v.end()),v.end());
cout << v.size() << "\n";
for(string a : v) cout << a << "\n";
return 0;
}
unique로 처리해도 문제가 생깁니다. 해당 코드를 실행할 경우 10가지 경우가 나오는데 이 역시 중복을 제거한 코드가 아닙니다. aaa, bbb, ccc 등 중복이 존재하며 3가지 말로 3자리를 채우는 문제의 해답은 총 5가지 입니다.
하지만 저 역시 n^m의 전체 경우의 수를 최적화 할 경우 1/n!를 곱한 결과와 같다는 것 또한 맞지 않습니다. 애초에 n^m은 n의 곱으로만 이루어진 수인데, 일반적으로 n!로 약분이 될 수 없겠죠.
그럼 위의 5가지 경우부터 짚고 넘어가겠습니다.
제 로직은 쭉 두가지 스텝으로 이뤄졌습니다. 첫 째는 말의 개수 구하기, 두번째는 말의 조합으로 순열 구하기. (후술하겠지만 두번째 스텝에서도 중복이 존재할 것 같습니다.)
말을 1개 쓰는 경우 : (0,0,3) -> 3C3 으로 1가지
말을 2개 쓰는 경우 : (0,1,2) -> 3C1 으로 3가지
말을 3개 쓰는 경우 : (1,1,1) -> 3C1 * 2C1 * 1C1 / 3! 으로 1가지
말을 3개 쓰는 경우는 abc, bca, cab 등.. 원래라면 6가지가 존재하겠지만, 3가지 말이 모두 같은 수를 갖고 있기에 3!으로 나눠주고 경우는 1가지가 됩니다. 이에 저는 이를 생각해서 대충 n! 정도의 배수를 갖겠구나 라고 생각했습니다. (무척 러프하게 생각했죠) 그리고 이게 제 로직에도 중복이 존재하는 원인이 됩니다.
제 코드에 대입한다면 말 3개를 쓰는 경우 (a,b,c)의 배열을 넘겨 next_permutation으로 정렬시키고 값을 비교합니다. 그럼 6가지의 모든 경우를 계산하겠죠. next_permutation으로는 동일 개수를 가진 말의 중복된 경우를 제거할 수 없다는 걸 깨달았습니다. (제 코드가 그렇게 빠르지 않았던, 혹은 2번 스텝의 함수 호출이 생각보다 잦던 이유는 찾았네요.)
나아가서, 이 예시는 일반화하여 설명하기에 적절하진 않습니다. 왜냐면 말의 개수도 좌석의 개수도 매우 작아서 말을 몇개를 쓰던 조합이 1가지 밖에 나오지 않습니다. 기존 문제로 돌아와 생각해보자면 4개의 말을 10개의 좌석에 배치하는 문제이고 첫 번째 스텝은 역시 말을 몇개 사용하는지로 시작합니다.
여기서 보면, 이전 예제와는 다르게 2개의 말을 사용하더라도 5가지의 경우가 존재합니다. 그리고 이들은 각각 다른 경우의 수를 갖죠. 그리고 보시면 "같은 수를 갖는 경우"가 빈번함을 볼 수 있습니다. 그리고 이 때마다 중복된 수의 개수 팩토리얼 만큼 나눠줘야 중복이 제거됨을 볼 수 있죠.
4개의 말을 쓰는 (1,1,1,7)의 경우를 보면 3개의 말이 동일한 하나의 말을 사용하는 것을 볼 수 있는데, 두가지 식으로 설명가능합니다.
10C1 * 9C1 * 8C1 / 3! * 7C7
혹은 10C7
이 둘의 결과는 120으로 동일합니다. 그리고 이 예제에는 최대 3개의 말이 중복된 수를 가질 수 있습니다. 10은 4의 약수가 아니기 때문이죠. 그렇기에 4!만큼의 차이가 날 것이란건 옳지 않았고 특정 경우에서는 4!만큼의 중복이 발생할 수 있었다..고 결론 짓는게 맞는 것 같습니다.
그럼 결국 4^10보다 얼마나 중복을 줄였냐? 를 따져보자면
4만회정도 나오네요. 100만에서 4만이면 약 25배니까 4!이랑 얼핏 비슷하기도 한 것 같습니다. 물론 이것도 우연일 수 있고 계산에서 실수가 있었을 수도 있었지만요..
이걸 일반화하거나 코드로 옮길 수 있을지는 모르겠습니다. 일반화할 수 있을만한 건덕지가 보이지는 않네요.. 특히나 n!로 나누는 부분은 어떻게 코드로 구현할지 어지럽습니다..ㅋㅋ
ㅎㅎ 제가 Maruche님을 통해 많이 배웁니다. ㅎㅎ
정말 열심히 연구하셨네요.
n!로 나눈다는 말씀 이해했습니다.
저도 Maruche님이 말씀하신 조합에 대해서 생각해보고 일반화에 대해 생각해보다가...
저도 문득 든 생각인데 DP로 해당 경우의 수를 계산할 수 있지 않을까? 라는 생각인데요.
어차피 어떤 인덱스에서 그 이전에 말이 똑같은지 아니면 다른지만 체크하면 되지 않을까? 생각이 드네요. 그렇게 따지면 처음의 경우의 수는 5개고.. 그 다음에는 10개(주사위의 경우의 수)가 되는 것이죠.
하지만 여기서 주사위의 경우의 수가 정해져있고 우리가 구하는 것은 어차피 최대값이기 때문에
5 * 10 ... 이 아니라
1 * 2 ... 가 되지 않을까 싶습니다.
예를 들어 n이 2개라면.
ab
aa
이렇게 2가지의 경우의 수가 나오는 것이죠.
그 다음 3번째 턴의 경우
aba
abb
또는
aab
aaa
이렇게 되는 것이죠.
이렇게 되면 총 경우의 수는 4가 됩니다.
즉, 모든 경우의 수는 n이라고 했을 때
1 * 2^(n - 1)이 되지 않을까 싶습니다.
근데 여기서 반례가... abc 이렇게도 될 수 있고 .. abd 이것도 있어가지구(3개의 턴밖에 없다면 abc, abd 이것도 같게 볼 수 있거든요..) 안되는 거 같아요..
좀 더 일반화할 수 있는 공식같은게 튀어나올 거 같은데... 일단은 여기까지네요 ㅋㅋ
뭔가 생각이 더 들면 다시 답변 달겠습니다.
감사합니다.
dp에 대해선 생각 못해봤는데 앞서 배치된 말과 동일한지 아닌지, 혹은 앞서 배치된 말의 개수와 동일하게 되는지 등의 정보를 저장하면 풀이가 될 수도 있겠네요.
근데 중간에 말씀하신
어차피 어떤 인덱스에서 그 이전에 말이 똑같은지 아니면 다른지만 체크하면 되지 않을까? 생각이 드네요. 그렇게 따지면 처음의 경우의 수는 5개고.. 그 다음에는 10개(주사위의 경우의 수)가 되는 것이죠.
요 부분을 이해하지 못했습니다. 어떤 조건의 문제에서 처음의 경우의 수가 5개란건가요? 일단 저희가 다룬 예제는 말이 3개, 자리가 3개인 예제와 본 문제인 말 4개 자리가 10개인 문제가 있어서 여기에 대입해봤으나 잘 이해가 가지 않았습니다..
아 이게 이런말입니다.
주사위가 1 ~ 5가지의 경우의 수가 있죠?
그러나 말A, B, C, D로 하든간에 똑같기 때문에
처음에 5개.
그다음에 5개 * 10개가 되거든요.
예를 들어 이렇게 되는 거죠.
aa
ab
이렇게 되는건데 여기서 a, b는 말을 뜻합니다.
ab라는 것은.
AB든.
AD든
AC든
CA든
똑같다는 것을 의미합니다.
aa라는 것은.
AA든.
BB든
CC든
DD든
똑같다는 것을 의미합니다.
이렇게 n = 2일 때 봤을 때는 똑같죠?
그걸 상상한 것이고.
그렇게 따졌을 때 경우의 수는
5 * 5 와
5 * 5를 더한 값이기 때문에
5 * 10이 된다는 말이였어요 ㅎㅎ
근데.. 이거 자체가 n이 커지면 또 안되는 반례가 있어서 흐지부지 된 것이죠..
또한 완탐으로 하거나 모든 경우의 수 자체를 조합으로 만들어서 하는 것은 시간복잡도상 사실 차이가 그렇게 많지는 않습니다. 어차피 모든 경우의 수를 고려하는 것이기 때문이죠.
>> 이유가 궁금합니다.
제가 조합을 만들 때 쓴 함수입니다. 이는 0,1,2,3의 배열을 넘겨서 호출했고 이 함수는 다음과 같은 값을 리턴합니다.
이는 0~3번 말이 이동하는 횟수의 모든 경우의 수입니다. 이 조합을 뽑고, func2로 0,2,2,6을 보내면 {1,1,2,2,3,3,3,3,3,3}의 배열을 만들고 이 배열을 next_permutation으로 경우의 수를 만들었습니다. 그런 결과, next_permutation은 약 11만회, func2는 23회 호출됐습니다. 23은 위의 조합의 개수입니다. 총 23번 func2를 호출했고 저걸로 순열을 만드는데에 총 11만번의 연산이 수행된 것입니다.
이런 결과라면 4^10인 100만보다 훨씬 낮은 시간복잡도를 갖는게 아닌가요?
참고로 강사님의 코드에서는 go함수를 카운트했을 때 gocnt 24만, innergo 28만 혹은 입력을 다르게 했을때 각 33만 37만회 호출됐습니다만.. 이건 또 이상하네요. isMal함수가 true를 반환해서 continue가 많이 이루어져서 재귀 호출이 적었던걸까요? innergo가 gocnt와 큰 차이가 없군요.
수치만 보고 꽤 큰 차이 아닌가? 싶었는데 막상 백준 실행시간보면 제 코드와 강사님 코드 모두 실행시간은 동일하네요 하하..