[25년 03차 / 문제풀이] 소프트웨어 성능 분석
개념
☐ 플랫폼 성능 특성 분석 항목
● 경과시간(Turnaround Time) : 요청된 시간부터 처리가 완료될 때가지 걸린 시간
● 응답시간(Response Time) : 요청을 전달한 시간부터 응답이 도착할 때까지 걸린 시간
● 사용률(Utilization) : 요청을 처리하는 동안 CPU, 메모리 자원 사용률
● 가용성(Availability) : 일정한 시간 내에 처리하는 일의 양
☐ 알고리즘 관련 용어
● 알고리즘 : 주어진 작업을 수행하는 컴퓨터 명령어를 순서대로 나열한 것
● 정렬(Sorting) : 흩어져 있는 데이터를 키 값을 이용하여 순서대로 열거하는 알고리즘
● 검색(Searching) : 정렬이 되지 않은 데이터 혹은 정렬이 된 데이터 중에서 키 값에 해당되는 데이터를 찾는 알고리즘
☐ 선형 검색(Linear Search)
● 선형 검색의 개념 : 순차 검색, 선형 검색, 데이터가 모인 집합(배열, 리스트 등)의 처음부터 끝가지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘
● 선형 검색의 장점 : 데이터 정렬이 필요 없어 검색의 난이도가 쉬움
● 선형 검색의 단점 : 하나하나 모두 비교하므로 비효율적이고, 데이터의 양이 많아질 경우 검색에 소요되는 시간도 비례하여 많아짐
☐ 이진 검색, 이분 검색(Binary Search)
● 이진 검색의 개념 : 전체 파일을 두 개의 서브파일로 분리해가면서 Key 레코드를 검색하는 방식
● 이진 검색의 특징
- 반드시 순서화된 파일이어야 검색할 수 있음
- 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색
- 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요
● 이진 검색의 과정
- 정렬된 리스트에서 중간 레코드 번호를 선택하여 찾고자 하는 값과 비교
- 중간 레코드 번호 구하는 공식 : M = (F+L) / 2 (M: 중간 레코드 번호, F : 첫 번째 레코드 번호, L : 마지막 레코드 번호)
- 중간 레코드 번호 값을 기준으로 찾고자하는 값이 더 크면 오른쪽 반, 찾고자하는 값이 더 작으면 왼쪽 반으로 탐색 범위를 줄여가며 검색함
● 이진 검색의 예시 : 레코드 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]에서 14를 찾을 때 비교 횟수 구하기
- 1차 비교 : 중간 값 8 < 찾으려는 값 14 - 오른쪽 반 [9~15]로 이동
- 2차 비교 : 오른쪽 반 [9~15]의 중간 값 12 < 찾으려는 값 14 - 오른쪽 반 [13~15]로 이동
- 3차 비교 : 오른쪽 반 [13~15]의 중간 값 14
☐ 빅오-표기법(Big-O Notation)
● 빅오 표기법의 특징
- 알고리즘의 실행시간이 최악일 때를 표기하는 방법
- 신뢰성이 떨어지는 오메가 표기법이나 평가하기 까다로운 세타 표기법에 비해 성능을 예측하기 용이하여 주로 사용됨
● 빅오 표기법으로 표현한 일반적인 알고리즘의 최악의 시간 복잡도
- O(1)
+ 입력값(n)에 관계 없이 일정하게 문제 해결에 하나의 단계만을 거침
+ 스택의 삽입(Push), 삭제(Pop)
- O(log₂)
+ 문제 해결에 필요한 단계가 입력값(n) 또는 조건에 의해 감소함
+ 이진 트리(Binary Tree), 이진 검색(Binary Search)
- O(n)
+ 문제 해결에 필요한 단계가 입력값(n)과 1:1의 관계를 가짐
+ for문
- O(nlog₂n)
+ 문제 해결에 필요한 단계가 n(log₂n)번만큼 수행됨
+ 힙 정렬(Heap Sort), 2-Way 합병 정렬(Merge Sort)
- O(n²)
+ 문제 해결에 필요한 단계가 입력값(n)의 제곱만큼 수행됨
+ 삽입 정렬(Insertion Sort), 쉘 정렬(Shell Sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 퀵 정렬(Quick Sort)
- O(2ⁿ)
+ 문제 해결에 필요한 단계가 2의 입력값(n) 제곱만큼 수행됨
+ 피보나치 수열(Fibonacci Sequence)
☐ 순환 복잡도(Cyclomatic Complexity)
● 순환복잡도의 개념 : 한 프로그램의 논리적인 복잡도를 측정하기 위한 소프트웨어 척도
● 순환복잡도의 특징
- 맥케이브 순환도(McCabe's Cyclcmatic), 맥케이브 복잡도 메트릭(McCabe's Complexity Metrics)라고도 함
- 제어 흐름도 이론에 기초를 둠
- 순환 복잡도를 이용하여 계산된 값은 프로그램의 독립적인 경로의 수를 정의, 모든 경로가 한 번 이상 수행되었음을 보장하기 위해 행해지는 테스트 횟수의 상한선을 제공
● 순환복잡도 계산 방법 : V(G) = E - N + 2 (G : 제어 흐름도, E : 화살표 수, N : 노드의 수)
문제
☐ 플랫폼 성능 특성 분석 항목
2023년-2차 7번. 소프트웨어 설계 시 구축된 플랫폼의 성능 특성 분석에 사용되는 측정 항목이 아닌 것은?
① 응답 시간(Response Time)
② 서버 튜닝(Server Tuning)
③ 가용성(Availability)
④ 사용률(Utilization)
정답 : 2
입력 답 : 3
☐ 선형 검색(Linear Search)
2022년-2차 31번. 알고리즘과 관련한 설명으로 틀린 것은?
① 주어진 작업을 수행하는 컴퓨터 명령어를 순서대로 나열한 것으로 볼 수 있다.
② 검색(Searching)은 정렬이 되지 않은 데이터 혹은 정렬이 된 데이터 중에서 키 값에 해당되는 데이터를 찾는 알고리즘이다.
③ 정렬(Sorting)은 흩어져 있는 데이터를 키 값을 이용하여 순서대로 열거하는 알고리즘이다.
④ 선형 검색은 검색을 수행하기 전에 반드시 데이터의 집합이 정렬되어 있어야 한다.
정답 : 4
입력 답 : 1
☐ 이진 검색, 이분 검색(Binary Search)
022년-2차 22번. 다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 14를 찾을 경우 비교되는 횟수는?
<보기>
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
① 2
② 3
③ 4
④ 5
정답 : 2
입력 답 : 1
<풀이>
- 1차 비교 : 중간 값 8 < 찾으려는 값 14 - 오른쪽 반 [9~15]로 이동
- 2차 비교 : 오른쪽 반 [9~15]의 중간 값 12 < 찾으려는 값 14 - 오른쪽 반 [13~15]로 이동
- 3차 비교 : 오른쪽 반 [13~15]의 중간 값 14
☐ 빅오-표기법(Big-O Notation)
2022년-1차 36번. 분할 정복(Divide and Conqure)에 기반한 알고리즘으로 피봇(pivot)을 사용하며 최악의 경우 (n(n-1)/2) 회의 비교를 수행해야 하는 정렬(Sort)은?
① Selection Sort
② Bubble Sort
③ Insert Sort
④ Quick Sort
정답 : 4
입력 답 : 2
☐ 순환 복잡도(Cyclomatic Complexity)
2020년-2회 26번. 제어흐름 그래프가 다음과 같을 때 McCabe의 cyclomatic 수는 얼마인가?
① 3
② 4
③ 5
④ 6
정답 : 2
입력 답 : 4
2023년-2차 36번. 제어 흐름 그래프가 다음과 같을 때 McCabe의 cyclomatic 수는 얼마인가?
① 3
② 4
③ 5
④ 6
정답 : 2
입력 답 : 3