파스칼의 삼각형은 수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것이다. 이것은 블레즈 파스칼에 의해 이름 붙여졌으나 이미 수세기 전에 다른 사람들에게서 연구된 것이다.

단순한 형태로, 파스칼의 삼각형은 다음과 같은 방법으로 만들 수 있다.

1.먼저 첫 번째 줄에는 숫자 1을 쓴다.
2.그 다음 줄을 만들려면, 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다. 예를 들어, 네 번째 줄의 숫자 1과 3을 더하여 다섯 번째 줄의 4가 만들어진다.

자료출처 : 위키백과


파스칼의 삼각형 모양 1

#include < stdio.h >

void Pascal(int n)
{
	int i, j;
	int p[10][20]={0};

	p[1][n]=1;
	for (i=2; i<=n; i++){
		for (j=1; j<=n*2; j++){
			p[i][j] = p[i-1][j-1] + p[i-1][j+1];
		}
	}

	for (i=1; i<=n; i++){
		for (j=1; j<=n*2; j++){
			if (p[i][j] == 0) printf("  ");
			else printf("%d ", p[i][j]);
		}
		printf("\n");
	}
}

int main()
{
	int n;

	printf("몇 줄까지 출력할까요? ");
	scanf("%d", &n);

	Pascal(n);

	return 0;
}

#include < stdio.h >

void Pascal(int n)
{
	int i, j;
	int p[10][10]={0};

	p[1][1]=1;
	for (i=2; i<=n; i++){
		for (j=1; j<=i; j++){
			p[i][j] = p[i-1][j-1] + p[i-1][j];
		}
	}

	for (i=1; i<=n; i++){
		for (j=1; j<=i; j++){
			printf("%d ", p[i][j]);
		}
		printf("\n");
	}
}

int main()
{
	int n;

	printf("몇 줄까지 출력할까요? ");
	scanf("%d", &n);

	Pascal(n);

	return 0;
}

아래와 같은 5x5 달팽이 모양 사각형을 만들어보자.

* 문제를 푸는 방법에는 여러가지 유형이 있다. 다음은 그중 한가지이다.

우선 내부의 숫자가 채워진 방향을 살펴보면

①~④의 순서대로 채우고, 이것을 채우는 횟수가 0 이 될때 까지 반복한다.

a[6][6] = a[1][1]부터 채우기 위해 6행 6열을 준비했다.
k=0 - 채워질 숫자
x=1, y=0 - 채울 행, 열
변수는 이렇게 준비한다.

①은 5번, a[1][1]부터 차례로 채운다.
a[x][++y] = ++k; 이렇게 하면 x=1 이고 , y는 전치증가연산을 사용해 1 이 된다. 또한 k도 전치증가연산을 하여 1 이 되고 a[x][y]에 저장된다.
따라서 a[1][1]=1, a[1][2]=2, a[1][3]=3, a[1][4]=4, a[1][5]=5 이렇게 채워진다.

②은 4번 a[1][5]부터 차례로 채운다. 단 이번에는 5번이 아닌 4번임을 주의한다.
a[++x][y]=++k; 이렇게 하면 y=5 이고 , x는 전치증가연산을 사용해 2가 된다. 또한 k도 전치증가연산을 하여 6 이 되고 a[x][y]에 저장된다.
따라서 a[2][5]=6, a[3][5]=7, a[4][5]=8, a[5][5]=9 이렇게 채워진다.

③은 4번 a[5][5]부터 ①과 반대 방향으로 차례로 채운다.
a[x][--y]=++k; ①과 반대 방향이므로 x=5 이고 , y는 전치감소연산을 사용해 4 가 된다. 또한 k도 전치증가연산을 하여 10 이 되고 a[x][y]에 저장된다.
따라서 a[5][4]=10, a[5][3]=11, a[5][2]=12, a[5][1]=13 이렇게 채워진다.

④는 3번 a[5][1]부터 ②와 반대 방향으로 차례로 채운다. 단 이번에는 4번이 아닌 3번임을 주의한다.
a[--x][y]=++k; ②와 반대 방향이므로 y=1 이고 , x는 전치감소연산을 사용해 4가 된다. 또한 k도 전치증가연산을 하여 14가 되고 a[x][y]에 저장된다.
따라서 a[4][1]=14, a[3][1]=15, a[2][1]=16 이렇게 채워진다.

이와같은 방식으로 반복횟수가 0 이 될때 까지 계속 진행한다.

소스)

int a[6][6]={0}, n=5;
int i, x=1, y=0, k=0;

for (::)
{
	// 1번 가로 채우기
	for (i=1; i<=n; i++)
	{
		a[x][++y]=++k;
	}

	// 2번 세로 채우기
	n--;	// 반복횟수 1감소
	if (n<=0) break;
	for (i=1; i<=n; i++)
	{
		a[++x][y]=++k;
	}

	// 3번 가로 채우기
	for (i=1; i<=n; i++)
	{
		a[x][--y]=++k;
	}

	// 4번 세로 채우기
	n--;	// 반복횟수 1감소
	if (n<=0) break;
	for (i=1; i<=n; i++)
	{
		a[--x][y]=++k;
	}
}

비트 연산(Bitwise operation)은 한 개 혹은 두 개의 이진수에 대해 비트 단위로 적용되는 연산이다.

* int 는 부호가 있는 정수라는 점을 잊지 말자.

● AND 연산자 : &
a & b : a, b 둘 다 '참' 일 때 1을 반환
예) 0 & 0 => 0
 0 & 1 => 0
 1 & 1 => 1

소스)

int main()
{
	int a = 4;	//0000 0100
	int b = 20;	//0001 0100
	int c = a & b;	//0000 0100
	printf("a & b = %d \n", c); // 4
	return 0;
}

● OR 연산자 : |
a | b : a, b 중 하나라도 '참' 일 때 1을 반환
예) 0 | 0 => 0
 0 | 1 => 1
 1 | 1 => 1

소스)

int main()
{
	int a = 4;	//0000 0100
	int b = 20;	//0001 0100
	int c = a | b;	//0001 0100
	printf("a | b = %d \n", c); // 20
	return 0;
}

● XOR 연산자 : ^
a ^ b : a, b 두 값이 서로 다를 때 1을 반환
예) 0 ^ 0 => 0
 0 ^ 1 => 1
 1 ^ 1 => 0

소스)

int main()
{
	int a = 4;	//0000 0100
	int b = 20;	//0001 0100
	int c = a ^ b ;	//0001 0000
	printf("a ^ b = %d \n", c); // 16
	return 0;
}

● NOT 연산자 : ~
~a : 값을 반대로 나타낸다.
예) ~0 => 1
 ~1 => 0

소스)

int main()
{
	int a = 4;	//0000 0100
	int c = ~a ;	//1111 1011 -> 부호있는 2의 보수의 형식이다.
	printf("~a = %d \n", c); // -5
	return 0;
}

● 왼쪽 쉬프트 연산자 : <<
a << b : a의 비트들을 b칸씩 왼쪽으로 이동, a*2^b의 값이 된다.
예) 18의 2인수 0001 0010 의 비트들을 왼쪽으로 두 칸씩 이동 : 0100 1000 -> 72

소스)

int main()
{
	int a = 18;
	int c = a << 2;	// 72 -> 18*4
	printf("%d << %d = %d \n", a, 2, c); 
	return 0;
}

● 오른쪽 쉬프트 연산자 : >>
a >> b : a의 비트들을 b칸씩 왼쪽으로 이동, a/2^b의 값이 된다.
예) 72의 2진수 0100 1000 의 비트들을 오른쪽으로 2칸 이동 : 0001 0010 -> 18

소스)

int main()
{
	int a = 72;
	int c = a >> 2;	// 18 -> 72/4
	printf("%d >> %d = %d \n", a, 2, c); 
	return 0;
}

인도 베나레스에 있는 한 사원에는 세상의 중심을 나타내는 큰 돔이 있고 그 안에 세 개의 다이아몬드 바늘이 동판 위에 세워져 있습니다. 바늘의 높이는 1 큐빗이고 굵기는 벌의 몸통만 합니다. 바늘 가운데 하나에는 신이 64개의 순금 원판을 끼워 놓았습니다. 가장 큰 원판이 바닥에 놓여 있고, 나머지 원판들이 점점 작아지며 꼭대기까지 쌓아 있습니다. 이것은 신성한 브라흐마의 탑입니다. 브라흐마의 지시에 따라 승려들은 모든 원판을 다른 바늘로 옮기기 위해 밤낮 없이 차례로 제단에 올라 규칙에 따라 원판을 하나씩 옮깁니다. 이 일이 끝날 때, 탑은 무너지고 세상은 종말을 맞이하게 됩니다.

뤼카가 하노이의 탑(tours de Hanoï)이라는 이름을 붙인 이유는 명확하지 않으나, 당시 프랑스의 식민지였던 베트남 하노이를 상징하는 국기탑에서 유래하였을 것으로 추정된다.

-출처 : 위키백과

하노이의 탑(Tower of Hanoi)은 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.

다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 하나의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

#include < iostream.h>
void hanoi(int n, int s, int e)
{
    if (n<=0) return ;
    hanoi(n-1, s, 6-s-e);
    cout << s << "에서 " << n << "돌을 " << e << "로 이동 " << "\n";
    hanoi(n-1, 6-s-e, e);
}

void main()
{    int nt;
    cout << "하노이의 돌 갯수 : ";
    cin >> nt;
    hanoi(nt,1,3);
}

삽입 정렬(揷入整列)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다. 

각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다. 

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

31 25 12 22 11 의 원소들이 있을 때 삽입정렬을 하면,

31 [25] 12 22 11    두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25> 31 [12] 22 11    세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12> 25 31 [22] 11    네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12 <22> 25 31 [11]    마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11> 12 22 25 31    종료.

소스)

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ) data[j+1] = data[j];
    data[j+1] = remember;
  }
}

아래는 정렬되는 자료가 단순 데이터일 경우에 memcpy()를 이용하여 자료를 밀어내는 예제이다. memcpy()는 자료를 당겨야하므로 비교를 역순으로 수행한다. 위의 코드보다 25~30% 가량 빠르게 처리된다.

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  i = n-1;
  while ( i-- > 0 )  
  {
    remember = data[(j=i)];
    while ( ++j < n && remember > data[j] );
 
    if ( --j == i ) continue;
    memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );
    data[j] = remember;
  }
}

출처 : 위키백과

#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 8, 5, 1, 7};
    int i, j;

    for (i=1; i<7; i++){
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1])SWAP(a[j], a[j+1]);
        }
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}

 소스)

#define SWAP(x, y) {int t=x; x=y; y=t;}

int main()
{
    int a[7]={10, 9, 4, 5, 6, 7, 8};
    int i, j, flag;

    for (i=1; i<7; i++){
        flag=0;
        for (j=0; j<7-i; j++){
            if (a[j] > a[j+1]){
                SWAP(a[j], a[j+1]);
                flag=1;
            }
        }
        if (flag==0) break;
    }

    for (i=0; i<7; i++){
        printf ("%d ", a[i]);
    }

    return 0;
}

최대공약수를 구할때는 "유클리드 호제법"을 사용하는것이 편하다.

유클리드 호제법이란? 단순하게 설명해서

1. 큰 수에서 작은 수를 나눈 나머지를 구한다.(큰 수 작은 수의 구분은 크게 의미가 없고 단지 먼저수와 나중수의 의미가 크다.)
2. 작은 수가 큰 수, 나머지가 작은 수의 역활을 하여 1의 과정을 다시한다.
3. 2의 과정을 하다가 나머지가 0 이며 종료한다.
4. 마지막으로 나눈 값이 최대공약수 이다.

그럼 최소공배수는 어떻게 구하나?
최대공약수로 처음의 큰 수와 작은 수의 곱을 나누면 된다.

큰수 * 작은수 / 최대공약수

예)두수를 입력받아서 최대공약수와 최소공배수 구하기

int EU(int x, int y)
{
    int n;
    while (1){
         n = x % y;
         if (n == 0) return y;
         x = y;
         y = n;
    }
}

int main()
{
    int gcm, lcm, su1, su2;
    scanf("%d %d",&su1, &su2);

    gcm = EU(su1, su2);
    lcm = su1 * su2 / gcm;

    printf("최대공약수 = %d\n", gcm);
    printf("최소공배수 = %d\n", lcm);

 return 0;
}

그럼 3개 이상의 수에서는 어떻게 구할까?

1. 처음 하나의 숫자를 최대공약수와 최소공배수로 정의한다. (숫자가 하나 일 때는 그 수가 최대공약수, 최소공배수이기 때문이다.)
2. 지금까지 구해놓은 최대공약수와 새로운 수로 최대공약수를 구한다.
3. 또 지금까지 구해놓은 최소 공배수와 새로운 수로 최소공배수를 구한다. 주의 - 최소공배수 * 새로운 수를 나눌때는 지금 곱하는 두 수의 최대공약수로 나누어야한다.
4. 2, 3 과정을 모든 숫자가 끝날때까지 반복한다.

예) 5개의 숫자를 입력 받아 최대공약수와 최소공배구수 구하기

소스)

int EU(int x, int y)
{
    int n;
    while (1){
        n = x % y;
        if (n == 0) return y;
        x = y;
        y = n;
    }
}

int main()
{
    int gcm, lcm, su, i;
    scanf("%d",&su);
    gcm = lcm = su;

    for(i=1; i<5; i++){
        scanf("%d",&su);
        gcm = EU(gcm, su);
        lcm = lcm * su / EU(lcm, su);
    }

    printf("최대공약수 = %d\n", gcm);
    printf("최소공배수 = %d\n", lcm);

    return 0;
}