[정보처리기사] 알고리즘

2019년 6월 정보처리기사 실기 시험을 준비하며 정리했던 내용입니다.

정보처리기사 - 실기 정리

1과목 실무 알고리즘 응용

1. 소프트웨어 개발의 기초

객체지향 기법의 기본 원칙

• 캡슐화(Encapsulation)
  • public, protected, private
  • 정보은닉(Information Hiding)
• 추상화(Abstraction)
• 상속성(Inheritance)
• 다형성(Polymorphism)

아키텍처 스타일

• IEEE 1471

  • 표준화, 중립성, 유연성, 의사소통

• 저장소 구조

  • 대량 데이터, 중앙 집중, 관리, 보안성
  • 저장소 오류 나면 시스템 전체 문제, 데이터 분산 x

• MVC 구조

  • 다양한 뷰, 효율적 모듈화, 유저 인터페이스에 대한 요구 사항을 적용시키기 용이
  • 간단한 앱에 적용 복잡, 모델이 자주변경되면 뷰가 못따라감

• 클라이언트/서버 구조

  • 데이터 관리, 업그레이드 용이
  • 데이터 처리 비용 증가 위험

• 계층 구조

  • OSI 7계층

• 파이프 필터 구조

  • 각 필터는 독립적 구조, 동시 수행으로 효율적, 응답성, 데드락 등 특수한 분석 지원
  • 상태 정보 공유는 X, 각 필터가 받은 데이터를 다시 파싱함

2. 프로그래밍 언어의 기본

순서도와 C언어의 기본

• 순서도 기호를 암기하자

C언어의 포인터, 배열, 구조체

• 포인터
  • 포인터 변수: 변수의 주소를 담는 변수
  • int *p = a;
    • int *p;
    • p = &a;
• 구조체
  • 새로운 자료형을 선언하는 기법
  • 구조체 포인터
    • seoul->name = "길동";
    • *(seoul).name = "길동";

3. 기본알고리즘 - 수열

1 부터 100까지 모든 합 구하기

피보나치 수열의 합계

• 현재 항 = 전 항과 그 전의 항의 합계

4. 기본알고리즘 - 수학

소수 판별법

• 입력값보다 1작은 값까지 1씩 증가시켜 나누어보자

• 입력값까지 1씩 증가시키면서 나누었을때 0이 되었다면 원래값인지 비교해보자

• 에라토스테네스의 체 : 입력값의 제곱근까지 1씩 더해보면서 나누어보자

  일정범위의 소수들의 합

  소수들의 개수

• 0이 아닌 수들은 모두 소수.

• 소수가 발견되면 소수의 배수들을 모두 0으로 초기화

  최대공약수, 최소공배수

• 최대공약수 : 큰 수/작은수 = 0 이라면, 작은수가 최대공약수

• 최소공배수 : 큰수*작은수/최대공약수 = 최대공배수

• 만약 나누었을때 0이 아니라면 큰수 = 작은수, 작은수 = 나머지값 으로 초기화하여 반복

• 유클리드 호제법

  소인수분해

• X를 소인수 분해할때 2부터 X의 제곱근까지 숫자로 나누어 떨어지는지 검사.

• 나누어 떨어졌을때 몫의 제곱근까지의 숫자로 나누어 떨어지는지 검사

  10진법을 2진법으로 변환

• 2로 나누었을때 나머지값을 저장

  10진수를 임의의 진수로 변환

• X를 가장 가까운 '입력받은 진수'의 누승을 구한다.

• 누승을 X에 나눴을때 몫이 '입력받은 진수의 값'이 되고

• 나머지는 다시 X가되어 위 과정을 반복

소수점이 포함된 2진수를 10진수로 변환

• 2진수를 입력받으면 5번째 자리까지는 소수이상이라고 가정하에

• 각 10진수를 2^(5-N) 계산

  최대값, 최소값 구하기

• 최대값 : 초기값으로 비교할 숫자들보다 작은 값 0을 기억시키고 시작

• 최대, 최소를 제외한 평점의 평균

  5의 배수의 개수와 합

  7에 가장 가까운 수 찾기

• 7과 특정값의 차이를 구해 그 차이가 가장 작은 값을 찾으면됨

  보수 구하기

• 1의 보수 : 각 자리수를 1씩 빼면됨

• 2의 보수 : 1의 보수에서 자리올림수 1을 추가함

  • 이진수 오른쪾에서 1이 나온거까지 그대로쓰다가 그다음부터 반대로 쓰기

• 2의 보수를 2의 보수로 바꾸기 (원래의 2진법으로 바꾸기)

  • 오른쪽에서 1이 나온거까지 바꿔쓰다가 그다음부터 그대로 쓰기 : 1의 보수 완성

  • 1의 보수를 숫자를 바꿔주면 됨

    그레이코드

• 첫번째 그레이코드 : 이진수 첫 비트는 그대로 쓴다.

• 다음 그레이코드부터 : 두번째 이진수 비트와 그 왼쪽 비트를 XOR연산값을 쓴다.

  큰수 더하기

• 배열의 각 자리수를 더하고 10의 자리가 넘으면 자리올림수라는 변수를 그 전항에 추가하는 식

• 이진수 더하기도 비슷함

5장 응용 알고리즘 - 자료구조

선택정렬

• 1회전 : 첫째항과 나머지 항을 비교하며 가장 최소값을 첫째항과 바꿈

버블정렬

• 붙어있는 것끼리 비교를 하여 오름차순 기준 오른쪽부터 정렬이 되어짐

삽입정렬

• 두번째 자료부터 시작해서 왼쪽자료들과 비교하여 삽입할 위치를 지정하여 정렬

석차 구하기(순위)

• 본인점수와 비교하여 본인점수가 낮으면 석차를 +1

이진검색

• 찾고자하는 index를 기준으로 처음과 끝의 평균을 구하며 평균보다 작고 큼을 비교하며 탐색

병합

• 두개의 오름차순 배열을 병합하는데 원소 하나씩 대소비교하며 병합된 배열에 들어간 배열의 원소위치를 증가시키며 병합

스택

• push, pop 함수와 스택의 head를 조절하여 구현

6장 응용 알고리즘 - 배열

기본 5행 5열

직각 삼각형

'ㄹ'자 만들기

다이아몬드 만들기

모래시계

오른쪽이 빈 삼각형

이등변 삼각형

90도 회전하기

달팽이

대각선으로 채우기

마방진

행렬 변환

• 공통적으로 문제의 조건에 따라 모든 규칙을 찾아내고 제시된 알고리즘에 맞게 규칙을 적용한다.

7장 실무 응용 알고리즘

화폐의 종류별 매수 계산

부서별 합계

동별, 나이별 인원 통계

학급별 최대, 최소 체중

사과 구입

사과 나눠 갖기

반 배정

역순으로 숫자 더하기

숫자의 좌우 위치 변경

구구단