Lv 0. 구슬을 나누는 경우의 수 *다시 풀어보기*

https://school.programmers.co.kr/learn/courses/30/lessons/120840

 

#include <string>
#include <vector>

using namespace std;

int comb[35][35];

int solution(int n, int r) {
    int answer = 0;
    for(int i=1; i<=30;i++){
        comb[i][0]=comb[i][i]=1;
        for(int j=1;j<i;j++){
            comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
        }
    }
    answer=comb[n][r];
    return answer;
}

 

이 문제의 경우는, 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int solution(int n, int r) {
    int ret = 1;

    for(int i=1; i<=n; i++) ret*=i;
    for(int i=1; i<=r; i++)  ret/=i;
    for(int i=1; i<=n-r;i++) ret/=i;
    
    return ret;
}

이와 같은 형태의 풀이만 생각이 나서 아주아주 오랜 시간 생각을 해보았는데, 계속 생각이 안나서( overflow 발생- long long 으로 설정해도 발생) 바킹독 알고리즘 강의에서 수학 부분을 확인해보고 해당 강의에서 케이스가 큰 경우의 이항계수를 구하는 방법을 보고나서 dp로 해결하는 풀이법을 알게되어서 맨 위에 제시한 풀이법으로 작성해서 해결한 문제이다. 아무래도 완전하게 내가 생각한 풀이가 아니기 때문에 다음에 꼭 다시 풀어보자. 

 

그리고 다른 사람들의 풀이를 보게 되면, 

 

#include <string>
#include <vector>

using namespace std;

int combi(int n, int r){
    if(r == 0) return 1;
    if(n == 1) return 1;
    if(r >= n) return 1;
    return combi(n-1, r) + combi(n-1, r-1);
}

int solution(int balls, int share) {
    int answer = 0;
    answer = combi(balls, share);
    return answer;
}

이와같이 nCr = n-1Cr-1 + n-1Cr 형태의 공식을 이용해서 재귀적으로 푼 풀이가 가장 위에 올라와있었다. 이 풀이와 맨 위에서 제출한

dp를 이용한 풀이를 한번 비교해보면, 

 

<dp를 이용한 풀이 결과>

테스트 1 〉	통과 (0.01ms, 4.21MB)
테스트 2 〉	통과 (0.01ms, 4.14MB)
테스트 3 〉	통과 (0.01ms, 4.21MB)
테스트 4 〉	통과 (0.01ms, 4.18MB)
테스트 5 〉	통과 (0.01ms, 4.22MB)
테스트 6 〉	통과 (0.01ms, 4.15MB)
테스트 7 〉	통과 (0.01ms, 4.13MB)
테스트 8 〉	통과 (0.01ms, 4.22MB)
테스트 9 〉	통과 (0.01ms, 3.59MB)
테스트 10 〉	통과 (0.01ms, 4.22MB)
테스트 11 〉	통과 (0.01ms, 4.16MB)
테스트 12 〉	통과 (0.01ms, 3.67MB)
테스트 13 〉	통과 (0.01ms, 4.14MB)
테스트 14 〉	통과 (0.01ms, 3.69MB)
테스트 15 〉	통과 (0.01ms, 4.21MB)
테스트 16 〉	통과 (0.01ms, 3.68MB)
테스트 17 〉	통과 (0.01ms, 4.02MB)
테스트 18 〉	통과 (0.01ms, 3.68MB)
테스트 19 〉	통과 (0.01ms, 4.14MB)
테스트 20 〉	통과 (0.01ms, 3.76MB)
테스트 21 〉	통과 (0.01ms, 4.21MB)
테스트 22 〉	통과 (0.01ms, 4.14MB)
테스트 23 〉	통과 (0.01ms, 4.15MB)
테스트 24 〉	통과 (0.01ms, 4.21MB)
테스트 25 〉	통과 (0.01ms, 4.21MB)
테스트 26 〉	통과 (0.01ms, 3.58MB)
테스트 27 〉	통과 (0.01ms, 4.21MB)
테스트 28 〉	통과 (0.01ms, 4.15MB)
테스트 29 〉	통과 (0.01ms, 4.13MB)
테스트 30 〉	통과 (0.01ms, 4.14MB)
테스트 31 〉	통과 (0.01ms, 3.68MB)
테스트 32 〉	통과 (0.01ms, 4.2MB)
테스트 33 〉	통과 (0.01ms, 3.64MB)
테스트 34 〉	통과 (0.01ms, 4.21MB)
테스트 35 〉	통과 (0.01ms, 4.21MB)

 

 

<재귀를 이용한 풀이 결과>

테스트 1 〉	통과 (0.01ms, 4.21MB)
테스트 2 〉	통과 (0.01ms, 4.22MB)
테스트 3 〉	통과 (0.01ms, 4.18MB)
테스트 4 〉	통과 (0.01ms, 4.21MB)
테스트 5 〉	통과 (452.59ms, 4.22MB)
테스트 6 〉	통과 (438.85ms, 4.14MB)
테스트 7 〉	통과 (437.63ms, 4MB)
테스트 8 〉	통과 (0.01ms, 4.01MB)
테스트 9 〉	통과 (0.01ms, 4.14MB)
테스트 10 〉	통과 (0.01ms, 4.16MB)
테스트 11 〉	통과 (0.01ms, 4.14MB)
테스트 12 〉	통과 (0.01ms, 4.14MB)
테스트 13 〉	통과 (0.01ms, 4.22MB)
테스트 14 〉	통과 (0.01ms, 4.21MB)
테스트 15 〉	통과 (0.01ms, 3.69MB)
테스트 16 〉	통과 (0.01ms, 4MB)
테스트 17 〉	통과 (0.02ms, 4.14MB)
테스트 18 〉	통과 (0.02ms, 4.23MB)
테스트 19 〉	통과 (0.01ms, 4.14MB)
테스트 20 〉	통과 (0.02ms, 4.2MB)
테스트 21 〉	통과 (0.01ms, 3.68MB)
테스트 22 〉	통과 (0.06ms, 4.21MB)
테스트 23 〉	통과 (0.14ms, 4.15MB)
테스트 24 〉	통과 (0.01ms, 3.68MB)
테스트 25 〉	통과 (0.97ms, 4.22MB)
테스트 26 〉	통과 (1.92ms, 4.13MB)
테스트 27 〉	통과 (0.51ms, 4.21MB)
테스트 28 〉	통과 (1.24ms, 3.64MB)
테스트 29 〉	통과 (2.02ms, 4.15MB)
테스트 30 〉	통과 (27.82ms, 3.63MB)
테스트 31 〉	통과 (45.86ms, 4.01MB)
테스트 32 〉	통과 (24.51ms, 3.57MB)
테스트 33 〉	통과 (1.64ms, 4.14MB)
테스트 34 〉	통과 (0.10ms, 4.14MB)
테스트 35 〉	통과 (347.15ms, 4.14MB)

 

dp를 이용한 풀이가 몇몇 케이스에 대해서 단순하게 재귀를 이용한 풀이보다 훨씬 빠르다는걸 알 수 있다. 

보이저엑스 면접에서 면접 결과와 관련해서 피드백을 받을때, 

"아쉬운 것들" 이라는 항목에서 받은 피드백중에 나의 대답에 대해서, 

<피보나치가 dp를 이용하면 빨라진다고 하셨습니다> 라는 부분이 있었는데, 내가 그때 피보나치의 항을 구할때 dp를 이용하면 훨씬 빠르게 구할 수 있다고 하였는데, 재귀적으로 구하는것보다 dp를 이용하는 풀이법이 훨씬 빠른데 왜 거기서는 이렇게 답변한 나의 답이 잘못되었고 그 부분이 아쉽다고 한것인지에 대해서, 이해가 가지 않는다. 

위의 결과물을 보면 재귀적으로 항을 구할때와 dp를 이용할때 아주아주 커다란 차이를 보인다.



확실하게 다음에도 이런식의 문제를 풀 일이 있다면, 재귀적으로 항의 연산을 통해서 하나의 특정한 항을 구해야 하는 형태의 경우, 재귀적인 풀이를 하기 보다는(물론 시간복잡도와 공간복잡도가 제한범위를 넘지 않는다면 충분히 시도해볼만 하지만) dp를 이용한 풀이를 통해서 시간복잡도를 확 줄여보도록 하자.

 

 

추가적으로 다른 사람의 풀이를 볼때, 아주 재미난 풀이가 있는데, 

#include <string>
#include <vector>

using namespace std;

long long solution(int balls, int share) {
    double answer = 1;
    for (int i = balls - share + 1; i <= balls; ++i)
    {
        answer *= i;
    }

    for (int i = 1; i <= share; ++i)
    {
        answer /= i;
    }

    return answer;
}

이 풀이의 경우는, nCr = n!/(r!)(n-r)! 이라는 공식보다는, 해당 수들을 약분해서, n*(n-1)*(n-2)*...*(n-r+1)/r! 이라는 값을 식으로 옮긴 것인데, 이렇게 풀이를 하면 이건 n=30 까지인 범위에서는 통과를 하는데, n=47 인 범위부터는 통과를 하지 못한다. 

dp로 해결하는것이 배열의 값과 for문의 범위를 넓히면 더 넓은 범위를 해결할 수 있어서, 현재까지는 이항계수를 구하는데 있어서는 가장 좋은 방법은 dp를 이용하는 풀이라는 생각이 든다. 

 

이 문제의 경우는 Lv 0. 에 존재 할만한 문제인지 잘 모르겠는데, 아주아주 약점 부위라는 생각이 들어서 다음에 꼭 다시한번 풀어보도록 하자. 

 

++++++++++++++++++++

추가적으로, c++ 조합 구현하기 라고 검색했을때 나오는 블로그 글인데, 읽어보고 도움을 받아볼만 해 보인다. 

https://ansohxxn.github.io/algorithm/combination/