= 파스칼의 삼각형 알고리즘 =
 * 며칠전에 마감된 자료구조의 첫번째 숙제였죠? 다른 분들도 다르게 짜신 분이 있으시다면 서로 의견을 나눠 보았으면 합니다.

== 재귀 호출을 이용한 방법 - by 인수 ==
{{{~cpp 
const int pas(const int &m,const int &n)
{
    if(m==n || n==1) // 행과 열이 같거나(가장 오른쪽이거나) 열이 1일때는 1출력
        return 1;
    else
        return pas(m-1,n-1)+pas(m-1,n); // 재귀호출
}
}}}

 * 보시는 바와 같이.. 졸라 간단합니다.
 * but.. 숫자가 조금만 커져도.. 굉장히 오래 걸립니다. 01학번 이선호군이 32행 정도를 넣어봤을때 걸린 시간은 100초가 넘었다 합니다. 재귀호출.. 될수 있으면 쓰지 맙시다.
 * 이 알고리즘은 시간을 희생하면서 공간을 줄인 알고리즘이겠죠?
 * 뒤를 볼것도 없이 일관적인 알고리즘 -- 선호.

== recursive -zennith ==
{{{~cpp 
unsigned long int P(int row, int col) {
	/* 열의 값이 행보다 클 경우 종료 */
	if(row < col)
		exit(0);

	/* 주어진 값을 검사하여, 첫번째 열이 1이거나 행과 열이 같은경우 1을 리턴 */
	if(col == 1 || row == col)
		return 1;

	/* 그렇지 않은 경우 행과 열을 1씩 감소해서 재귀 호출한 값과
	행만 1 감소시켜 재귀 호출한 값을 더해서 리턴 */
	return P(--row, --col) + P(row, ++col);
}
}}}

 * 단순히 프린트물의 내용을 옮겼을 뿐..

== 동적 배열을 이용한 방법 - by 인수 ==
{{{~cpp 
typedef unsigned long ulong;

ulong Pascal_Triangle(int m,int n)
{
	ulong **Array=new ulong*[m];	// 2차원 동적 배열 할당

	for(int i=0;i<m;i++)
		Array[i]=new ulong[i+1];	// n행에는 n개의 열만 할당되게

	for(i=0;i<m;i++)
	{
		for(int j=0;j<=i;j++)
		{
			if(i==j || j==0)		// 행과 열이 같거나 열이 1일때
				Array[i][j]=1;		// (배열은 0부터 시작하므로 0이라했음) 1의 값을 줌
			else
				Array[i][j]=Array[i-1][j-1]+Array[i-1][j];
						// 그 외의 경우에는 공식을 따른다.
		}
	}

	ulong return_value=Array[m-1][n-1];
	// 원하는 값 리턴(역시 배열은 0부터 시작하므로 하나씩 빼서)

	if(Array)	// Array 2차원 배열이 할당되었을때
	{
		for(i=0;i<m;i++)
		{
			if(Array[i])
				delete [] Array[i];		// 지워 준다.(열)
		}
	}

	delete [] Array;		// 지워 준다.(행)

	return return_value;
}
}}}

 * 딱 보기에도 재귀호출보다는 복잡하죠?
 * 그런데.. 속도는 확실히 빠릅니다. 몇백을 넣어도 즉시즉시 나오는..
 * 이 알고리즘은 메모리를 더 쓰면서 속도를 살린 방법이겠죠?
 * 자바로 짜면 좀 더 쉬울거 같네여. 메모리 새는걸 걱정하지 않아도 되니..
 * 다른 좋은 방법이 있으시면 여기다 적어주시기 바랍니다.
 * ㅡ.ㅡ 가..같다.. --선호

== dynamic allocation -zennith ==
{{{~cpp 
int P(int row, int col) {
	/* 변수 선언부 */
	int i, j, temp;

	/* 연산을 위해 이중 정수형 포인터 선언 */
	int ** buffer;

	/* 열이 행보다 클 경우 종료 */
	if(col > row)
		exit(0);

	/* buffer에 행만큼의 정수포인터형을 할당받아 대입 */
	buffer = malloc( row * sizeof(int *) );

	for(i = 0; i < row; i++) {
		/* 각각의 정수 포인터에 정수 배열을 할당한다 */
		*(buffer + i) = (int *)malloc( (i + 1) * sizeof(int) );

		/* 할당을 실패했을 때 */
		if(*(buffer + i) == NULL) {

			/* 먼저 여태까지 할당한 정수 배열을 반환 하고 */
			for(j = 0; j <= i; j++) {
				free(*(buffer + j));
			}

			/* 정수 포인터 배열을 반환 한 후 */
			free(buffer);

			/* 종료한다 */
			exit(0);
		}
	}

	/* 연산부 */
	for(i = 0; i < row; i++) {
		for(j = 0; j <= i; j++) {
			/* 열이 1이거나 행과 열이 같은 경우, 1을 대입 한다 */
			if(j == 0 || j == i) {
				*(*(buffer + i) + j) = 1;
				continue;
			}

			/* 그렇지 않은 경우 전 행(i - 1) 전 열(j - 1)의 값과,
			전 행(i - 1) 동 열(j) 의 값을 더해서 대입한다 */
			*(*(buffer + i) + j) =
				*(*(buffer + i - 1) + j - 1) + *(*(buffer + i - 1) + j);
		}
	}

	/* 계산한 결과값을 임시변수에 저장한다 */
	temp = *(*(buffer + row - 1) + col - 1);

	/* 먼저 정수 배열을 반환하고 */
	for(i = 0; i < row; i++)
		free(*(buffer + i));

	/* 정수 포인터 배열을 반환한다 */
	free(buffer);

	/* 임시변수에 저장한 값을 리턴 */
	return temp;
}
}}}

 * 아직 개선할점이 한 두 군데 있는데.. 구지 여기에 올린 이유는 저게 Null pointer assignment 에러가 나서.. 에러난걸 왜 올리는데. 라고 하시면 할말 없지만.. 혹시 혜안으로 시원하게 찔러주실 분 지적해주시면 감사하겠습니다.
 * 해결했습니다. 문제 없이 돌아가는군요.. 역시 포인터는 어렵고 어려워라..

== 첫줄부터 쭉 계산하는 방법 ==
{{{~cpp 
// 첫행부터 n행까지 계산하는 방법을 통해
// 파스칼의 삼각형의 n행 m열의 값을 구하는 함수 (34행 까지 계산 가능)
unsigned long PascalTriangle1(int n, int m)
{
	if(n<0 || n>35 || m<0 || m>n)	// 행과 열의 값이 잘못된경우 0을 리턴
		return 0;
	if(n==1 || n==2)	// 1행 또는 2행은 모두 1 이므로 1을 리턴
		return 1;

    // 2개의 배열을 사용하여 계산을 한다
	// 하나의 배열에 2행을 저장한 후
	// 그 배열을 사용해 3행을 계산해 나머지 배열에 저장하고
	// 다시 3행이 저장된 배열을 사용해 4행을 계산해서
	// 2행이 저장되어 있던 배열에 저장하고
	// 계속 이와같은 식으로 n행 까지 계산한다

	unsigned long *row[2];	// 2개의 배열의 포인터
	row[0]=new unsigned long[40];	// 최대 40열까지 저장할 수 있도록 메모리 할당
	row[1]=new unsigned long[40];
	row[0][0]=row[0][1]=1;	// 2행을 저장한다
	int current=0;	// 2개의 배열 중 계산중인 배열을 나타내는 변수

	for(int i=3;i<=n;i++)	// 3행부터 n행까지 계산
	{
		current=!current;	// 계산할 배열을 바꿈

		row[current][0]=1;	// 첫번째 열은 항상 1
		row[current][i-1]=1;	// 마지막 열도 항상 1

		for(int j=1;j<i-1;j++)	// 나머지 열을 계산
			row[current][j]=row[!current][j-1]+row[!current][j];
	}

	// n행 m열의 값을 보관
	unsigned long temp=row[current][m-1];
	delete[] row[0];	// 할당했던 메모리 해제
	delete[] row[1];
	return temp;	// 보관해둔 n행 m열의 값을 리턴
}
}}}

== 조합의 수를 이용한 방법 ==
{{{~cpp 
// 조합의 수를 계산하는 방법을 통해
// 파스칼의 삼각형의 n행 m열의 값을 구하는 함수 (17행까지 계산 가능)
unsigned long PascalTriangle2(int n, int m)
{
	if(n<0 || n>18 || m<0 || m>n)	// 행과 열의 값이 잘못된 경우 0을 리턴
		return 0;
	if(n==1 || n==2)	// 1행 또는 2행은 모두 1 이므로 1을 리턴
		return 1;
	// 5행 1열과 5행 5열, 5행 2열과 5행 4열 등은
	// 값이 같지만 5행 1열이나, 5행 2열이 계산이 간단하여
	// 계산중에 오버플로우가 일어나는 경우를 줄일수 있어
	// 더욱 많은 행을 계산할 수 있다
	// 5행 5열이나, 5행 4열과 같은 것을 5행 1열이나, 5행 2열로
	// 바꿔서 다시 호출해주는 부분이다
	if(m>n/2+n%2)
		return PascalTriangle2(n,n-m+1);

	unsigned long x=1,y=1, p;

    // (n-1)!/((n-1)-(m-1))! 을 계산
	p=n-1;
	for(int i=0;i<m-1;i++)
	{
		x*=p;
		p--;
	}

	// (m-1)! 을 계산
	for(p=m-1;p>=2;p--)
		y*=p;

	return x/y;	// (n-1)!/(((n-1)-(m-1))!*(m-1)!) 을 리턴
}
}}}
----
[문제분류]