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

04 Aug 2018

Reading time ~8 minutes

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

10진수를 입력 받아 2진수, 8진수, 16진수로 변환해서 출력하시오. 단, 진수 표시에 사용될 0~9, A, B, C, D, E, F는 A[16]배열에 저장되어 있다고 가정한다.
(10진수를 임의의 변수로 변환하기)

알고리즘의 이해

이 방법은 10진수를 변환하려는 진수의 가장 가까운 누승(거듭제곱)부터 1까지 차례대로 나누는 방법. 진수에 관계없이 모든 진법 변환에 사용 가능
- 예를 들어 31을 2진수로 변환할 경우 누승이 16+8+4+2+1 = 2⁴ + 2³ + 2²+ 2¹+ 2⁰으로 구성되어 있으므로 31을 첫 번째 누승인 16으로 나누어 몫과 나머지를 구하면 이 때의 몫 1은 24을 의미하고 나머지는 15다. 다시 나머지 15를 두 번째 누승인 8로 나누어 몫과 나머지를 구하면 이때 몫 1은 23을 의미하고 나머지는 7이다. 이런 방법으로 20(1)로 나눌 떄까지 차례대로 반복하면 됨.
2진수로 변환하기 때문에 2의 누승으로 나눔. 8진수면 8의 누승, 16진수면 16의 누승으로 나눔.
- 예로 87을 8진수로 변환한다면 8²(64), 8¹(8), 8⁰(1)으로 나눔
  - 87/64 = 몫1, 나머지23
  - 23/8 = 몫2, 나머지 7
  - 7/1 몫7
  - 제수가 1이면 종료
  - (87)₁₀ -> (127)₈
변수
- a[16] : 0~9, A~F까지 저장되어 있는 1차원 배열
- b : 변환할 진수의 밑(base)이 저장될 변수(2~16 중 하나가 저장됨)
  - 베이스 : 진수의 밑을 말함, 2진수는 2가 베이스, 8진수는 8이 베이스.
- c : 10진수가 저장될 변수
- d : c에 가장 가까운 b의 누승이 저장될 변수(제수)
- e : c를 d로 나눈 몫이 저장될 변수
- f : c를 d로 나눈 나머지가 저장될 변수

int main() {

  int b, c, d, e, f;
  char a[16] = { 
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
    'A', 'B', 'C', 'D', 'E', 'F'
  };

  printf("진법과 10진수 수를 입력 : ");
  scanf("%d %d", &b, &c);
  
  d = 1;
  while (d <= c)            // c와 가까워질때까지
    d *= b;                 // 진수값을 곱해 c보다 큰 누승을 구함

  while (1) {
    if (d > 1)              
      d /= b;               // b로 나눠 c와 가장 가까운 누승을 구함
    e = c / d;              // 몫
    f = c - e * d;          // 나머지

    printf(" %c ", a[e]);   

    if (d != 1)             // 제수가 1이 아니면 나머지를 피제수로 놓고 반복
      c = f;      
      else
      break;

  }

  return 0;
}

입력받은 10진수에 가장 가까운 2의 누승 구하기
- 1에 2를 계속 곱하다가 원하는 수보다 커지면 다시 2로 나눔.
  - 예) 26, 1x2x2x2x2x2/2 = 16
몫을 출력할 때 왜 문자가 들어있는 배열을 사용?
- 16진수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F를 사용하므로 0~9까지의 숫자만 사용해 모든 문자를 표시할 수 없음
- 16개짜리 배열에 16진수에 사용할 숫자와 문자를 저장해 놓고 필요한 문자를 출력.
  - 예를들어 몫이 10이라면 11번째에 있는 값 A를 출력, 몫이 1이라면 2번째에 있는 즉 몫+1번째에 있는 값을 출력

10자리로 구성된 2진수를 입력 받아 10진수로 변환하여 출력하시오. 단, 10자리 2진수는 문자열로 되어 있고, 5번째 자리까지는 소수 이상이고, 6번째 자리부터 10번째 자리까지는 소수 이하를 의미한다.
(진법 변환 - 소수점이 포함된 2진수를 10진수로 변환하기)

알고리즘의 이해

예를 들어 입력받은 문자열이 ‘1010111011’이라면 각 자릿수의 의미는 다음과 같음
- 1 : 1 * 2⁴
- 0 : 0 * 2³
- 1 : 1 * 2²
- 0 : 0 * 2¹
- 1 : 1 * 2⁰
- .
- 1 : 1 * 2^-1
- 1 : 1 * 2^-2
- 0 : 0 * 2^-3
- 1 : 1 * 2^-4
- 1 : 1 * 2^-5
첫 번째 문자는 2⁴, 두 번째 문자는 2³, … N번째 문자는 2^(5-N)
입력된 숫자에서 각 자리의 문자를 분리한 후 2^(5-N)을 곱하여 누적하면 됨
MID(x1, x2, x3)
- MID는 문자열 x1의 x2 위치에서부터 x3개의 문자를 추출하는 함수
- MID(“ABCDE”, 3, 2) -> “CD”
- MID(“12345”, 4, 1) -> “4”
VAL(x)
- VAL은 문자 “x”를 숫자로 변환하는 함수
- 단 “x”는 숫자 형태의 문자여야 함.
- VAL(“123”) -> 123
- VAL(“1”) -> 1
- VAL(MID(“1010111011”, 1, 1) -> VAL(“1”) -> 1
- 이를 위해 C에서는 atoi함수를 사용
변수
- a : 입력 받은 2진수가 저장될 변수
- b : 2진수 각 자릿수에 대한 10진수의 합계가 저장될 변수
- c : 2진수 각 자리를 지정해 주는 변수, 2진수가 10자리이므로 c는 1부터 10까지 차례로 변경됨
- d : 2진수 각 자리의 값이 저장될 변수
- e : 2진수 각 자리의 값에 대한 10진수 값이 저장될 변수

#include<stdlib.h>  // atoi() 함수가 정의되어 있는 헤더
#include<math.h>    // pow() 함수가 정의되어 있는 헤더

main() {

  char a[11], munja[2]; 

  double d, e;          
  scanf("%s", a);
  double b = 0;         // 10진수 값이 저장될 변수

  int c = -1;

  munja[1] = '\0';    
  // NULL 문자를 저장, 문자열로 사용하기 위해서!
  // atoi 함수는 문자열을 정수로 변환하는 함수기 때문. 
  // munja[2] 자체는 문자 배열

  while (1) {
    c++;
    if (c <= 9) {
      munja[0] = a[c];
      // 배열 a의 각 자리를 munja[0]에 저장
      // munja에 저장된 배열 a의 각 자리값은 문자열로 인식됨

      d = atoi(munja);         
      // 문자열 munja가 숫자로 변환되어 d에 저장됨

      e = d*pow(2, 4 - c);     
      // 해당 자리의 수를 10진수 수로 변환
      // pow함수는 거듭제곱

      b += e;          // 10진수가 저장될 b에 각 자리수를 더함      

    } else {
      printf("%8.5f", b);
      break;
    }
  }
}

10개의 수치 자료를 입력 받아 배열의 저장한 후 저장된 자료 중 가장 큰 값을 찾으시오.
(최대값 구하기)

알고리즘의 이해

최대 값은 자료 중 가장 큰 값을 찾는 것. 자료 중에서 나올 수 있는 임의의 가장 작은 값을 가지고 다른 자료들과 비교하는 것.
자료를 처음부터 차례대로 비교하여 더 큰 값이 나오면 그 값을 최대값으로 하고 다음 자료와 비교하는 과정을 모든 자료에 대해 반복.
- 또 다른 방법은 자료의 첫 번째 값을 최대값으로 지정, 두 번째 값부터 비교하여 최대값을 구하는 방법
변수
- a[10] : 입력받은 숫자가 저장될 배열
- i : 비교 대상의 위치를 지정해 주는 변수, 즉 i는 1, 2, 3, … , 10 까지 차례로 변경
- max : 최대값이 저장될 변수
- j : 입력 받은 숫자의 개수를 세는 변수

main() {
  int i;
  int a[10];
  int j = -1, max = 0;

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

  for (i = 0; i <= 9; i++) {
    if (a[i] > max)
      max = a[i];
  }

  printf("max : %d", max);
}

7명의 채점 점수 중에서 최하위 점수와 최상위 점수를 제외한 5명 점수의 평균을 구하시오. 단, 7명의 채점 점수는 배열에 들어 있다.
(최대값, 최소값을 제외한 평점의 평균 구하기)

변수
- a[7] : 입력 받은 7개의 자료가 저장될 변수
- m : 입력 받은 데이터의 개수가 저장될 변수
- i : 배열의 저장 위치를 지정해 주는 변수
- min : 자료 중 가장 작은 점수가 저장될 변수
- max : 자료 중 가장 큰 점수가 저장될 변수
- sum : 입력 받은 자료의 합계가 저장될 변수
- avg : 자료의 평균이 저장될 변수

#include <stdio.h>

main() {
  int m, min, max, sum, avg, i;
  int a[7];

  m = -1;

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

  // 첫 번째 값이 최소, 최대값으로 가정
  min = a[0]; 
  max = a[0];
  sum = a[0];
  i = 0;

  while (i < 6) {
    i++;
    sum += a[i];      // 여기선 일단 다 더하고
    if (a[i] < min)   // 현재 값이 최소값보다 작으면
      min = a[i];     // 새로운 최소값으로 할당
    if (a[i] > max)   // 현재 값이 최대값보다 크면
      max = a[i];     // 새로운 최대값으로 할당
  }

  // 여기서 최대, 최소 빼고 평균계산
  sum = sum - min - max;  
  avg = sum / 5;
  printf("%d %d %d %d", min, max, sum, avg);

}

1부터 100까지의 수 중 5의 배수의 개수와 합을 출력
(5의 배수의 개수와 합)

알고리즘의 이해

어떤 정수를 5로 나누었을 때 나머지가 0 이면 5의 배수.
1 ~ 100 사이에 있는 5의 배수의 개수와 합을 계산하려면 숫자를 1에서 100까지 증가시키면서 각각의 숫자를 5로 나누어 나머지가 0이면 5의 배수. 개수를 1증가시키고 그 때의 숫자를 합계에 누적하면 됨
변수
- count : 5의 배수의 개수가 저장될 변수
- sum : 5의 배수의 합계가 저장될 변수
- i : i부터 100까지 증가하는 값이 저장될 변수
- mok : i를 5로 나눈 몫이 저장될 변수
- nmg : i를 5로 나눈 나머지가 저장될 변수

main() {

  int count, sum, mok, nmg, i;
  count = 0, sum = 0;

  for(i = 0; i<= 100; i++) {
    mok = i / 5;
    nmg = i - mok * 5;

    if (nmg == 0) {
      count++;
      sum += i;
    }
  }
  
  printf("%d %d", count, sum);

}

10개의 1자리 양의 정수를 입력 받아 배열에 저장한 후 저장된 자료 중 7에 가장 가까운 자료를 찾으시오. 단, 자료는 1자리 정수이고 근사값이 2개인 경우에는 나중에 찾은 값을 출력
(7에 가장 가까운 수 구하기)

알고리즘의 이해

가장 가까운 수 구하기는 두 수의 차이에 대한 최소값을 구하는 것, 최소값 구하기와 같다고 볼 수 있음.
7에 가장 가깝다는 의미는 어떤 수와 7과의 차이가 가장 작다는 말.
7과 다른 수들의 차를 계산 후 차이를 비교, 가장 작은 수를 찾으면 됨.
주의할 점은 차이를 계산할 때 음수가 나오면 안됨.
- 7과 어떤 수의 대소 비교한 후 큰수에서 작은 수를 뺀다.
변수
- a[10] : 입력 받은 10개의 숫자가 저장될 배열
- i : 입력 받은 자료의 개수가 저장될 변수
- min_gap : 7과 비교 대상의 차이 값 중 최소값이 저장될 변수
- k : a배열의 위치를 지정해 주는 변수, 즉 k는 1,2,.. 10까지 차례로 변경됨
- gap : 7과 비교 대상의 차이 값이 저장될 변수
- nearest_num : 7과 가장 가까운 값이 저장될 변수

#include <stdio.h>
#define SEVEN 7

main() {
  int i, min_gap, k, gap, nearest_num;
  int a[10];

  for (i = 0; i < 10; i++) {
    scanf("%d", &a[i]);
  }

  min_gap = 9;

  for (k = 0; k < 10; k++) {

    if(a[k] >= SEVEN) 
      gap = a[k] - SEVEN;
    else 
      gap = SEVEN - a[k];
  
    if (gap <= min_gap) {
      min_gap = gap;
      nearest_num = a[k];
    }

  }
    printf("%d", nearest_num);
}

최소 값에 9를 주고 시작하는 이유?
- 한 자릿수에서 가장 큰 값은 9
- 처음에 비교할 자료와의 차이 값은 그 값의 크기와 관계없이 최소값이 되어야 함
  - 따라서 한 자리에서 나올 수 있는 가장 큰 값을 최소 값의 차이 값으로 둔 것.
- 그럼 최소값과 첫 번째 자료의 차이 값을 비교할 때 첫 번째 자료의 차이 값이 최소값이 됨.
- 만약 두 자릿수를 대상으로 비교한다면 최소값의 초기 값은 99를 가져야 함.
위처럼 구현 안하고 아래와 같이도 구현할 수도 있음. abs함수를 이용하면 결과를 항상 양수로 표시, 큰 수와 작은 수를 결정하기 위해 수치의 대소를 비교할 필요가 없음.

 for (k = 0; k < 10; k++) {

    gap = abs(a[k] - SEVEN);
  
    if (gap <= min_gap) {
      min_gap = gap;
      nearest_num = a[k];
    }

  }

정보처리기사실기