백준 2407번: 조합

접근법

• $nCr = n!/(r!*(n-r)!)$입니다.
• factorial을 단순히 재귀함수로 구현하면 시간초과가 발생합니다.
  • 이미 구한 값은 다시 계산하는 게 아니라 이전에 구한 값을 바로 사용하는 방식이 요구됩니다. 이는 Dynamic Programming문제의 메모이제이션에 해당하는 부분으로 매우 자주 사용되기 때문에 여기서 확실히 익혀두시길 바랍니다.

정답

n,m = list(map(int,input().split(" ")))

dp = [0]*(n+1) // 이미 구한 factorial값을 저장합니다

def factorial(n):
    #0!은 1입니다
    if n == 0:
        dp[0] = 1
        return 1
    #1!은 1입니다
    if n == 1:
        dp[1] = 1
        return 1
    #factorial(n)값이 이전에 계산해서 dp에 저장되어 있다면
    if dp[n] !=0:
        return dp[n] #저장된 값을 그대로 씁니다
    else: #저장되어진 값이 없다면
        dp[n] = n*factorial(n-1) #재귀를 통해 새롭게 구합니다
        return dp[n]
print((factorial(n)//factorial(m)//factorial(n-m)))        

기타

• 단순나눗셈을 하면 틀립니다.

#둘의 결과는 다릅니다.
print((factorial(n)/factorial(m)/factorial(n-m))) 
#결과: 1.9564640595300215e+28
print((factorial(n)//factorial(m)//factorial(n-m))) 
#결과: 19564640595300216439731236256

왜 결과가 다를까?

• 부동소수점 때문입니다. 부동소수점의 사전적 의미는 다음과 같습니다.
  

실수를 컴퓨터상에서 근사하여 표현할 때 소수점의 위치를 고정하지 않고 그 위치를 나타내는 수를 따로 적는 것

아주 간단히 설명하면 우리가 5.0이라고 쓴 값을 컴퓨터는 4.999999999999999의 값으로 저장한다는 뜻입니다.
factorial(n)은 정수이고 factorial(m)도 정수이지만 이를 나눈 값을 파이썬은 기본적으로 실수로 반환합니다.
이러한 차이가 아주 큰 값에 적용되면 그 결과값이 달라질 수 있습니다.

• 부동소수점 문제를 해결하는 방법은 다음과 같습니다.

  • 첫째. 몫을 표현하는 //로 나눗셈을 실행합니다.
  • 둘째. Decimal패키지와 함수를 활용합니다.
    • Decimal(5.0)을 하면 4.999999999가 아닌 5.0의 값을 제대로 저장합니다.

• 이렇게 불편한 부동소수점을 왜 쓸까?

  • 소수점은 정확히 계산하려면 1/3 = 0.33333333333.... 처럼 무한이 길어져 메모리가 부족할 수 있습니다.
  • 정확한 계산도 좋지만 메모리를 고려해 어느 부분에서는 그 값을 끊어줘야 했고, 그게 바로 부동소수점이 도입된 이유일 것이라 생각합니다. (이는 정확한 내용이 아닌 제 추측입니다)