[C] 자료구조와 알고리즘 - Day 1

💻 자료구조와 알고리즘 - Day 1

편입 준비로 인한 기초 다지기 기록 Start!

🤔 기본 알고리즘

1️⃣ 알고리즘이란?

세 값의 최댓값

#include <stdio.h>

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

    printf("세 정수의 최댓값을 구합니다.\n");
    printf("a: "); scanf("%d", &a);
    printf("b: "); scanf("%d", &b);
    printf("c: "); scanf("%d", &c);

    max = a;
    if(b>max) max = b;
    if(c>max) max = c;
    printf("세 정수의 최댓값은 %d입니다.\n", max);

    return 0;
}

• 3개의 정수 값 가운데 최댓값 구하기

1. max에 a 값 대입
2. b 값이 max보다 크면 max에 b 값 대입
3. c 값이 max보다 크면 max에 c 값 대입

• 최댓값을 구하는 과정
  • 세 문장이 아래로 나란히 있다면 이 문장은 순서대로 실행됨
    • 여러 문장(프로세스)이 순차 실행되는 구조 -> 순차적(concatenation) 구조
  • 식의 평가 결과에 따라 프로그램의 실행 흐름을 변경하는 if문 -> 선택(selection) 구조
  • int max = a;
    • 변수를 만드는 시점에 값을 넣는 초기화
  • max = a;
    • 이미 만들어져 있는 변수에 값을 넣는 대입

• 순서도(flowchart)

#include <stdio.h>

int max3(int a, int b, int c) {
    int max = a;
    if(b>max) max = b;
    if(c>max) max = c;
    return max;
}

int main(void) {
    printf("max3(%d, %d, %d) = %d\n", 3, 2, 1, max3(3, 2, 1));
    printf("max3(%d, %d, %d) = %d\n", 3, 2, 2, max3(3, 2, 2));
    printf("max3(%d, %d, %d) = %d\n", 3, 2, 3, max3(3, 2, 3));
    printf("max3(%d, %d, %d) = %d\n", 6, 7, 2, max3(6, 7, 2));
    return 0;
}

• 세 값의 최댓값을 함수로 처리
  • 함수호출식을 평가하면 함수의 반환값을 얻을 수 있음
    • 반환값의 자료형이 void인 함수는 값을 반환하지 않음

중앙값

#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(void) {
    int a, b, c;
    printf("세 정수의 중앙값을 구합니다.\n");
    printf("a: "); scanf("%d", &a);
    printf("b: "); scanf("%d", &b);
    printf("c: "); scanf("%d", &c);
    printf("중앙값: %d\n", med3(a, b, c));
    return 0;
}

• 중앙값을 구하는 절차: 퀵 정렬(Quicksort)

조건 판단과 분기

#include <stdio.h>

int main(void) {
    int n;
    printf("정수 입력: "); scanf("%d", &n);

    // ...
    if(n>0) printf("양수\n"); // 1
    else if(n<0) printf("음수\n"); // 2
    else printf("0\n"); // 3
    // ...

    return 0;
}

• // ... 로 싸여진 부분에서 실행되는 부분은 1, 2, 3 중 하나뿐이며 두 가지가 동시에 실행되거나 하나도 실행되지 않거나 하는 경우는 없음
  • 프로그램의 흐름이 세 가지로 분기하기 때문

• 순서도

순서도의 기호

연산자와 피연산자

• 연산자(operator): 연산을 수행하는 기호
• 피연산자(operand): 연산의 대상이 되는 식
• b > max 에서 연산자는 > 이고, b와 max는 피연산자

단항 연산자(unary operator) ... 피연산자가 1개(a++)
2항 연산자(binary operator) ... 피연산자가 2개(a<b)
3항 연산자(ternary operator) ... 피연산자가 3개(a?b:c)

식(expression)

변수
상수
변수나 상수를 연산자로 결합한 것

• x=n+135
  • 변수 x와 n은 int형
  • x, n, 135, n+135, x=n+135 는 모두 식
• xx연산자와 피연산자가 결합한 식 -> xx식
  • 대입 연산자에 의해 x 와 n+135 가 결합된 식 -> 대입식(assignment expression)

식의 평가

• 프로그램을 실행할 때 식이 평가됨
• 모든 수식에는 값이 있으며 그 값은 프로그램을 실행할 때 확인할 수 있음
  • 평가(evaluation): 식의 값을 알아내는 것

관계 연산자와 등가 연산자

• 왼쪽과 오른쪽 피연산자의 대소 관계를 판단하는 관계 연산자
  • <, <=, >, >=
• 값이 같은지의 관계를 판단하는 등가 연산자
  • ==, !=
• 참이면 int형 1, 거짓이면 int형 0

매개변수(parameter) 또는 형식 매개변수(foraml parameter)

• 함수를 정의할 때 함수에 전달되는 값을 저장하기 위한 변수(variable)
• 함수를 정의할 때는 매개변수, 함수를 호출할 때는 실인수(actual argument)

알고리즘(algorithm)

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

세 값의 대소 관계

• 결정 트리(decision tree)
  • 세 값의 대소 관계의 조합은 13가지 종류
  • 조합을 나열한 모양이 나무 형태

조건 연산자

• 3개의 피연산자를 갖는 3항 연산자를 조건 연산자(conditional operator) 라고 함
  • ?, :
• min a<b?a:b;
  • 변수 min에 대입되는 값은 a가 b보다 작으면 a, 그렇지 않으면 b

연습문제

Q1. 네 값의 최댓값을 구하는 함수 max4를 작성하라

Q2. 세 값의 최솟값을 구하는 min3 함수를 작성하라

Q3. 네 값의 최솟값을 구하는 min4 함수를 작성하라

#include <stdio.h>

int max4(int a, int b, int c, int d) {
    int max = a;
    if(b>max) max = b;
    if(c>max) max = c;
    if(d>max) max = d;
    return max;
}

int min3(int a, int b, int c) {
    int min = a;
    if(b<min) min = b;
    if(c<min) min = c;
    return min;
}

int min4(int a, int b, int c, int d) {
    int min = a;
    if(b<min) min = b;
    if(c<min) min = c;
    if(d<min) min = d;
    return min;
}

int main(void) {
    printf("max4(%d, %d, %d, %d) = %d\n",
    15, 18, 4, 7, max4(15, 18, 4, 7));
    printf("min3(%d, %d, %d) = %d\n",
    15, 18, 4, min3(15, 18, 4));
    printf("min4(%d, %d, %d, %d) = %d\n",
    15, 18, 4, 7, min4(15, 18, 4, 7));
    return 0;
}

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(void) {
    int a, b, c;
    printf("med3(%d, %d, %d) = %d\n", 3, 2, 1, med3(3, 2, 1)); // a>b>c
    printf("med3(%d, %d, %d) = %d\n", 3, 2, 2, med3(3, 2, 2)); // a>b=c
    printf("med3(%d, %d, %d) = %d\n", 3, 1, 2, med3(3, 1, 2)); // a>c>b
    printf("med3(%d, %d, %d) = %d\n", 3, 2, 3, med3(3, 2, 3)); // a=c>b
    printf("med3(%d, %d, %d) = %d\n", 2, 1, 3, med3(2, 1, 3)); // c>a>b
    printf("med3(%d, %d, %d) = %d\n", 3, 3, 2, med3(3, 3, 2)); // a=b>c
    printf("med3(%d, %d, %d) = %d\n", 3, 3, 3, med3(3, 3, 3)); // a=b=c
    printf("med3(%d, %d, %d) = %d\n", 2, 2, 3, med3(2, 2, 3)); // c>a=b
    printf("med3(%d, %d, %d) = %d\n", 2, 3, 1, med3(2, 3, 1)); // b>a>c
    printf("med3(%d, %d, %d) = %d\n", 2, 3, 2, med3(2, 3, 2)); // b>a=c
    printf("med3(%d, %d, %d) = %d\n", 1, 3, 2, med3(1, 3, 2)); // b>c>a
    printf("med3(%d, %d, %d) = %d\n", 2, 3, 3, med3(2, 3, 3)); // b=c>a
    printf("med3(%d, %d, %d) = %d\n", 1, 2, 3, med3(1, 2, 3)); // c>b>a
    return 0;
}

Q5. 중앙값을 구하는 함수는 다음과 같이 작성할 수도 있음. 그러나 med3.c에서의 med3 함수에 비해 효율이 떨어지는데, 그 이유 설명하라

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

• My Answer: med3.c의 med3 함수는 많으면 4번의 조건절에 걸리는데 해당 함수는 무조건 4번의 조건절에 걸리기 때문에 시간적으로 불리하다.

/*
첫 if 문의 다음 판정에 주목합니다.
    if ((b >= a && c<= a) || (b <= a && c >= a)
여기서 b>=a 및 b<=a의 판정을 뒤집는 판정(실질적으로 동일한 판정)이, 뒤이은 else 이후에 다음과 같이 수행됩니다.
    else if ((a > b && c < b) || (a < b && c > b)
즉, 첫 번째 if 문이 성립되지 않은 경우, 두 번째 if 문에서도 (실질적으로) 같은 판정을 하므로 효율이 나빠집니다.
*/

• Correct Answer

2️⃣ 반복

1부터 N까지의 정수 합 구하기 - while문 반복

#include <stdio.h>

int main(void) {
    int i=1, n;
    int sum=0;
    printf("1부터 n까지의 합을 구합니다.\n");
    printf("n 입력: "); scanf("%d", &n);
    while(i<=n) {
        sum+=i;
        i++;
    }
    printf("1부터 %d까지의 합: %d\n", n, sum);
    return 0;
}

while(제어식) 명령문

• 반복(repetition) 구조 or 루프(loop): 어떤 조건이 성립하는 동안 처리(프로그램 명령문 또는 명령어의 집합)를 반복하여 실행하는 것
• while문은 실행 전에 반복을 계속할지를 판단함 -> 사전 판단 반복 구조
  • 제어식의 평갓값이 0이 아니면 프로그램 명령문이 계속 반복됨

• 순서도

1부터 N까지의 정수 합 구하기 - for문 반복

#include <stdio.h>

int main(void) {
    int n;
    int sum=0;
    printf("1부터 n까지의 합을 구합니다.\n");
    printf("n 입력: "); scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        sum+=i;
    }
    printf("1부터 %d까지의 합: %d\n", n, sum);
    return 0;
}

for(식1; 식2; 식3) 명령문

• 하나의 변수를 사용하는 반복문은 while문보다 for문을 사용하는 것이 적합함
  • 식1은 반복을 실행하기 앞서 처음 한 번만 실행됨
  • 제어식인 식2를 평가한 값이 0이 아니면 루프 본문이 반복하여 실행됨
  • 식3이 평가, 실행됨

• 순서도

양수만 입력하기

#include <stdio.h>

int main(void) {
    int n, sum=0;
    printf("1부터 n까지의 합을 구합니다.\n");
    do {
        printf("n 입력: "); scanf("%d", &n);
    } while(n<=0);
    for(int i=1; i<=n; i++) {
        sum+=i;
    }
    printf("1부터 %d까지의 합: %d\n", n, sum);
    return 0;
}

do문 while(제어식);

• do문은 일단 루프 본문을 한 번 실행한 다음 계속 반복할 것인지를 판단하는 사후 판단 반복문
  • 제어식을 평가한 값이 0이 아니면 루프 본문의 명령문이 반복됨

• 순서도

구조적 프로그래밍(structured programming)

• 하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법
  • 순차, 선택, 반복이라는 3종류의 제어 흐름 사용

다중 루프

#include <stdio.h>

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

• 순서도

논리 연산과 드모르간 법칙

#include <stdio.h>

int main(void) {
    int n;
    do {
        printf("2자리 정수 n 입력: "); scanf("%d", &n);
    } while(n<10||n>99);
    printf("n = %d\n", n);
    return 0;
}

• x&&y: 논리곱(and)
  • 둘 다 참이면 참
• x||y: 논리합(or)
  • 하나라도 참이면 참
• 논리 연산자의 단축 평가(short circuit evaluation)
  • 논리 연산의 식 전체를 평가한 결과가 왼쪽 피연산자의 평가 결과만으로 정확해지는 경우 오른쪽 피연산자의 평가를 수행하지 않는 것

x&&y와 !(!x||!y)는 동일하다
x||y와 !(!x&&!y)는 동일하다

• 드모르간 법칙(De Morgan's laws)
  • 각 조건을 부정하고 논리곱을 논리합으로, 논리합을 논리곱으로 바꾸고 다시 전체를 부정하면 원래의 조건과 같음
  • 즉, n<10||n>99는 !(n>=10&&n<=99)와 같음

직각 이등변 삼각형 출력

#include <stdio.h>

int main(void) {
    int height;
    do {
        printf("몇 단 삼각형입니까?: "); scanf("%d", &height);
    } while(height<=0);
    for(int i=1; i<=height; i++) {
        for(int j=1; j<=i; j++)
            putchar('*');
        putchar('\n');
    }
}

• 순서도

0이 아니면 참이고 0이면 거짓

if(a) printf("ABC");

• 변수 a의 값이 0이 아니기만 하면(1이든 100이든 -2도 모두) 'ABC' 출력
  • C 언어에서는 0은 거짓, 0이 아닌 모든 값은 참으로 간주

사전 판단 반복과 사후 판단 반복의 차이점

• 사전 판단 반복문인 while문과 for문은 처음에 제어식을 평가한 결과가 0이면 루프 본문은 한 번도 실행되지 않음
• 사후 판단 반복문인 do문은 루프 본문이 반드시 한 번은 실행됨

연습문제

Q7. 실습 1-5를 참고하여 n이 7이면 '1 + 2 + 3 + ... + 7 = 28'로 출력하는 프로그램을 작성하라

Q8. 1부터 10까지의 합은 (1+10)*5와 같은 방법으로 구할 수 있다. 가우스의 덧셈이라는 이 방법을 이용하여 1부터 n까지의 정수 합을 구하는 프로그램을 작성하라

Q9. 정수 a, b를 포함하여 그 사이의 모든 정수의 합을 구하는 sumof 함수를 작성하라(a와 b의 대소 관계에 상관없이 합을 구하라)

#include <stdio.h>

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

void q8(int n) {
    int sum;
    if(n%2==0) sum=(1+n)*(n/2);
    else sum=(1+(n-1))*((n-1)/2)+n;
    printf("1부터 %d까지의 합: %d\n", n, sum);
}

void sumof(int a, int b) {
    int big, small, sum=0;
    if(a>=b) {
        big=a; small=b;
    }
    else {
        big=b; small=a;
    }
    for(int i=small; i<=big; i++) {
        sum+=i;
    }
    printf("%d부터 %d까지의 합: %d\n", small, big, sum);
}

int main(void) {
    int n;
    printf("1부터 n까지의 합을 구합니다.\n");
    printf("n의 값: "); scanf("%d", &n);
    q7(n);
    q8(n);
    int a, b;
    printf("a의 값: "); scanf("%d", &a);
    printf("b의 값: "); scanf("%d", &b);
    sumof(a, b);
    return 0;
}

Q10. 두 변수 a, b에 정수를 입력하고 b-a를 출력하는 프로그램을 작성하라(변수 b에 입력한 값이 a 이하면 변수 b의 값을 다시 입력)

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

void q10() {
    int a, b;
    printf("a의 값: "); scanf("%d", &a);
    do {
        printf("b의 값: "); scanf("%d", &b);
        if(a>=b) printf("a보다 큰 값을 입력하세요!\n");
    } while(a>=b);
    printf("b-a = %d\n", b-a);
}

void q11() {
    int num, digits=0;
    do {
        printf("값: "); scanf("%d", &num);
    } while(num<=0);
    while(num>0) {
        num/=10;
        digits++;
    }
    printf("그 수는 %d자리입니다.\n", digits);
}

Q12. 위쪽과 왼쪽에 곱하는 수가 있는 곱셈표를 출력하는 프로그램을 작성하라(구분선은 수직선, 마이너스, 플러스 기호 사용)

Q13. 곱셈이 아니라 덧셈을 출력하는 프로그램을 작성하라

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

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

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

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

void q14() {
    int side;
    printf("사각형을 출력합니다.\n"); 
    printf("입력 수: "); scanf("%d", &side);
    for(int i=1; i<=side; i++) {
        for(int j=1; j<=side; j++)
            putchar('*');
        putchar('\n');
    }
}

void q15() {
    int width, height;
    printf("사각형을 출력합니다.\n");
    printf("높이: "); scanf("%d", &height);
    printf("너비: "); scanf("%d", &width);
    for(int i=1; i<=height; i++) {
        for(int j=1; j<=width; j++)
            putchar('*');
        putchar('\n');
    }
}

Q16. 왼쪽 아래, 왼쪽 위, 오른쪽 위, 오른쪽 아래가 직각인 이등변 삼각형을 출력하는 함수를 각각 작성하라

Q17. n단의 피라미드를 출력하는 함수를 작성하라

Q18. 아래를 향한 n단의 숫자 피라미드를 출력하는 함수를 작성하라

void triangleLB() {
    int height;
    do {
        printf("몇 단 삼각형입니까?: "); scanf("%d", &height);
    } while(height<=0);
    for(int i=1; i<=height; i++) {
        for(int j=1; j<=i; j++)
            putchar('*');
        putchar('\n');
    }
}

void triangleLU() {
    int height;
    do {
        printf("몇 단 삼각형입니까?: "); scanf("%d", &height);
    } while(height<=0);
    for(int i=height; i>=1; i--) {
        for(int j=1; j<=i; j++)
            putchar('*');
        putchar('\n');
    }
}

void triangleRU() {
    int height;
    do {
        printf("몇 단 삼각형입니까?: "); scanf("%d", &height);
    } while(height<=0);
    for(int i=height; i>=1; i--) {
        for(int j=1; j<=height; j++) {
            if((height-i)>=j) putchar(' ');
            else putchar('*');
        }
        putchar('\n');
    }
}

void triangleRB() {
    int height;
    do {
        printf("몇 단 삼각형입니까?: "); scanf("%d", &height);
    } while(height<=0);
    for(int i=1; i<=height; i++) {
        for(int j=1; j<=height; j++) {
            if((height-i)<j) putchar('*');
            else putchar(' ');
        }
        putchar('\n');
    }
}

void spira(int n) {
    int max = (n-1)*2+1;
    int half = max/2+1;
    for(int i=0; i<n; i++) {
        for(int j=1; j<=max; j++) {
            if((half-i)<=j&&(half+i)>=j) putchar('*');
            else putchar(' ');
        }
        putchar('\n');
    }
}

void nrpira(int n) {
    int max = (n-1)*2+1;
    int half = max/2+1;
    for(int i=n-1; i>=0; i--) {
        for(int j=1; j<=max; j++) {
            if((half-i)<=j&&(half+i)>=j) printf("%d", half-i);
            else putchar(' ');
        }
        putchar('\n');
    }
}