정보처리기사 실기 알고리즘 정리 04

03 Aug 2018

Reading time ~10 minutes

정보처리기사 실기 알고리즘 정리 04

10개의 수치 자료를 입력 받아 배열에 저장한 후 저장된 자료를 오름차순으로 정렬하는 순서도를 작성하시오
(삽입 정렬)

알고리즘의 이해

삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘.
즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾음.
자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킴.
변수
- a[10] : 정렬할 숫자가 저장될 배열
- j : 입력 받은 숫자의 개수가 저장될 배열
- i : 정렬 회전 수, key 값의 위치를 지정해 주는 변수, 즉 i는 2부터 10까지 차례로 변경됨
- k : 비교 대상이 있는 위치를 지정해 주는 변수, 즉 k는 i-1에서 i까지 차례로 변경됨
- key : 비교 기준인 key 값이 저장될 변수

main() {
  int j, i, k, key;
  int a[10];

  j = -1;

  do {
    j++;
    scanf("%d", &a[j]);
  } while(j < 9);

  for (i = 1; i <= 9; i++) {          // i는 정렬 회전수(기준값 인덱스)

    key = a[i];                       // 비교 기준 key. 2부터 시작함

    for (k = i - 1; k >= 0; k--) {    // 왼쪽에 있는 수를 비교, 비교대상을 가리키는 k

      if (a[k] > key)                 // 왼쪽에 더 기준보다 큰수가 있다면
        a[k + 1] = a[k];              // 비교대상을 오른쪽칸으로 이동시킴
      else                            // 왼쪽 비교 대상이 키값보다 작으면
        break;                        // 비교안하고 빠져나옴
    }

    a[k + 1] = key;   // 비교대상(왼쪽)값 바로 우측칸이 삽입될 위치, 그 자리에 기준값 삽입
  }

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

}

if 문을 이용한 삽입 정렬

main() {

  int i, k, key;
  int a[20] = {
    9,7,4,6,3,1,8,2,5,10,19,17,14,16,13,11,18,12,15,20
  };

  i = 1;              // 2번째 요소부터 기준으로 비교

  do {

    key = a[i];       // 2번째 값을 key에 저장하고
    k = i - 1;        // 기준 왼쪽을 비교할 인덱스 k

    do {

      if (key < a[k]) {            // key값이 왼쪽 값보다 작으면 정렬해야지
        a[k+1] = a[k];             // 왼쪽에 있던 값을 오른쪽에 옮김.
        k--;                        // 옮기고 비교 대상을 왼쪽으로 한칸 이동
      } else {                     // 왼쪽에 비교대상이 현재 기준값보다 작으면
        break;                     // 빠져나옴.
      }

    } while(k >= 0);

    a[k+1] = key;                  // 해당 비교대상 + 1(우측)에 기준값을 넣음(제자리)
    i++;                           // 기준값 인덱스를 올림.

  } while(i <= 19);

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

10명의 학생에 대한 중간고사 점수의 석차를 구하는 순서도를작성하시오.
(석차 구하기 - 배열 이용)

알고리즘의 이해

특정인 점수에 대한 석차를 알려면 다른 사람들과 점수를 비교해 보면 됨.
다른 사람들과 비교 전엔 1등이고, 비교하며 점수가 높은 사람이 있으면 석차를 1씩 증가시킴.
여러 사람의 석차를 계산한다면 이런 작업을 모든 사람에게 반복해 적용하면 됨.
변수
- score[10] : 입력 받은 점수가 저장될 배열
- m : 입력 받은 점수의 개수가 저장될 변수(점수를 입력 받을 때 사용)
- rank[10] : 석차가 저장될 배열
- n : 입력 받은 점수의 개수가 저장될 변수(석차를 구하는 과정에서 사용)
- i : 회전 수, 석차를 구할 점수가 있는 위치를 지정해 주는 변수
- j : 각 회전에서의 비교 횟수, 비교 대상 점수가 있는 위치를 지정해 주는 변수

main() {

  int m, n, i, j;
  int score[10], rank[10];

  m = -1;
  do {
    m++;
    scanf("%d", &score[m]);
  } while(m < 9);

  n = 9;
  i = 0;
  while (i <= n) {
    rank[i] = 1;                  // 모든 등수를 1로 초기화
    i++;
  }

  i = 0;                          // 회전수 i, 비교 기준 인덱스
  while (i <= n) {
    j = 0;                        // 비교 대상 인덱스 j
    while (j <= n) {    
      if (score[i] < score[j])    // 비교대상의 점수가 더 높으면 기준의 등수를 올림.
        rank[i]++;
      j++;
    }
    i++;
  }

  for (int x = 0; x < 10; x++)
    printf("%d ", score[x]);
  printf(" \n");
  for (int x = 0; x < 10; x++)
    printf("%d ", rank[x]);
}

10명 학생의 국어, 수학 점수를 각각 입력 받아 총점을 계산한 후 총점 기준 내림차순으로 순위를 출력하는 순서도를 작성하시오. 단, 동점은 동석차로 하고 총점이 0인 경우는 출력하지 않음.
(석차구하기 - 바로 출력)

알고리즘의 이해

유형 1과 다른 점은 석차를 배열에 넣지 않고 바로 출력한다는 것.
즉, 어떤 사람의 석차가 1등이라 가정하고 다른 사람들과 비교하면 석차를 계산 후 점수와 함께 바로 출력한다.
석차를 매길 사람이 10명이라면 이런 일은 10번 반복.
변수
- kor[10] : 국어 점수가 저장될 변수
- mat[10] : 수학 점수가 저장될 변수
- sum[10] : 국어와 수학 점수의 합계가 저장될 배열
- i : 입력 받은 자료의 개수가 저장될 변수, 비교 기준 점수의 위치를 지정해 주는 변수(회전수)
- j : 비교 대상의 위치를 지정해 주는 변수, 각 회전에서의 비교수
- rank: 석차가 계산되어 저장될 변수

main() {

  int i, j, rank;   // i는 비교 기준 인덱스, j는 비교 대상 인덱스
  int kor[10], mat[10], sum[10];

  i = -1;

  do {
    i++;
    scanf("%d %d", &kor[i], &mat[i]);
    sum[i] = kor[i] + mat[i];
  } while(i < 9);

  for (i = 0; i <= 9; i++) {
    if (sum[i] != 0) {
      rank = 1;                        // 현재 비교 기준 i의 등수를 1로 초기화
      for (j = 0; j <= 9; j++) {       // 비교대상보다 점수가 낮으면 등수를 올림
        if (sum[i] < sum[j])
          rank++;
      }
      printf("%d %d %d %d %d\n", i + 1, kor[i], mat[i], sum[i], rank);
    }
  }
}

키보드로 입력 받은 값이 data배열의 몇 번째에 기억되어 있는지 알아보기 위해 출력하는 순서도를 작성하시오. 단 data[10] 배열에는 10개의 숫자가 들어 있으며, 찾는 자료가 없을 경우 자료와 함께 ‘not found’를 출력하고 끝냄.
(이분 검색 - 1차원 배열)

알고리즘의 이해

이분 검색은 말 그대로 검색할 자료를 반씩 나누어서 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 것.
- 빠른 속도로 자료를 찾을 수 있다.
- 자료의 범위를 반씩 줄여 가는 것이므로 최대 검색 횟수는 log2N
  - 자료가 100건일 때 , log₂100 = log₂2^6.xx = 6회. 100만건이라도 19번만 검색하면 찾을 수 있음.
단, 이분 검색은 데이터가 정렬되어 있어야 작업이 가능하다.
끝나는 조건은 자료의 범위를 좁혀오다 시작 위치가 끝 위치보다 커지면 해당 자료가 없는 것.
변수
- data[10] : 입력 받은 숫자가 저장될 배열
- input : 입력 받은 찾을 값이 저장될 변수
- start : 검색 범위의 시작 위치를 지정해 주는 변수
- last : 검색 범위의 마지막 위치를 지정해 주는 변수
- m : 검색 위치의 중간 위치가 저장될 변수

main() {
  int input, start, last, m;
  int data[10] = {8,15,35,60,61,70,80,92,99};

  scanf("%d", &input);

  start = 0;                              // 탐색 범위 0~
  last = 9;                               // 탐색 범위 ~9

  while (1) {
    if (start <= last) {                  // 탐색 시작 인덱스가 끝 인덱스보다 커지면 없는거
      m = (start + last) / 2;             // 가운데 인덱스 찾음

      if (input == data[m]) {             // 입력 값과 비교, 동일하면 출력(값, 인덱스 위치))
        printf("%d %d", input, m + 1);
        break;
      }
      if (input < data[m])                // 입력값이 가운데 값보다 작으면
        last = m - 1;                     // 가운데 인덱스보다 왼쪽 탐색
      else
        start = m + 1;                    // 가운데 값보다 크면 가운데 인덱스보다 오른쪽 탐색
    } else {                          
      printf("%d NOT FOUND", input);      
      break;
    }
  }
}

키보드로 입력 받은 번호에 대한 점수를 data 배열에서 찾아 출력하는 순서도를 작성하시오. 단 data[2][10] 배열에는 번호와 점수가 들어 있다고 가정하고, 찾는 자료가 없을 경우 자료와 함께 “NOT FOUND”를 출력하고 끝낸다.
(이분 검색 - 2차원 배열)

알고리즘의 이해

2차원 배열 1행에는 학생 번호가, 2행에는 학생 점수가 저장되어 있다.
변수
- data[2][10] : 자료가 저장될 2차원 배열
- input : 찾을 번호가 저장될 변수
- start : 검색 범위의 시작 위치를 지정해 주는 변수
- last : 검색 범위의 마지막 위치를 지정해 주는 변수
- m : 검색 범위의 중간 위치가 저장될 변수

main() {

  int input, start, last, m;
  int data[2][10] = {
    {1,2,3,4,5,6,7,8,9,10},
    {100,66,25,88,90,65,87,86,58,99}
  };

  scanf("%d", &input);

  start = 0;
  last = 9;

  while (1) {
    if (start <= last) {
      m = (start + last) / 2;

      if (input == data[0][m]) {                // 입력 받은 값과 학생번호의 값이 같은지 확인
        printf("%d %d\n", input, data[1][m]);   // 같으면 점수 결과 출력.
        break;
      }
      if (input < data[0][m])
        last = m - 1;
      else
        start = m + 1;

    } else {
      printf("%d NOT FOUND", input);
      break;
    }
  }
}

다음 처리 조건에 맞게 병합하는 순서도를 작성하시오(병합(MERGE))

처리 조건

배열 A, B에는 정수가 오름차순으로 정렬되어 있다.
데이터는 10건 미만이다.
배열 A, B에서 0이 들어 있는 다음 요소에는 데이터가 없는 것으로 간주한다.
배열 A, B를 병합시켜 배열 C에 기억시키고 맨 마지막에는 0을 기억시킨다.
배열 A와 B에 같은 데이터가 있으면 한 번만 C에 옮긴다.

예)
- A[10] : 1, 3, 5, 6, 0
- B[10] : 2, 3, 5, 8, 9, 10, 12, 13, 0
- C[20] : 1, 2, 3, 5, 6, 8, 9, 10, 12, 13, 0

알고리즘의 이해

병합은 정렬된 2개의 파일 또는 배열을 하나의 정렬된 자료로 만드는 것.
배열을 이용할 때는 자료의 크기가 작은 쪽의 배열 첨자를 증가시키면서 2개의 배열을 1개로 합친다.
병합을 수행할 때는 병합할 두 자료의 대소를 비교하여 클때, 같을 때, 작을 때를 구분하여 처리하면 됨.
- 두 배열을 합치므로 20짜리 c배열 필요
- a, b, c의 위치를 가리키는 변수 사용
- a의 값 < b의 값
  - a의 값을 c에 넣고 a와 c ++ 1
- a의 값 == b의 값
  - 둘 중 한개의 값만 c에 넣고 a, b둘다 ++1
- a의 값 > b의 값
  - b의 값을 c에 넣고 b와 c ++1
- 0이면 배열의 끝이므로 한 배열이 끝나면 나머지 배열의 값을 모두 넣고 0을 붙여 끝을 알림
변수
- a[10] : 병합할 자료가 들어 있는 배열
- b[10] : 병합할 자료가 들어 있는 배열
- c[20] : 2개의 배열을 병합할 자료가 들어갈 배열
- c_index : 배열 c의 위치를 지정해 주는 변수
- a_index : 배열 a의 위치를 지정해 주는 변수
- b_index : 배열 b의 위치를 지정해 주는 변수

#include <stdio.h>
#include <stdlib.h> // exit(), atoi(), atof()함수가 정의되어 있는 헤더

void fillA(a, c);  // b 요소가 0일 때, 남은 a 배열 값으로 c를 채우는 함수
void fillB(b, c);  // a 요소가 0일 때, 남은 b 배열 값으로 c를 채우는 함수
void finishC(c);   // fillA, fillB가 끝나고 c배열에 0을 붙여주는 함수

int a_index, b_index, c_index;

main() {
  int a[10] = {2,3,5,8,9,10,12,13,0};
  int b[10] = {1,3,5,6,0};
  int c[20];
  a_index = 0;
  b_index = 0;
  c_index = -1;

  while (1) {
    c_index++;

    if (a[a_index] < b[b_index]) {     // a값이 b의 값보다 작으면 c에 넣고 a, c인덱스 증가

      c[c_index] = a[a_index];
      a_index++;

      if (a[a_index] == 0)
        fillB(b, c);

    } else if (a[a_index] == b[b_index]) {// 두 값이 같으면, a의 값 저장, a,b 두 인덱스 증가

      c[c_index] = a[a_index];          
      a_index++;
      b_index++;

      if (a[a_index] == 0)
        fillB(b, c);
      else if (b[b_index] == 0)
        fillA(a, c);    

    } else {                      // b의 값이 a값보다 작을 때 b를 c에 넣고 b, c인덱스 증가

      c[c_index] = b[b_index];
      b_index++;

      if (b[b_index] == 0)
        fillA(a, c);

    }
  }
}

void fillB(int b[10], int c[10]) {

  if (b[b_index] == 0)
    finishC(c);

  do {
    c_index++;
    c[c_index] = b[b_index];
    b_index++;
  } while(b[b_index] != 0);

  finishC(c);
}

void fillA(int a[10], int c[10]) {

  do {
    c_index++;
    c[c_index] = a[a_index];
    a_index++;  

  } while(a[a_index] != 0);

  finishC(c);
}

void finishC(int c[10]) {
  c_index++;
  c[c_index] = 0;

  for (int i = 0; i < 20; i++) {

    if (c[i] == 0)
      break;

    printf("%d ", c[i]);
  }
  exit(0);
}

10 개의 요소를 갖는 1차원 배열을 스택으로 이용하는 순서도를 작성하시오. 입출력되는 데이터가 스택의 크기보다 커지면 “Overflow”를 출력하고, 제거할 데이터가 없으면 “Underflow”를 출력한다.
(스택(stack))

스택은 한쪽 끝으로만 자료의 삽입과 삭제가 이루어지는 자료구조.
배열을 이용해 단순 스택을 구성할 때는 배열의 가장 마지막에 삽입된 자료의 위치, 즉 스택 포인터의 위치를 이용하여 입력과 제거를 수행.
스택에 자료를 삽입하는 작업을 push라 하고, 스택에서 자료를 제거하는 작업을 pop이라 함.
변수
- stack[5] : 스택으로 이용할 배열
- top : 스택 포인터로 값을 저장할 스택의 위치를 기억하는 변수
- i : 입력할 값, 제거한 값, overflow, underflow 등을 확인하는 다용도 변수
- select : 입력 또는 삭제를 선택할 변수(1이면 삽입(push), 2이면 삭제(pop))
- input : 스택에 저장될 자료를 입력 받을 변수
- push_val : push 함수에서 k의 값을 받을 변수
- pop_val : pop 함수에서 스택에서 제거된 자료를 기억할 변수

#include<stdio.h>
#define MAX 5  // 숫자 5를 MAX로 정의

int stack[MAX];
int top = -1;

int push(int push_val) {

  top++;
  if (top >= MAX) {

    printf("OverFlow!\n");
    top--;
    return -1;
  }

  stack[top] = push_val;
  return 0;
}

int pop(void) {
  
  int pop_val;
  if (top < 0) {

    printf("UnderFlow!\n");
    return -1;
  }
  pop_val = stack[top];
  top--;
  return pop_val;
}

main() {
  while (1) {

    int i, select, input;
    printf("작업을 선택하세요 : (1)삽입, (2)삭제 : ");
    scanf("%d", &select);

    if (select == 1) {

      printf("삽입할 숫자를 입력하세요 : ");
      scanf("%d", &input);

      i = push(input);
      if (i == -1) break;

    } else if (select == 2) {

      i = pop();
      if (i == -1) break;

      else
        printf("제거된 자료는 %d입니다. \n", i);

    } else break;
  }

  if (top < 0)
    printf("스택에 자료가 없습니다.\n");
  else {
    printf("스택의 자료는 다음과 같습니다.\n");
    for (int i = top; i >= 0; i--)
      printf("%10d ", stack[i]);
  }
}

정보처리기사실기