---
title: "정보처리기사 실기 알고리즘 정리 05"
date: "2018-08-04"
tags: ["정보처리기사실기"]
status: archived
verified: false
---

## 정보처리기사 실기 알고리즘 정리 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<sup>4</sup> + 2<sup>3</sup> + 2<sup>2</sup>+ 2<sup>1</sup>+ 2<sup>0</sup>으로 구성되어 있으므로 31을 첫 번째 누승인 16으로 나누어 몫과 나머지를 구하면 이 때의 몫 1은 24을 의미하고 나머지는 15다. 다시 나머지 15를 두 번째 누승인 8로 나누어 몫과 나머지를 구하면 이때 몫 1은 23을 의미하고 나머지는 7이다. 이런 방법으로 20(1)로 나눌 떄까지 차례대로 반복하면 됨.
* 2진수로 변환하기 때문에 2의 누승으로 나눔. 8진수면 8의 누승, 16진수면 16의 누승으로 나눔.
    * 예로 87을 8진수로 변환한다면 8<sup>2</sup>(64), 8<sup>1</sup>(8), 8<sup>0</sup>(1)으로 나눔
        * 87/64 = 몫1, 나머지23
        * 23/8 = 몫2, 나머지 7
        * 7/1 몫7
        * 제수가 1이면 종료
        * (87)<sub>10</sub> -> (127)<sub>8</sub>
* 변수
    * 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로 나눈 나머지가 저장될 변수


```cpp
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번째에 있는 값을 출력

<hr />



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

#### 알고리즘의 이해
* 예를 들어 입력받은 문자열이 ‘1010111011’이라면 각 자릿수의 의미는 다음과 같음
  * 1 : 1 * 2&lt;sup>4&lt;/sup>
 
  * 0 : 0 * 2&lt;sup>3&lt;/sup>

  * 1 : 1 * 2&lt;sup>2&lt;/sup>

  * 0 : 0 * 2&lt;sup>1&lt;/sup>

  * 1 : 1 * 2&lt;sup>0&lt;/sup>

  * .

  * 1 : 1 * 2&lt;sup>-1&lt;/sup>

  * 1 : 1 * 2&lt;sup>-2&lt;/sup>

  * 0 : 0 * 2&lt;sup>-3&lt;/sup>

  * 1 : 1 * 2&lt;sup>-4&lt;/sup>

  * 1 : 1 * 2&lt;sup>-5&lt;/sup>

* 첫 번째 문자는 2&lt;sup>4&lt;/sup>, 두 번째 문자는 2&lt;sup>3&lt;/sup>, ... N번째 문자는 2&lt;sup>(5-N)&lt;/sup>
* 입력된 숫자에서 각 자리의 문자를 분리한 후 2&lt;sup>(5-N)&lt;/sup>을 곱하여 누적하면 됨

* 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진수 값이 저장될 변수

```cpp
#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;
    }
  }
}
```

<hr />


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

#### 알고리즘의 이해 
* 최대 값은 자료 중 가장 큰 값을 찾는 것. 자료 중에서 나올 수 있는 임의의 가장 작은 값을 가지고 다른 자료들과 비교하는 것.
* 자료를 처음부터 차례대로 비교하여 더 큰 값이 나오면 그 값을 최대값으로 하고 다음 자료와 비교하는 과정을 모든 자료에 대해 반복.
    * 또 다른 방법은 자료의 첫 번째 값을 최대값으로 지정, 두 번째 값부터 비교하여 최대값을 구하는 방법

* 변수
    * a[10] : 입력받은 숫자가 저장될 배열
    * i : 비교 대상의 위치를 지정해 주는 변수, 즉 i는 1, 2, 3, ... , 10 까지 차례로 변경
    * max : 최대값이 저장될 변수
    * j : 입력 받은 숫자의 개수를 세는 변수

```cpp
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);
}
```

<hr />


### 7명의 채점 점수 중에서 최하위 점수와 최상위 점수를 제외한 5명 점수의 평균을 구하시오. 단, 7명의 채점 점수는 배열에 들어 있다.
(최대값, 최소값을 제외한 평점의 평균 구하기)
* 변수
    * a[7] : 입력 받은 7개의 자료가 저장될 변수
    * m : 입력 받은 데이터의 개수가 저장될 변수
    * i : 배열의 저장 위치를 지정해 주는 변수
    * min : 자료 중 가장 작은 점수가 저장될 변수
    * max : 자료 중 가장 큰 점수가 저장될 변수
    * sum : 입력 받은 자료의 합계가 저장될 변수
    * avg : 자료의 평균이 저장될 변수

```cpp
#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);

}
```

<hr />

### 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로 나눈 나머지가 저장될 변수

```cpp
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);

}
```

<hr />


### 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과 가장 가까운 값이 저장될 변수

```cpp
#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함수를 이용하면 결과를 항상 양수로 표시, 큰 수와 작은 수를 결정하기 위해 수치의 대소를 비교할 필요가 없음.

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

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

  }
```