양의 정수 N이 주어졌을 때, 모든 이항 계수(binomial coefficient) 중에서 가장 큰 값을 찾는 문제를 살펴보겠습니다.
문제 정의
이항 계수 수열은 다음과 같이 표현됩니다.
nC0, nC1, nC2, …, nCr, …, nCn-2, nCn-1, nCn
여기서 우리가 구해야 할 것은 nCr의 최댓값입니다. 이항 계수는 아래 공식으로 계산할 수 있습니다.
nCr = n! / (r! × (n − r)!)
예제 1
입력: N = 4
출력: 최대 계수 = 6
설명: 4C0 = 1, 4C1 = 4, 4C2 = 6, 4C3 = 4, 4C4 = 1 이므로, 이 경우 최대 계수는 6입니다.
예제 2
입력: N = 5
출력: 최대 계수 = 10
설명: 5C0 = 1, 5C1 = 5, 5C2 = 10, 5C3 = 10, 5C4 = 5, 5C5 = 1 이므로, 이 경우 최대 계수는 10입니다.
알고리즘 접근 방식
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 사용자로부터 N을 입력받습니다.
- 함수 maxCoeff(int n)은 매개변수 'n'을 하나 받아, 지금까지 발견한 최대 계수를 반환합니다. 계산 결과는 C[n+1][n+1] 배열에 저장됩니다.
- min과 max 변수를 0으로 초기화합니다. 'min'은 C[][] 배열을 순회하는 범위를 정하는 데 사용되고, 'max'는 발견된 최대 계수 값을 저장하는 데 사용됩니다.
- i = 0부터 n까지의 반복문으로 C[][] 배열을 초기화합니다.
- 내부 반복문에서는 'i'와 'n' 중 더 작은 값까지만 순회합니다.
- i == j인 경우 C[i][j] = 1이고, 그 외의 경우 파스칼 삼각형의 성질을 이용해 C[i][j] = C[i-1][j-1] + C[i-1][j]로 계산합니다.
- 배열 계산이 끝나면 C[][] 배열을 다시 한번 전체 순회하며 최대 계수를 max 변수에 저장합니다.
- 최종 결과를 반환합니다.
C 언어 구현 예제
#include <stdio.h>
int maxCoeff(int n){
int C[n+1][n+1];
int max=0,min=0;
// 이항 계수 값 계산
for (int i = 0; i <= n; i++){
min=i<n?i:n;
for (int j = 0; j <= min; j++){
if (j == 0 || j == i)
C[i][j] = 1;
else
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}
for (int i = 0; i <= n; i++){
max = max> C[n][i] ? max: C[n][i];
}
return max;
}
int main(){
int N = 3;
printf("Maximum Coefficient :%d", maxCoeff(N) );
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.
Maximum Coefficient: 3
마무리
이 방법은 동적 계획법(DP)을 활용해 파스칼 삼각형 형태로 이항 계수를 채워 나간 뒤, 마지막 행에서 최댓값을 찾는 방식입니다. 시간 복잡도는 O(n²)이며, 이항 계수가 대칭성(nCr = nCn-r)을 가진다는 점을 활용하면 실제 계산량을 절반으로 줄일 수도 있습니다.