[정보처리기사] 필기 - 소프트웨어 개발(1)

자료 구조 학습

⎮ 선형 / 비선형 구조 (자료 구조 : 자료의 묶인 모습 + 데이터 + 연산)

   선형 구조 : 큐, 스택, 데크, 리스트, 연결 리스트

   비선형 구조 : 그래프, 트리, 인접 행렬

   스택의 응용 분야 : 인터럽트의 처리, 수식의 계산, 서브루틴의 복귀 번지 저장, 후위 표현(Post-fix Expression)의 연산, 깊이 우선 탐색

1. 다음 중 선형 구조로만 묶인 것은?
① 스택, 트리
② 큐, 데크
③ 큐, 그래프
④ 리스트, 그래프

2. 스택(Stack)에 대한 옳은 내용으로만 나열된 것은?
㉠ FIFO 방식으로 처리된다.
㉡ 순서 리스트의 뒤(Rear)에서 노드가 삽입되며, 앞(Front)에서 노드가 제거된다.
㉢ 삭제가 리스트의 앞과 뒤에서 모두 가능한 자료 구조이다.
㉣ 인터럽트 처리, 서브루틴 호출 작업 등에 응용된다.
① ㉠, ㉡
② ㉡, ㉢
③ ㉣
④ ㉠, ㉡, ㉢, ㉣
-> ㉠, ㉡은 Queue, ㉢은 데크

 

⎮ 트리

트리 그림 예시

 

구 분	설 명	예 시
노드(Node)	트리의 기본 구성 요소	A ... G 까지
근노드(Root Node)	가장 상위에 있는 노드	그림에서 A가 Root Node.
레벨(Level)	근노드를 기준으로 특정 노드까지의 경로 길이	그림에서는 4층
조상 노드(Ancestors Node)	어떤 노드에서 근노드에 이르는 경로상의 모든 노드	D의 조상노드는 B, A
부모 노드(Parent Node)	어떤 노드에 연결된 이전 레벨의 노드	E의 부모 노드는 B, B와 C의 부모 노드는 A
자식 노드(Child Node)	어떤 노드에 연결된 다음 레벨의 노드	B의 자식 노드는 D, E, F
형제 노드(Brother Node)	같은 부모를 가진 노드	D의 형제 노드는 E, F
깊이(Depth)	트리의 최대 레벨	H, I가 최대 레벨
차수(Degree)	어떤 노드에 연결된 자식 노드의 수	A의 차수는 2, B의 차수는 3, H의 차수는 0
단말 노드(Terminal Node)	트리의 제일 마지막에 있는 노드 (차수 = 0)	H, I 뿐만 아니라 D, E, G도 단말 노드
트리의 차수(Degree)	트리의 노드 중 가장 큰 차수	B의 차수가 3으로 가장 큰 차수

 

⎮ 트리 순회, 연산식

- 트리 순회, 연산식 

  Root가 언제 방문했는지가 기준

  전위 순회(Preorder) : [루트 → 왼쪽 자식 → 오른쪽 자식] 순으로 순회

  중위 순회(Inorder) : [왼쪽 자식 → 루트 → 오른쪽 자식] 순으로 순회

  후위 순회(Postorder) : [왼쪽 자식 → 오른쪽 자식 → 루트] 순으로 순회

  *연산식일 때는 Prefix, Infix, Postfix

1. 다음 트리를 Preorder 운행법으로 운행할 경우 다섯 번째로 탐색되는 것은?
① C
② E
③ G
④ H

2. 다음 Postfix로 표현된 연산식의 연산 결과로 옳은 것은?

3 4 * 5 6 * +

① 35
② 42
③ 81
④ 360
-> 연산의 대상이 앞에 있고, postfix(연산자)가 뒤에 있는 것
     Prefix : 3 4 * 5 6 * +
     Infix : (3*4) + (5*6)

 

⎮ 정렬 (오름차순 / 내림차순)

    * 오름차순 작 → 큰

   선택정렬, 버블정렬은 교환법에 근거한 알고리즘(성능이 안좋음)

   삽입정렬은 삽입법에 근거한 알고리즘(효율적임)

   - 선택 정렬(Selection Sort) : n개의 레코드 중에서 최솟값(또는 최댓값)을 찾아 배열의 첫 번째 위치에 놓고,

      이를 반복하여 정렬하는 방법

      최상, 최악, 평균 시간 복잡도 : 0(n²)

   - 버블 정렬(거품 정렬, Bubble Sort) : 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법

      최상, 최악, 평균 시간 복잡도 : 0(n²)

   - 삽입 정렬(Insertion Sort) : 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬하는 방법

      최상 시간 복잡도 : 0(n)

      최악, 평균 시간 복잡도 : 0(n²)

1. 버블 정렬을 이용하여 다음 자료를 오름차순으로 정렬할 경우 PASS 1의 결과는?

9, 6, 7, 3, 5

① 6, 9, 7, 3, 5
② 3, 9, 6, 7, 5
③ 3, 6, 7, 9, 5
④ 6, 7, 3, 5, 9
-> 오름차순이라면 최종 값은 3, 5, 6, 7, 9이다.
     버블 정렬은 인접한 데이터를 비교하는 것이므로
      PASS1 일 때 : 6 7 3 5 9
      PASS2 일 때 : 6 3 5 7 9
      PASS3 일 때 : 3 5 6 7 9

2. 다음 자료에 대하여 "Selection Sort"를 사용하여 오름차순으로 정렬한 경우 PASS 3의 결과는?

초기 상태 : 8, 3, 4, 9, 7

① 3, 4, 7, 9, 8
② 3, 4, 9, 7, 8
③ 3, 8, 7, 4, 9
④ 3, 8, 4, 9, 7
-> Selection Sort에서는 오름차순일 때 최소값을 맨 앞으로 가져다 놓고, 선택 값을 교환
     PASS1일 때 : 3, 8, 4, 9, 7
     PASS2일 때 : 3, 4, 8, 9, 7
     PASS3일 때 : 3, 4, 7, 9, 8
     PASS4일 때 : 3, 4, 7, 8, 9

 

⎮ 검색 (선형 검색 / 이분 검색)

  선형 검색(순차 검색) : 원하는 레코드를 찾을 때까지 처음부터 끝까지 차례로 하나씩 비교하면서 검색하는 것

  데이터가 모인 집합(배열, 링크드 리스트 등)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아 내는 알고리즘

  단점 : 평균 검색 시간이 많이 소요됨.(단순한 방식으로 정렬되지 않는 검색에 가장 유용하긴 함)

  평균 검색 횟수 : (n + 1) / 2 

  이분 검색(이진 검색) : 비교 횟수를 거듭할 때마다 검색 대상이 되는데이터의 수가 절반으로 줄어드는 검색 방식

  탐색 효율이 좋고 탐색 기간이 적게 소요됨.

  검색할 데이터가 정렬되어 있어야 함.

  대상 범위의 첫번째 원소의 위치를 Low로, 마지막 원소의 위치를 High로 두고서

  그 중간 원소의 위치인 Mid를 (Low + High) /2로 구함

  - 찾고자 하는 Key와 중간값을 비교

     Key > 중간값 : Low를 (Mid + 1)로 두고서 계속 수행

     Key < 중간값 : High를 (Mid - 1)로 두고서 계속 수행

     Key = 중간값 : 검색 완료

1. 알고리즘과 관련한 설명으로 틀린 것은?
① 주어진 작업을 수행하는 컴퓨터 명령어를 순서대로 나열한 것으로 볼 수 있다.
② 검색(Searching)은 정렬이 되지 않은 데이터 혹은 정렬이 된 데이터 중에서 키 값에 해당하는 데이터를 찾는 알고리즘이다.
③ 정렬(Sorting)은 흩어져 있는 데이터를 키값을 이용하여 순서대로 열거하는 알고리즘이다.
④ 선형 검색은 검색을 수행하기 전에 반드시 데이터의 집합이 정렬되어 있어야 한다.
-> 순차 검색은 검색을 수행하기 전에 정렬되어 있어야 함.

2. 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾을 경우 비교되는 횟수는?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

① 2
② 3
③ 4
④ 5
-> 순차 검색을 한다면 14번 해야하는데, 이분 검색으로 처리한다면 3회만에 찾을 수 있음.
     1회 비교 : M = (L + H) / 2 에 대입하면 위의 숫자에서는 8 = (1 + 15) / 2
     2회 비교 : M = ((L : M + 1) + H) / 2에 대입하면 위의 숫자에서는 12 = (8 + 1) + 15 / 2 
     3회 비교 : M = ((L : M + 1) + H) / 2에 대입하면 위의 숫자에서는 28 = (12 + 1) + 15 / 2

 

⎮ 해싱 함수의 종류

   해싱 함수의 종류 : 제산 방법(Division Method), 중간 제곱 방법(Mid-Sqaure Method), 중첩 방법(Folding Method), 

                  기수 변환 방법(Radix Conversion Method), 무작위 방법(Random Method), 계수 분석 방법(Digit Analysis Method)

1. 해싱 함수(Hashing Function)의 종류가 아닌 것은?
① 제곱법(Mid-Square)
② 숫자 분석법(Digit Analysis)
③ 개방 주소법(Open Addressing)
④ 제산법(Division)

2. 해싱 함수 중 레코드 키를 여러 부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 사용하는 방식은?
① 제산법
② 폴딩법
③ 기수 변환법
④ 숫자 분석법

 

⎮ 단위 테스트

  단위 테스트 : 하나의 모듈을 기준으로 독립적으로 진행되는 가장 작은 단위의 테스트

  애플리케이션을 구성하는 하나의 기능이 올바르게 동작하는 지를 독립적으로 테스트하는 것

  구현 단계에서 각 모듈의 개발을 완료한 후 개발자가 명세서의 내용대로 정확히 구현되었는지 테스트

  모듈 내부의 구조를 구체적으로 볼 수 있는 구조적 테스트를 주로 시행

   - 단위 테스트 지원 도구(xUnit)

      JUnit : Java 프로그래밍 언어에 사용되는 테스트 도구. 데이터를 테스트한 다음 코드에 삽입

      NUnit : 모든 .net 언어에 널리 사용되는 단위 테스트 프레임워크로 병렬로 실행할 수 있는 데이터 중심 테스트를 지원

      JMockit : 오픈소스 단위 테스트 도구로 기록 및 검증 구문으로 API를 Mocking할 수 있음

      EMMA : 코드 분석 오픈소스 툴킷으로 Java 기반이므로 외부 라이브러리 종속성이 없으며 소스 코드에 액세스할 수 있음

      PHPUnit : PHP 프로그래머를 위한 단위 테스트 도구

      HttpUnit : Java 프로그램용 GUI가 없는 브라우저를 포함하는 오픈소스 Java 라이브러리

      DBUnit : 데이터베이스 단위 테스트를 지원하는 프레임워크

1. 단위 테스트(Unit Test)와 관련된 설명으로 틀린 것은?
① 구현 단계에서 각 모듈의 개발을 완료한 후 개발자가 명세서의 내용대로 정확히 구현되었는지 테스트한다.
② 모듈 내부의 구조를 구체적으로 볼 수 있는 구조적 테스트를 주로 시행한다.
③ 필요 테스트를 인자를 통해 넘겨주고, 테스트 완료 후 그 결과값을 받는 역할을 하는 가상의 모듈을 테스트 스텁(Stub)이라고
한다.
④ 테스트할 모듈을 호출하는 모듈도 있고, 테스트할 모듈이 호출하는 모듈도 있다.
-> 자료를 추가하고 결과값을 확인하는 것은 통합 테스트와 관련한 표현

2. 다음 중 단위 테스트 도구로 사용할 수 없는 것은?
① CppUnit
② JUnit
③ HttpUnit
④ lgpUnit

 

⎮ 블랙박스 테스트 vs 화이트박스 테스트

    - 블랙박스 테스트(기능 테스트) : 소프트웨어가 수행할 특정 기능을 알기 위해 각 기능이 완벽히 작동되는 것을 입증하는 테스트

       대표적인 명세 기반 기법(Specification-based Technique)

        등가 분할의 경계 부분에 해당하는 입력값에서 결함이 발견될 확률이 경험적으로 높아서 결함을 방지하기 위해

       경계값까지 포함하여 테스트하는 기법

       종류 : 동치 분할 검사, 원인 효과 그래프, 오류 예측 검사, 비교 검사, 경계값 분석

    - 화이트박스 테스트 : 모듈의 원시 코드를 오픈시킨 상태에서 코드의 논리적 모든 경로를 테스트하는 방법

       Source Code의 모든 문장을 한번 이상 수행함으로써 진행

       화이트박스 테스트의 이해를 위해 논리 흐름도(Logic-Flow Diagram)을 이용할 수 있음

       테스트 데이터를 이용해 실제 프로그램을 실행함으로써 오류를 찾는 동적 테스트(Dynamic Test)에 해당

       종류 : 기초 경로 검사, 루프 테스트, 데이터 흐름 테스트, 제어 구조 검사

1. 화이트박스 검사 기법에 해당하는 것으로만 짝지어진 것은?
㉠ 데이터 흐름 검사
㉡ 루프 검사
㉢ 동등 분할 검사
㉣ 경계값 분석
㉤ 원인 결과 그래프 기법
㉥ 오류 예측 기법
① ㉠, ㉡
② ㉠, ㉣
③ ㉡, ㉤
④ ㉢, ㉥

2. 블랙박스 테스트를 이용하여 발견할 수 있는 오류가 아닌 것은?
① 비정상적인 자료를 입력해도 오류 처리를 수행하지 않는 경우
② 정상적인 자료를 입력해도 요구된 기능이 제대로 수행되지 않는 경우
③ 반복 조건을 만족하는데도 루프 내의 문장이 수행되지 않는 경우
④ 경계값을 입력할 경우 요구된 출력 결과가 나오지 않는 경우

 

본 게시물은 과학기술정보통신부와 정보통신기획평가원이 지원한 'SW중심대학'의 결과물로써

국립안동대학교 SW융합교육원의 자료를 참고하여 작성하였습니다.