[1] 알고리즘

알고리즘이란?

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

아무리 정확한 알고리즘이라도 변수의 값에 따라 결과가 달라지는 경우 올바른 알고리즘이라 할 수 없다.

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

 

예시) 중앙값을 찾는 알고리즘

1) 3항 연산자를 활용한 중앙값을 찾는 함수 이용: 직관적임

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
//세 정수의 중앙값을 찾는 알고리즘
int centerval(int a,int b,int c){
    int rst = a;
    if(a>b && a>c) rst = (b>c)?b:c;//3번
    else if(b>a && b>c) rst = (a>c)?a:c;//5번
    else rst = (a>b)?a:b;//5번

    return rst;
}
int main(){
    int val[3] = {},rst;
    printf("세 정수의 중앙값을 구합니다.\n");
    for(int i=0;i<3;i++){printf("%c의 값: ",(97+i));scanf("%d",&val[i]);}
    rst = centerval(val[0],val[1],val[2]);

    printf("중앙값은 %d 입니다.",rst);

}

2) 최적화된 중앙값 분석 코드 (가장 효율적인 코드)

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
//세 정수의 중앙값을 찾는 최적화된 알고리즘
int centerval(int a,int b,int c){
    int rst;
    //1번째 조건문 : 최대 4번
    if(a>=b){//a와 b를 비교하여 a가 더 큰 경우
        if(b>=c) return b;
        //a > b > c -> 중앙값은 b이다.
        else if(a <=c) return a;
        //c > a > b
        else return c;
    }
    //2번째 조건문: 최대 2번
    else if(a>c) return a;//1번째 조건문을 불만족 == a보다 b가 더크다
    /**
    2번째 조건문 ->a보다 b가 더 클 때, a가 c보다 큰 경우
    따라서 중앙값은 a이다.
    >>b > a > c 
     */

    //3번째 조건문: 최대 3번
    else if(b > c) return c;//1번째 조건문과 2번째 조건문을 불만족 => a보다 b가 더크고 c가 a보다 더 크다
    /**
    3번째 조건문에 따라 a보다 b가 더크고 c가 a보다 더 크면서 b가 c보다 크다
    >> b > c > a 따라서 중앙값은 c
     */
    else return b; //모든 경우의 수를 제외하면 남는 것은 b이다.
    //최대 4번

}
int main(){//최대 4번안에 결과값 도출
    
    int a,b,c;
    printf("세 정수의 중앙값을 구합니다.\n");
    printf("a의 값: ");scanf("%d",&a);
    printf("b의 값: ");scanf("%d",&b);
    printf("c의 값: ");scanf("%d",&c);

    int rst = centerval(a,b,c);
    printf("결과값: %d",rst);

}

이처럼 알고리즘을 어떻게 짜냐에 따라 가독성이 좋은 프로그램, 효율성이 좋은 프로그램으로 만들 수 있다.

(1)번 코드와 같은 경우 크게 세 번의 조건문만 확인하면 되므로 코드 분석이 용이한 장점이 있지만, 최대 조건문이 5번 반복되므로 비효율적이다. (2)번 코드는 가독성을 떨어지나 최대 4번으로 보다 효율적인 프로그램 진행이 가능하다.

 

조건 판단과 분기

분기: 동시에 실행되거나 하나도 실행되지 않는 부분이 존재하지 않음.

 

분기

 

순서도의 기호

순서도의 기호

단말	외부 환경으로 나가거나 외부 환경에서 들어오는 것을 나타냄. 예를 들어 프로그램의 흐름의 시작이나 종료를 나타낸다.
처리	여러 종류의 처리기능 수행함. 정보의 값, 자료형, 위치 등을 바꾸거나 연속적인 흐름 중 방향을 결정하는 정의한 연산이나 연산군의 실행을 나타냄.
판단	판단은 하나의 입구와 하나 이상을 선택 할 수 있는 출구가 존재하며, 기호에서 정한 조건을 평가하여 하나의 출구를 정하는 기능을 가짐.
데이터	데이터의 입출력을 나타냄.
루프	루프 범위는 두 부분으로 구성되며 시작과 종료를 나타냄. 예시) i(변수명) : a(초기값), b(증가값), c(종료값)

 

구조적 프로그래밍

• 하나의 입구와 하나의 출구를 가진 구성 요소만을 계층적으로 배치하여 프로그램을 구성하는 방법

구조적 프로그래밍	순차
	선택
	반복

반복

반복의 종류

사전 판단 반복	do while
사후 판단 반복	for
차이점	루프 본문을 최소 한번 이상을 반복함의 차이

드모르간의 법칙

x && y == !( !x ||  !y)
x || y  == !(!x && !y)

 

반복예제: do while

//두 변수 a,b에 정수를 입력하고 b-a를 출력하는 프로그램을 작성하라.
//단 a>b이면 변수 b의 값을 다시 입력해야한다.
#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
int main(){
    int a,b;
    printf("a를 입력하세요: ");scanf("%d",&a);
    do{
        printf("b를 입력하세요: ");scanf("%d",&b);
    }while(a>b);
    printf("결과값은 %d 입니다.",b-a);
}

다중 루프 반복예제: 직각삼각형 그리기

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
//정수 n,m을 입력하고 nxm의 정사각형을 만들어라

void triangleLB(int n){//왼쪽 아래가 직각
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            printf("*");
        }printf("\n");
    }

}

void triangleLU(int n){//왼쪽 위가 직각
    for(int i=n;i>=1;i--){
        for(int j=i;j>=1;j--){
            printf("*");
        }printf("\n");
    }
}

void triangleRB(int n){//오른쪽 아래가 직각
    for(int i=1;i<=n;i++){
        for(int k=0;k<n-i;k++) printf(" ");
        for(int j=1;j<=i;j++)printf("*");
        printf("\n");
    }
}

void triangleRU(int n){//오른쪽 위가 직각
    for(int i=n;i>=1;i--){
        for(int k=0;k<n-i;k++) printf(" ");
        for(int j=1;j<=i;j++)printf("*");
        printf("\n");
    }
}

int main(){
    int n,dir;
    printf("정수 n을 입력하세요: "); scanf("%d",&n);
    printf("직각의 방향을 입력하세요\n우측 상단:1\n우측 하단:2\n좌측 상단:3\n좌측 하단:4\n입력: ");scanf("%d",&dir);
    switch (dir){
    case 1:
        triangleRU(n);
        break;
    case 2:
        triangleRB(n);
        break;
    case 3:
        triangleLU(n);
        break;
    case 4:
        triangleLB(n);
        break;
    }
}