조합(nCr) 값을 여러 번 계산해야 하는 상황을 가정해 보겠습니다. 이 문제는 매우 효율적으로 해결할 수 있습니다. 핵심 아이디어는 작은 값의 nCr 결과를 저장해 두면 이를 재활용하여 더 큰 값을 쉽게 구할 수 있다는 점입니다. 즉, n이 주어졌을 때 nC0부터 nCn까지의 전체 목록을 한 번에 구하는 것이 목표입니다. 만약 계산 결과가 너무 커진다면 10^9로 나눈 나머지를 반환하면 됩니다.
예를 들어 입력이 n = 6이라면 출력은 [1, 6, 15, 20, 15, 6, 1]이 됩니다.
해결 접근 방식
조합의 성질을 이용하면 다음과 같은 점화식을 얻을 수 있습니다.
nCr = nC(r-1) × (n − r + 1) / r
이전 값을 활용해 다음 값을 상수 시간(O(1))에 계산할 수 있으므로, 전체 시간 복잡도는 O(n)입니다. 알고리즘은 다음과 같습니다.
- items := 원소 1 하나만 담고 있는 리스트로 초기화합니다.
- r을 1부터 n까지 반복하며 다음을 수행합니다.
- (items의 마지막 원소 × (n − r + 1)) / r 의 몫을 items의 끝에 추가합니다.
- items[n-2] := items[n-2] mod 10^9 로 갱신합니다. (여기서 n은 items의 현재 크기)
- items를 반환합니다.
예제 코드
아래 Python 구현 예시를 통해 더 잘 이해할 수 있습니다.
def solve(n): items = [1] for r in range(1,n+1): items.append(items[-1]*(n-r+1)//r) items[-2] %= 10**9 return items n = 6 print(solve(n))
입력
6
출력
[1, 6, 15, 20, 15, 6, 1]
이처럼 파스칼의 삼각형의 대칭성과 점화식을 활용하면 팩토리얼을 직접 계산하지 않고도 오버플로우 위험을 줄이면서 모든 조합 값을 빠르게 구할 수 있습니다.