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

30 Jul 2018

Reading time ~7 minutes

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

1+2+3+4+… +100까지의 합계

알고리즘의 이해

0에서 1씩 증가시켜 100까지 변경되는 수열을 더하려면 두 개의 변수를 이용
한 개의 변수 i에는 수열의 각 항을 만들기 위해 1~100까지 증가시킬 수 있도록 1씩 더함
- i : 1씩 증가되는 숫자가 저장될 변수, 1~100까지 차례로 변경
다른 한 개의 변수 j에는 수열의 각 항이 1씩 증가할 때마다 그 값을 누적하여 저장
- i가 누적되어 저장될 변수, 1+2+3…+100까지 값이 저장

int main() {

  int i, j; 
  i = 0; j = 0;
  do {
    i++;
    j += i;
  } while (i < 100);

  printf("%d %d", i, j);

  return 0;
}

1+3+5+7+.. +99 합계를 구하는 순서도

int main() {

  int i, j;
  i = -1, j = 0;
  do {
    i += 2;
    j += i;
  } while(i<99);

  printf("%d", j);

  return 0;
}

1-2+3-4+5-6 … +99-100의 합계(스위치 변수 이용)

알고리즘의 이해

0에서 1씩 증가하여 100까지 변경되는 수열 중 한 번은 더하고, 한 번은 빼는 작업을 번갈아 반복할 경우 스위치 변수를 이용
수열의 각 항을 저장할 변수 i
- 1씩 증가되는 숫자가 저장될 변수
계산 값을 저장할 변수 j
- i의 값이 계산되어 저장될 변수
스위치 값을 저장할 변수 sw
- 스위치 변수 값이 0이면 더하고, 아니면 빼는 과정을 반복
- ‘+’와 ‘-‘중 어떤 연산자를 사용할지 판단할 수 있는 값이 저장될 변수

int main() {
  int i, j, sw;
  i = j = 0;
  sw = 0;

  do {

    i++;

    if (sw == 0) {
      j += i;
      sw = 1;
    } else {
      j -= i;
      sw = 0;
    }

  } while (i < 100);

  printf("%d", j);

  return 0;
}

1-2+3-4+5-6 … -98+99까지의 합계(순서에 의한 반복 계산)

알고리즘의 이해

다른 방법은 더하고 빼는 작업을 하나의 단위로 보고 그 단위를 반복하는 것
수열의 각 항을 저장할 변수 i
- i : 1씩 증가되는 숫자가 저장될 변수, 1~99까지 차례로 변경됨
각 항에 대한 계산값을 저장할 변수 j
- i의 값이 계산되어 저장될 변수, 1-2+3-4.. -98+99까지 계산값이 저장됨

int main() {

  int i = 0, j = 0;
  
  while (1) {
    i++;
    j += i;

    if (i >= 99) {
      printf("%d", j);
      break;
    } else {
      i++;
      j -= i;
    }
  }

  return 0;
}

(-1)x2x(-3)x4(-5)x… x100의 합계(홀짝 판별을 이용한 반복 계산)

알고리즘의 이해

홀짝을 판별, 정수를 2로 나누어 나머지가 0이면 짝수, 1이면 홀수
1씩 증가하는 값이 홀수인 경우 증가한 값을 음의 값으로 만들어 원래 값에 곱함
짝수인 경우 원래의 값에 증가한 값을 그대로 곱하는 과정을 번갈아 가면서 반복
두 개의 변수 사용
- i : 1씩 증가되는 숫자가 저장될 변수
- j : i의 곱한 값이 저장될 변수

int main() {

  int i;
  double j;

  i = 0;
  j = 1;

  do {

    i++;

    if (i % 2 == 0) 
      j *= i;
    else 
      j *= i * -1; 

  } while(i < 100);

  printf("%11.4e", j); // 결과는 안중요

  return 0;
}

- (1/2) + (2/3) - (3/4) + (4/5) - (5/6) … - (99/100)

알고리즘의 이해

분수를 생각하지 말고 분자만 1~99 증가시키는 수열이라 생각!
분자를 1~99까지 증가시키고 분자에 1을 더해 분모를 만들면 됨.
분자가 홀수면 누적된 값을 빼고, 짝수면 누적된 값을 더하는 작업을 분자가 99가 될때까지 반복
- i : 수열 각 항의 분자값이 증가할 수 있도록 1씩 더함
- j : 수열의 각 항이 누적되도록 함
홀짝 판별2
- 정수를 2로 나누어 정수 값만을 취한 값과 그냥 정수를 2로 나눈 값이 같으면 짝수, 값이 다르면 홀수
  - int(4/2) == 4/2 (2)
  - int(3/2) != 3/2 (1)
  - int()는 정수 값만 반환하는 함수.

int main() {

  float i = 0, j = 0;

  do {

    i++;

    if ((int)(i/2) == i/2)
      j += i/(i+1);
    else 
      j -= i/(i+1);

  } while (i < 99);

  printf("%f", j);

  return 0;
}

1+2+4+7+11+16+22… 순서로 나열되는 수열의 20번째 항까지의 합계
(항사이의 증가하는 값이 일정한 비율로 증가하는 수열)

알고리즘의 이해

수열의 이전 항에서 다음 항을 만들 때, 항 사이의 증가하는 값이 일정한 비율로 증가하는 수열의 합을 계산하려면 3개의 변수를 사용해야 함.
1에서 1씩 증가하여 19까지 변경되면서 20번째 항까지 만들기 위한 증가 값으로 사용할 변수 i
- i : 1씩 증가하는 숫자가 저장될 변수 1,2,3… 19까지 차례로 변경됨
증가 값을 더하여 수열의 각 항을 만들어 저장할 변수 j, 즉 1, 2, 4, 7을 기억할 변수
- j : i가 누적되어 저장될 변수, 1,2,4,7,11 까지 차례로 변경됨
그리고 수열의 각 항인 j가 만들어 질때마다 그 값을 누적할 변수 k
- k : j가 누적되어 저장될 변수 1+2+4+7+11… 의 계산값이 저장됨
이 수열의 합을 구하는 핵심은 각 변수의 초기 값으로 증가 값을 0, 첫 번째 항을 1, 합계를 1로 시작하는 것

int main() {

  int i, j, k;

  i = 0;
  j = 1;
  k = 1;

  do {

    i++;
    j += i;
    k += j;


  } while(i < 19);

  printf("%d", k);
  return 0;
}

k초기값으로 이미 계산된 것으로 처리함, 따라서 i는 19번 반복(20번째 항까지니까)

1+3+6+10+15+21+28+… 의 순서로 나열되는 수열의 20번째 항까지의 합계

이 문제는 처음 증가하는 값이 2라는 점이 위 문제와 다름. 초기항을 0부터 시작.
i : 1씩 증가되는 숫자가 저장될 변수
j : 1부터 i까지의 값이 누적되어 수열의 각 항이 저장될 변수
k : j의 값이 누적되어 저장될 변수, 1+3+6+10+… 의 값이 저장됨

int main() {

  int i = 0, j = 0, k = 0;

  do {

    i++;
    j += i;
    k += j;

  } while (i < 20);

  printf("%d", k);

  return 0;
}

-1 +2 -4 +7 -11 + 16 -22 +… 의 순서로 나열되는 수열의 20번째 항까지의 합계
(항이 바뀔 때마다 빼기와 더하기가 번갈아 나열되는 수열)

알고리즘의 이해

항이 바뀔때마다 빼기와 더하기를 번갈아 계산한다는 점이 위와 다름
- 여기선 -1을 곱하는 방법을 이용, -1을 곱할때마다 부호가 바뀜
i : 1씩 증가하는 숫자가 저장될 변수
sw : -1과 1을 반복하는 스위치 변수
j : i가 누적되어 저장될 변수, 1,2,4,7,11.. 차례로 변경
k : j * sw 값이 누적되어 저장될 변수

int main() {

  int i, j, k, L;

  i = 0;
  j = 1;
  k = -1;
  sw = -1;;

  do {

    i++;
    j += i;
    sw *= -1;
    k += j * sw;

  } while(i < 19);

  printf("%d", k);

  return 0;
}

k가 -1인 첫 항을 이미 포함하고 시작하기 때문에 19개의 항을 더하기 위해 i를 19까지만 증가

1! + 2! + 3! + 4!+ .. + 10!의 순서로 나열되는 수열의 10번째 항까지의 합계

알고리즘의 이해

팩토리얼의 합계를 구하는 알고리즘
세개의 변수 사용
- 각 항사이에서 일정한 비율로 증가하여 곱할 값으로 사용할 증가 배수 변수 i
  - i : 1씩 증가되는 숫자가 저장될 변수
- 증가 배수를 곱하여 수열의 각 항을 만들어 저장할 변수 j (1!, 2!, 3!,..)
  - j : 1부터 i까지의 곱, 수열의 각 항인 i!를 저장할 변수
- 수열의 각 항인 J가 만들어질 때마다 그 값을 누적할 변수 k
  - k : j의 값이 누적되어 저장될 변수

int main() {

  int i = 1, k = 1, j = 1;

  do {

    i++;
    j *= i;
    k += j;
    
  } while(i < 10);

  printf("%d", k);

  return 0;
}

1+1+2+3+5+8+13…의 순서로 나열되는 피보나치 수열의 20번째 항까지의 합계
(피보나치 수열의 합계)

알고리즘의 이해

피보나치 수열은 첫 번째 항과 두 번째 항을 더해서 세 번째 항을 만들고, 두 번째 항과 세 번째 항을 더해서 네 번째 항을 만드는 방법, 계속해서 다음 항을 만들어가는 수열
- 합계는 새로운 항이 만들어질 때마다 누적
3개의 변수 사용, 첫 번째항 a, 두 번째 항 b, 세 번째 항 c
- b를 a에 치환, c를 b에 치환한 후 a와 b를 더해 다시 세 번째 항을 만듦
- a : 첫 번째 항의 값이 저장될 변수
- b : 두 번째 항의 값이 저장될 변수
- c : 첫 번째 항과 두 번째 항의 합, 즉 세 번째 항이 저장될 변수
- sum : 각 항의 값이 누적되어 저장될 변수
- count : 몇 개의 항이 계산되었는가를 세는 개수가 저장될 변수

int main() {

  int sum, count, c;
  int a = 1, b = 1;

  sum = 2;
  count = 2;
  
  while (1) {

    c = a + b;
    sum += c;
    count++;

    if (count < 20) {
      a = b;
      b = c;
    } else {
      printf("%d", sum);
      break;
    }

  }

  return 0;
}

입력받은 값까지 피보나치 수열의 합을 구하는 문제
(반복문을 이용한 피보나치 수열)

a : 첫 번째 항의 값이 저장될 변수
b : 두 번째 항의 값이 저장될 변수
c : 첫 번째 항과 두 번째 항의 합, 즉 세 번째 항이 저장될 변수
sum : 각 항의 값이 누적되어 저장될 변수
count : 항의 값이 누적될 때마다 항의 개수가 저장될 변수
input : 입력받은 수열의 항의 개수가 저장될 변수

int main() {

  int a, b, c, sum, input, count;

  a = 1, b = 1;
  sum = 2;

  scanf("%d", &input);
  for (count = 3; count <= input; count++) {
    c = a + b;
    sum += c;
    a = b;
    b = c;
  }

  printf("%d", sum);

  return 0;
}

정보처리기사실기