자료구조와 알고리즘 01 完 / (01~06)

Write Date : 2021.6.13
Last Edit : 2021.6.14

Last Page : 40page (완료!)

Chap(01) - 기본 알고리즘

연습문제

Q1

//q1_네 값의 최댓값을 구하는 함수 max4를 작성하세요.
#include <stdio.h>

int max4(int a, int b, int c, int d)
{
    int max;
    max = a;
    if(max < b) max = b;
    if(max < c) max = c;
    if(max < d) max = d;

    return max;
}

int main()
{
    printf("max4(%d %d %d %d) = %d\n", 3, 2, 1, 5, max4(3,2,1,5));
    printf("max4(%d %d %d %d) = %d\n", 1, 2, 4, 1, max4(1,2,4,1));
    printf("max4(%d %d %d %d) = %d\n", 3, 1, 2, 1, max4(3,1,2,1));
    // ...
    return 0;
}

Q2

// q2_세 값의 최솟값을 구하는 min3 함수
#include <stdio.h>

int min3(int a, int b, int c)
{
    int min;
    min = a;
    if(min > b) min = b;
    if(min > c) min = c;

    return min;
}

int main()
{
    printf("min3(%d %d %d) = %d\n", 1, 2, 3, min3(1,2,3));
    printf("min3(%d %d %d) = %d\n", 6, 5, 4, min3(6,5,4));
    printf("min3(%d %d %d) = %d\n", 8, 7, 9, min3(7,8,9));
    // ....
    return 0; 
}

Q3

// q2_네 값의 최솟값을 구하는 min4 함수
#include <stdio.h>

int min4(int a, int b, int c, int d)
{
    int min;
    min = a;
    if(min > b) min = b;
    if(min > c) min = c;
    if(min > d) min = d;

    return min;
}

int main()
{
    printf("min4(%d %d %d %d) = %d\n", 1, 2, 3, 4, min4(1,2,3,4));
    printf("min4(%d %d %d %d) = %d\n", 6, 5, 4, 7, min4(6,5,4,7));
    printf("min4(%d %d %d %d) = %d\n", 8, 7, 9, 10, min4(7,8,9,10));
    // ....
    return 0; 
}

Q4

// q4_ 세 값의 대소 관계 13종류의 모든 조합에 대해 중악밧을 구하여 출력하는
// 프로그램
#include <stdio.h>

int med3(int a, int b, int c)
{
    if (a >= b)
        if (b >= c)
            return b;
        else if (a <= c)
            return a;
        else
            return c;
    else if (a > c)
        return a;
    else if (b > c)
        return c;
    else
        return b;
}

int main()
{
    int a, b, c;

    printf("세 정수의 중앙값을 구합니다.\n");
    
    printf("%d %d %d is med = %d\n", 3, 2, 1, med3(3,2,1)); // A a > b > c
    printf("%d %d %d is med = %d\n", 3, 2, 2, med3(3,2,2)); // B a > b = c
    printf("%d %d %d is med = %d\n", 3, 1, 2, med3(3,1,2)); // C a > c > b
    printf("%d %d %d is med = %d\n", 3, 2, 3, med3(3,2,3)); // D a = c > b
    printf("%d %d %d is med = %d\n", 2, 1, 3, med3(2,1,3)); // E c > a > b
    printf("%d %d %d is med = %d\n", 3, 3, 2, med3(3,3,2)); // F a = b > c
    printf("%d %d %d is med = %d\n", 3, 3, 3, med3(3,3,3)); // G a = b = c
    printf("%d %d %d is med = %d\n", 2, 2, 3, med3(2,2,3)); // H c > a = b
    printf("%d %d %d is med = %d\n", 2, 3, 1, med3(2,3,1)); // I b > a > c
    printf("%d %d %d is med = %d\n", 2, 3, 2, med3(2,3,2)); // J b > a = c
    printf("%d %d %d is med = %d\n", 1, 3, 2, med3(1,3,2)); // K b > c > a
    printf("%d %d %d is med = %d\n", 2, 3, 3, med3(2,3,3)); // L b = c > a
    printf("%d %d %d is med = %d\n", 1, 2, 3, med3(1,2,3)); // M c > b > a

    return 0;
}

Q6

// q6_ while문이 종료될 때 변수 i 값이 n + 1이 됨을 확인하자.
#include <stdio.h>

int main()
{
    int i, n;
    int sum;
    sum = 0;

    puts("1부터 n까지의 합을구하며 반복문 종료시 i값을 출력");
    
    printf("n의 값 : "); scanf("%d", &n);
    while(i <= n)
    {
        sum += i;
        i++;
        if ( i > n )
            printf("i is %d + 1 = %d\n", n, i);
    }

    printf("1부터 %d까지의 합 : %d\n", n, sum);

    return 0;
}

Q7

// q7_ n이 7이면 '1+2+3+4+5+6+7 = 28'로 출력하는 프로그램작성.
#include <stdio.h>

int main()
{
    int i, n;
    int sum; // 합
    sum = 0;
    puts("1부터 n까지의 합을 구한다");
    printf("n의 값 : "); scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        sum += i;
        if (i == n)
            printf("%d = %d", i, sum);
        else
            printf("%d + ", i);
    }

    // printf("1부터 %d까지의 합은 %d입니다.\n", n, sum);

    return 0;
}

Q8

// q8_ 1부터 10의 합은 (1 + 10) * 5와 같은 방법으로 구할 수 있다.
// 가우스의 덧셈이라는 방법을 이용하여 1부터 n까지의 합을 구하는 프로그램
#include <stdio.h>

int main()
{
    int i, n, sum;
    sum = 0;
    puts("가우스 덧셈");
    
    printf("n을 입력하세요 : "); scanf("%d", &n);

    if (n % 2 == 0)
        sum += (1 + n) * ((1 + n) / 2);
    else
        sum += (1 + n) * ((1 + n) / 2) - ((1 + n) / 2);
    
    printf("가우스 덧셈결과 1 ~ %d까지의 합은 %d입니다.", n, sum);

    return 0;
}

Q9

// Q9_ 정수 a,b를 포함하여
// 그 사이의 모든 정수의 합을 구하는 아래 함수.

#include <stdio.h>

int sumof(int a, int b)
{
    int i, sum;
    sum = 0;
    if (a > b)
    {
        for(i = b; i <= a; i++)
        {
            sum += i;
        }
    }
    else
    {
        for(i = a; i <= b; i++)
        {
            sum += i;
        }
    }
    return sum;
}

int main()
{
    int x, y;

    puts("정수 x와 y를 포함한 그 사이의 모든 정수의 합");
    printf("x와 y를 입력하세요 : "); scanf("%d %d", &x, &y);

    printf("%d부터 %d사이의 합은 %d입니다.", x, y, sumof(x,y));


    return 0;
}

Q10

// q10_ 아래와같이. 
// a 의 값 6
// b 의 값 6
// a보다 큰값을 입력하세요!
// b 의 값 8
// b - a 는 2입니다. 를 출력하는 프로그램을 작성하라.

#include <stdio.h>

int main()
{
    int a, b;
    puts("b-a를 구합니다.");
    printf("a 값 : "); scanf("%d", &a);
    do
    {
        printf("b 값 : "); scanf("%d", &b);
        if (b <= a)
            printf("a보다 큰 값을 입력하세요!\n");
    } while(b <= a); // b가 a보다 크거나 같을때까지 반복한다.

    
    printf("%d - %d는 %d입니다.\n", b, a, b-a);

    return 0;
}

Q11

// 양의 정수를 입력하고. 자릿수를 출력하는 프로그램을 작성하라.

#include <stdio.h>

int main()
{
    int a, i;

    puts("자릿수를 출력하는 프로그램");
    
    do
    {
        printf("양의 정수를 입력하세요 : "); scanf("%d", &a);
    }while(a <= 0);

    i = 0;
    
    while(a > 0)
    {
        a /= 10;
        i++;
    }
    
    printf("그 수는 %d자리입니다.", i);

    return 0;
}

Q12

// q12_ 위쪽과 왼쪽에 곱하는 수가 있는 곱셈표를 출력하는 프로그램
// 곱셈표를 출력합니다.
#include <stdio.h>

int main()
{
    int i, j;
    printf("  | ");
    for( i = 1; i <= 9; i++)
        printf("% 2d ", i);
    printf("\n--+----------------------------\n");
    for (i = 1; i <= 9; i++)
    {
        printf("%d |", i);
        for (j = 1; j <= 9; j++)
        {
            printf("% 3d", i * j);
        }
        putchar('\n');
    }

    return 0;
}

Q13

// q13_ 위쪽과 왼쪽에 더하는 수가 있는 덧셈표를 출력하는 프로그램
// 덧셈표를 출력합니다.
#include <stdio.h>

int main()
{
    int i, j;
    printf("  | ");
    for( i = 1; i <= 9; i++)
        printf("% 2d ", i);
    printf("\n--+----------------------------\n");
    for (i = 1; i <= 9; i++)
    {
        printf("%d |", i);
        for (j = 1; j <= 9; j++)
        {
            printf("% 3d", i + j);
        }
        putchar('\n');
    }

    return 0;
}

Q14

// Q14_입력한 수를 한 변으로 하는 정사각형을
// * 기호로 출력하는 프로그램을 작성하시오.

#include <stdio.h>

int main()
{
    int i, j, n;
    puts("사각형을 출력합니다.");
    printf("입력할 수 : "); scanf("%d", &n);

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            putchar('*');
        }
        putchar('\n');
    }
}

Q15

// Q15_입력한 높이와 너비에 맞는 직사각형을
// * 기호로 출력하는 프로그램을 작성하시오.

#include <stdio.h>

int main()
{
    int i, j, h, w;
    puts("직사각형을 출력합니다.");
    printf("높이 : "); scanf("%d", &h);
    printf("너비 : "); scanf("%d", &w);

    for (i = 1; i <= h; i++)
    {
        for (j = 1; j <= w; j++)
        {
            putchar('*');
        }
        putchar('\n');
    }
}

Q16

// Q16_ 직각 이등변 삼각형을 출력하는 부분을 아래와 같은 함수로 작성하시오.
// void triangleLB (int n);
// 또 왼쪽 위, 오른쪽 위, 오른쪽 아래가 직각인 이등변 삼각형을 출력하는 함수도
// 작성하시오.
#include <stdio.h>

void triangleLB (int n)
{
    int i ,j;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= i; j++)
        {
            putchar('*');
        }
        putchar('\n');
    }
}

void triangleLU (int n) // 왼쪽 위가 직각인 이등변 삼각형.
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = n; j >= i; j--)
        {
            putchar('*');
        }
        putchar('\n');
    }
}

void triangleRU (int n) // 오른쪽 위가 직각인 이등변 삼각형.
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j < i; j++)
        {
            putchar(' ');
        }
        for (j = n; j >= i; j--)
        {
            putchar('*');
        }
        putchar('\n');
    }
}
void triangleRB (int n) // 오른쪽 아래가 직각인 이등변 삼각형.
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = n - 1; j >= i; j--)
        {
            putchar(' ');
        }
        for (j = 1; j <= i; j++)
        {
            putchar('*');
        }
        putchar('\n');
    }
}


int main()
{
    int n;
    do
    {
        printf("몇 단 삼각형입니까? : "); scanf("%d", &n);
    }while(n <= 0);

    puts("왼쪽 아래가 직각인 이등변 삼각형");
    triangleLB(n);
    puts("왼쪽 위가 직각인 이등변 삼각형");
    triangleLU(n);
    puts("오른쪽 위가 직각인 이등변 삼각형");
    triangleRU(n);
    puts("오른쪽 아래가 직각인 이등변 삼각형");
    triangleRB(n);    
    return 0;
}

Q17

// Q17_ n단의 피라미드를 출력하는 함수.

#include <stdio.h>

void spira(int n)
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        for (j = n; j >= i; j--)
        {
            putchar(' ');
        }
        for (j = 1; j <= (i - 1) * 2 + 1; j++)
        {
            putchar('*');
        }
        putchar('\n');
    }
}

int main()
{
    int n;
    puts("n단의 피라미드를 출력하는 프로그램.");
    do
    {
        printf("몇단의 피라미드? : "); scanf("%d", &n);
    }while (n <= 0);

    spira(n);

    return 0;
}

Q18

// Q18_오른쪽과 같이 아래를 향한 n단의 피라미드를 출력하는 함수를 작성하시오
// 1111111
//  22222
//   333
//    4

#include <stdio.h>

void nrpira(int n)
{
    int i, j;
    int nx;
    nx = n;
    for (i = 1; i <= nx; i++)
    {
        for (j = 1; j <= i; j++)
        {
            putchar(' ');
        }
        for (j = (n - 1) * 2 + 1; j > 0; j--)
        {
            printf("%d", i % 10);
        }
        putchar('\n');
        --n;
    }
}

int main()
{
    int n;
    puts("n단의 역피라미드를 출력하는 프로그램.");
    do
    {
        printf("몇단의 역피라미드? : "); scanf("%d", &n);
    }while (n <= 0);

    nrpira(n);

    return 0;
}

알고리즘이란?
문제를 해결하기 위한것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합

순서도
알고리즘 문제애 대한 정의.분석.해법을 그림으로 표현하는 순서도(FlowChart)
링크텍스트 여기서 그리면 편하고좋음

반복문
어떤 조건이 성립하는 동안 처리(프로그램 명령문 또는 명령어의 집합)를 반복하여 실행하는 것을 반복구조라 하며 일반적으로는 'Loop(루프)'라 부른다.

while문
실행 전에 반복을 계속할지를 판단한다. 이를 '사전 판단 반복 구조'라고 부른다.
제어식의 평갓값이 0이 아니면 프로그램 명령문이 반복된다.

for문
처음에 제어식을 평가한 결과가 0이면 루프 본문은 실행자체가 안된다. '사전 판단 반복 구조'

구조적 프로그래밍
하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법을 구조적 프로그래밍이라고 ㅎ나다.
구조적 프로그래밍은 순차 - 서택 - 반복이라는 3종류의 제어흐름을 사용한다.

드모르간의 법칙
'각 조건을 부정하고 논리곱(&&)을 논리합(||)으로, 논리합(||)을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같다.'

1. x && y와 !(!x || !y)는 같다.
2. x || y와 !(!x && !y)는 같다.