TIL) 프로그래밍에서 조합은 어떻게 사용을 하는가?

개요

프로그래밍에서 !(팩토리얼) 을 사용하는 문제는 숫자가 너무 커지는 경우가 많다.

프로그래머스에서 나오는 입문 문제에서 순열 공식만 알고 순수하게 사용을 했다가 문제가 생긴 경우에 대해서 설명을 하고자한다.

 

 

 

프로그래머스

문제 풀이) 구슬을 나누는 경우의 수

문제는 단순하게 머쓱이가 친구들과 구슬을 나누어주는 방식에 대해서 풀어보라고 적혀있다.

일반적으로 balls와 share의 숫자가 작은 경우는 우리가 고등학생 때 배운 공식을 사용해도 문제가 없을 것이다.

문제에서 주어지는 예시는 3이기 때문에

class Solution {
    public int solution(int balls, int share) {
        return factorial(balls) / (factorial(balls-share) * factorial(share));
    }

    private int factorial(int num) {
        if( num == 1 ) return num;
        return num * factorial(num-1);
    }
}

 

factorial 재귀함수를 만들어서 사용하면 빠르게 풀 수 있다.

하지만 해당 문제에서는 제출을 하게 되면 틀린다.

틀린 모습

 

 

 

왜 틀렸는지 살펴 보면 제한사항을 살펴봐야한다.

프로그래머스에서 제한사항

제한사항에 balls 혹은 share 의 수는 30이 최대라고 적혀있다.

즉 해당 공식에 대입을 해보면 다음과 같은 숫자가 나온다.

예상하는 최대 숫자

즉 계산해야 되는 숫자는 30! 와 15! X 15! 인것이다.

 

 

기호를 써서 보니 모르겠으니까 숫자로 변환해서 확인해보자.

30!

 

15! X 15!

팩토리얼	실제 숫자
30!
15! X 15!

숫자로 봐서는 큰건 알겠는데 왜 안되는지 변수들의 범위를 통해 알아보자.

 

 

우리가 알고 있는 변수들의 범위를 생각을 해보자.

타입	메모리 사용 크기		값의 범위
byte	1byte	8bit	-128 ~ 127
short	2byte	16bit	-32,768 ~ 32,767
char	2byte	16bit	0 ~ 65535(유니코드)
int	4byte	32bit	-2,147,483,648 ~ 2,147,483,647
long	8bit	64bit	-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807

https://coding-factory.tistory.com/862

[Java] 자바의 변수 종류, 크기, 범위 총정리

다른 분께서 이쁘게 정리한 표를 가져왔다. 감사합니다.(_ _)

 

얼핏봐서는 "Long 사이즈에 문제 없지 않나"라고 생각이 들 수 있다.

265,252,859,812,191,058,636,308,480,000,000 => 30!

                                9,223,372,036,854,775,807 => Long 의 최대 숫자

어림도 없었다.....

 

 

 

그러면 해당 문제는 풀 수 없는 문제가 아닌가? 라고 생각을 한다면 방법은 2가지가 있다.

하나는 더 큰 변수를 가져오면 된다.

 

자바에는 BigInteger이라는 무제한 사이즈의 변수가 있다.

해당 BigInteger의 작동 방식은 단순하게 말하면

단순한 1234567

BigInteger는 숫자를 전부 문자열로 저장을 한다.

add(BigInteger.TEN)

만약에 new BigInteger("1234567").add(BigInteger.TEN)을 하면 위에 그림처럼 동작하게 된다.

코드

결과

블로그 주인장은 단순하게 이 방법을 생각해서 풀었다.

변수에 제한이 생기면 제한을 없애버리면 된다.

import java.math.BigInteger;

class Solution {
    public int solution(int balls, int share) {
        BigInteger front = BigInteger.valueOf(1);
        for( int i = 0; i < share; i++) {
            BigInteger temp = BigInteger.valueOf(balls);
            temp = temp.add(BigInteger.valueOf(-i));
            front = front.multiply(temp);
        }
        BigInteger back = BigInteger.valueOf(1);
        for( int i = 0; i < share; i++) {
            BigInteger temp = BigInteger.valueOf(share);
            temp = temp.add(BigInteger.valueOf(-i));
            back = back.multiply(temp);
        }

        BigInteger sum = front.divide(back);

        return sum.intValue();
    }
}

 

 

문제 풀이 이후 다른 사람 풀이 확인

사실 이 TIL을 적게 된 이유가 나오게 된다.

문제를 이렇게 풀어주신 keaunsolNa , 당근주스 , qorcp , 서민수 외 8 명에게 감사합니다.

그리고 문제 이해에 도움을 준 블로그 주인장의 수학 선생님께도 감사합니다.

 

class Solution {
    public long solution(int balls, int share) {
        share = Math.min(balls - share, share);

        if (share == 0)
            return 1;

        long result = solution(balls - 1, share - 1);
        result *= balls;
        result /= share;

        return result;
    }
}

 

일단 해당 문제에서 가장 차이점을 보이는 점은 long 타입이라는 것이다.

BigInteger을 사용하지 않아도 문제를 풀 수 있다는 점에 주목을 하게 되었다.

 

코드를 충분히 간단하여 읽을 수는 있지만 왜 이렇게 사용이 되었는지 궁금해서 블로그를 적게 되었다.

 

일단 보면 share 는 balls - share vs share 중에 더 작은 것을 받고 있다.

 

이후 share 이 0 이되면 리턴 1을 해주며

 

result 는 재귀함수로 balls - 1, share -1 을 매개변수로 사용하고 있다.

이후 result 에 balls 을 곱해주고 result 로 나눠주는 모습을 확인 할 수 있다.

 

 

 

해당 풀이에 대해서 이해를 해보자.

프로그래머스 풀이 밑에 힌트를 남겨주신 분께 감사드립니다.

 

조합 공식에도 변형 공식이 많다는 것은 알 것이다.

 

일단 공식에 대한 증명을 해보자.

 

마지막가서 코드 보면서 이해하였지만...이 증명 필요가 없다.

안 볼 사람들은 밑으로 공식을 실사용해보자 까지 넘겨가보자.

공식 증명)

수학 기초가 생각 안나서 많이 찾아봤습니다..

 

위키피디아 : 파스칼 삼각형

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

파스칼의 삼각형 - 위키백과, 우리 모두의 백과사전

 

해당 공식은 파스칼 삼각형과 관련된 조합의 성질이라고 한다...?

 

그래서 이게 무슨 의미인데?

일단 블로그 주인장이 이해한 바에 따르면

우변의 첫번째 항은 조합의 가짓수에 하나를 반드시 포함하지 않는 경우

그리고 두번째 항은 조합의 가짓수에 하나를 반드시 포함을 하는 경우

이렇게 2개가 된다.

 

예시를 들어보자

해당 프로그래머스 문제에서 보인 예시을 사용해보겠다.

머쓱이가 3개의 구슬 중 2개를 남에게 준다고 생각을 해보자.

 

머쓱이가 3개의 구슬 중 반드시 하나를 안줄 것이다. => 그러면 경우의 수는 2C2 즉 1이다.

그러면 머쓱이가 3개의 구슬 중 하나를 반드시 줄 것이다. => 그러면 경우의 수는 2C1 즉 2이다.

1 + 2가 되서 3개의 경우의 수가 나오는 것이다.

 

 

이제 공식을 실 사용을 해보자.

class Solution {
    public long solution(int balls, int share) {
        share = Math.min(balls - share, share);

        if (share == 0)
            return 1;

        long result = solution(balls - 1, share - 1);
        result *= balls;
        result /= share;

        return result;
    }
}

이제는 뭔가가 보일 것 같다. ( 아직 안 보일 수 도? )

 

 

순서대로 분석을 해보겠다.

첫번째 줄

share = Math.min(balls - share, share);

 

이것은 조합의 대칭성으로

조합의 대칭성

n C n-r = n C r 과 같은 것이다.

예시를 들면 3C1 과 3C2 와 같은 것이다.

즉, Math.min 을 사용하여 고르는 것은 숫자를 더욱 보기 쉽게 바꾸는 것이라 할 수 있다.

 

두번째 줄

if(share == 0) return 1;

share 가 0인 경우

즉, nC0 인 상태를 가르키는 것이며 아무것도 선택을 하지 않는다는 선택지는 하나뿐이다.

 

 

세번째 줄

long result = solution(balls - 1, share - 1);

드디어 재귀함수로 들어간다.

자세한 이야기는 다음 줄과 같이 하겠다.

 

 

네번째 마지막

result *= balls;
result /= share;

return result;

이제 핵심으로 들어간다.

 

이것까지 다 적어보고 코드에 대해서 이해를 해서 위에 증명이 쓸모 없다는 것을 알았다.

뭔가가 복잡하지만 순서대로 설명을 해보겠다.

 

 

조합 공식

 

가장 먼저 이것은 공식으로 보면 어렵지만 숫자로 보면 빠르게 감이 잡힌다.

 

 

이 공식을 과거 고등학생 때 배웠던 기억을 살려보면

C 뒤에 있는 숫자만큼 고른다 보면된다.

즉 7C3 는 앞에서 3개 7, 6, 5이고 분자가 되며, 뒤에 3은 3!로 되고 이것은 분모가 된다.

 

 

그래서 이것을 고르기 위해 하나씩 줄여나가게 된

여기서 s는 share의 약자입니다.

이제 보면 7에서 6 -> 5 순으로 변화하는 것을 확인할 수 있다.

밑에 share 도 3, 2, 1 순으로 변화하는 것을 볼 수 있는데, 이제

balls 는 result에서 곱하기가 되고, share는 나누기 연산이 된다.

 

 

순차적으로 쌓아나가

결론

마지막 이런 모습이 될 수 있다.

 

 

결론.

문제에서는 30C15 까지 밖에 안나오는데 왜 int 값이 오류가 나는가 라고 생각이 들수 있을 것같다.

int 값이 최대치는 약 21억까지인데 마지막 답이 155117520(약 1.5억) 이다.

1.5에 마지막 나누기 15가 되기 전 값을 생각을 해보자.

2326762800(약 23억)으로 이미 int값을 넘는다.

아마 C언어에서 있는 unsgined int 같은 것을 사용한다면 문제가 없지 않을까라는 생각이다.

 

느낀 점.

"순열 변형 공식 힌트인가" 해서 식 자체가 이해도 안되길레 증명부터 하고,

기억 안나는 것 투성이라 다 찾아서보고, 물어보고, 선생님에게 도움을 청했는데,

결론적으로는 순수하게 nCr 공식을 사용한 것이라 뭔가 허무했다.

 

이왕 이렇게 된거,

내일은 nCr = n-1Cr + n-1Cr-1 ( 이중 트리 재귀?? ) vs nCr ( 재귀 ) 비교를 해봐야겠다.