[정보처리기사] Part02-04-03. 애플리케이션 성능 개선 (1)

 

애플리케이션 성능 개선

  알고리즘

  개념

  알고리즘 표현 방법

• 알고리즘 기술 방법
• 알고리즘 성능 표현 방법
• 알고리즘 표기법 유형

  알고리즘 표현을 위한 순서도

• 순서도 기본
• 순서도 기본 모형

  알고리즘 기법

  정렬 알고리즘

• 개념
• 선택 정렬
• 버블 정렬
• 삽입 정렬
• 기수 정렬

 

  소스 코드 품질분석 도구

  개념

  소스코드 품질도구 종류

• 정적 분석 도구 (Static code analyzer)
• 동적 분석 도구 (Dynamic code analyzer)

 

 

애플리케이션 성능 개선

알고리즘

개념

수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어 내는 과정.

 

사전적 의미 : 어떤 문제를 해결해 나가는 특별한 방법 또는 문제 해결을 위해 컴퓨터로 이용될 수 있는 명확한 방법.

 

 

알고리즘 표현 방법

알고리즘 기술 방법

• 순서도(흐름도 - flowchart)
• 자연어 (일상 언어)
• 의사 코드 (Pseudo code)
• 프로그래밍 언어
• 인터프리터가 작업하는 제어 테이블
• 유한 상태 기계의 상태도 등

 

알고리즘 성능 표현 방법

• 시간적 복잡도 (Time Complexity) : 시간 효율성 위해 알고리즘 수행에 필요한 시간의 양을 측정하고 단위 연산이 몇 번이나 수행되는지 입력 크기에 따라서 평가하는 방법
• 점근적인 복잡도 (Asymptotic Complexity) : 알고리즘 복잡도 평가 시 주요 항 이외의 항과 주요 항에 있는 계수도 무시하고 꼭 필요한 부분 (매개변수 N의 값)이 무한에 가까워 졌을 때 복잡도가 어떻게 되느냐에 중점하는 평가 방법

 

알고리즘 표기법 유형

• 알고리즘 표기법 유형

표기법	개념
Big-O(빅 오)	입력 데이터가 최악일 때 기준으로 알고리즘 효율 평가를 위해 사용되는 수학적 기호 (알고리즘 수행시간 상한을 표시)
Big-Ω(빅 오메가)	입력 데이터가 최상일 때 기준으로 알고리즘 효율 평가를 위해 사용되는 수학적 기호 (알고리즘 수행시간 하한을 표시)
Big-θ(빅 세타)	빅오, 빅오메가 둘 다를 포함하는 개념으로, 알고리즘 수행시간 하한인 동시에 상한을 표시

• O-Notation (빅 오 표기법) 유형

유형	설명	사례
O(1)	상수형 자료 크기와 무관하게 항상 같은 속도로 작동	Hash Function
O(log N)	로그형 주로 커다란 문제를 일정 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형 데이터 크기에 따라 달라지나 데이터가 추가 될수록 더 효율적임	Binary Search
O(N)	선형 입력 자료를 차례로 하나씩 모두 처리 수행 시간이 자료 크기와 직접적인 관계로 변함 (정비례)	Find item

O(N log N)	분할과 합병형 자료 분할하여 각각 처리하고 합병 일반적으로 정렬 (sorting) 알고리즘이 가져야 할 최소한의 복잡도로 간주	Quick Sort
O(N²)	제곱형 주요 처리 (기본 연산) loop 구조가 2중인 경우 N의 크기가 작을 땐 N²이 N log N보다 작을 수 있음 자료가 증가함에 따라 급격히 커지기 때문에 대부분 과제들에 비해 비효율적이라고 간주	Bubble Sort
O(N³)	세제곱형 주요 처리 (기본 연산) loop가 3중인 경우 O(N²)보다 더 비효율적	Finding the Sortest Path
O(Nⁿ)	지수형 가능한 해결 방법 모두 다 검사하여 처리함 매우 비효율적이므로 최대한 피해야 함	Dynamic Programming

O-Notation 유형 별 연산 시간 추이

 

 

알고리즘 표현을 위한 순서도

순서도 기본

기호	이름	의미
	단자 (Terminal)	순서도 시작과 끝
	준비 (Preparation)	변수 선언 및 초기 값 부여 / 배열 선언
	처리 (Process)	값 계산 또는 대입 기호
	판단 (Decision)	참 거짓 판단 또는 조건에 맞는 경로 분기
	수동 입력 (Console)	키보드 이용한 수동 입력
	입/출력 (Input/Output)	데이터 입출력
	문서 (Document)	처리 결과 프린터로 출력
	흐름선 (Flow Line)	각종 처리 기호의 처리 흐름 연결
	연결자 (Connector)	다른 곳으로의 연결 표시
	순환 구조 (Loop)	상단에는 각각 초기화, 최종 값, 증가치 의미

 

순서도 기본 모형

직선형	분기형	반복형
처음 시작부터 마지막 종료까지 단계적으로 진행	조건에 따라 실행 내용이나 순서 달리하는 형태	조건 만족할 때까지 일정한 내용 반복 수행

 

알고리즘 기법

기법	설명
분할과 정복 (Divide and Conquer)	문제를 나눌 수 없을 때까지 나누고 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘
동적 계획법 (Dynamic Programming)	어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고 과거에 구한 답을 활용하는 방식의 알고리즘
탐욕법 (Greedy)	결정을 해야할 때마다 그 순간 가장 좋다는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 방식의 알고리즘
백트래킹 (Backtracking)	어떤 노드의 유망성을 점검한 후 유망하지 않으면 그 노드의 부모 노드로 되돌아가 다른 자손 노드를 검색하는 알고리즘

 

 

정렬 알고리즘

개념

컴퓨터 기억공간 내 여러 원소로 구성된 배열에서 레코드 특정 항목들을 순서 기준에 따라 재배치하는 알고리즘

 

01 선택 정렬

최소 원소를 찾아 제자리에 위치

void SelectionSort(int A[], int N) { int i, j, minIndex, temp; for(i = 0; i < N-1; i++) { minIndex = i; for(j = minIndex+1; j < N; j++) { if(A[minIndex] > A[j]) { minIndex = j; } if (minIndex != i) { temp = A[i]; A[i] = A[minIndex]; A[minIndex] = temp; } } } }

매우 느린 속도의 알고리즘으로 효율성 좋지 않고 안정성 만족하지 않음 키의 비교 횟수 (n-1) + (n-2) + ··· + 1 = n(n-1) / 2 → O(n²)

 

02 버블 정렬

왼쪽부터 모든 인접한 두 원소를 비교한 후 왼쪽의 원소가 더 크면 오른쪽 원소와 자리 변경하여 정렬해 나가는 방법

	void BubbleSort(int A[], int N) { int i, j, temp; for(i = 0; i < N-1; i++) { for(j = 1; j < N; j++) { if(A[j-1] > A[j]) { temp = A[j]; A[j] = A[j-1]; A[j-1] = temp; } } } }
	선택 정렬보다 자료 이동이 평균적으로 더 많음 최악의 경우 (내림차순으로 이미 정렬되어 있는 경우) O(n²)

 

03 삽입 정렬

두 번째 자료를 비교 기준 Key로 설정하고 그 앞의 자료들과 비교하여 삽입 위치를 지정한 후 자료 삽입하여 정렬하는 알고리즘. 자료 삽입 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 한 칸씩 자료들을 뒤로 이동시킴.

	void InsertionSort(int A[], int N) { int i, j, key; for(i = 2; i <= N; i++) { key = A[i]; j = i; while(A[j-1] > key) { A[j] = A[j-1]; j--; } A[j] = key; } }
	키 간 비교 횟수가 키들의 원래 순서에 민감하게 반응 자료 이동이 여러 번 발생 키가 내림차순으로 이미 정렬된 경우 (역순으로) 2 + 3 + ··· + n = n(n-1) / 2 - 1 → O(n²)

 

04 기수 정렬

낮은 자리 수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘. 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블 크기만한 메모리가 더 필요함

void Radix_Sort(int[] data) { int maxsize = getMaxlength(data); ArrayList<Linear_Queue> bucket = new ArrayList(); int powed=1; int index = 0; for(int i = 0; i < 10; i++) { bucket.add(new Linear_Queue(10)); } for(int i = 1; i <= maxsize; i++) { for(int j = 0; j < data.length; j++) { bucket.get((data[j]/powed)%10).EnQueue(data[j]); } for(int k = 0; k < 10; k++) { int bucket_num = bucket.get(k).rear; for(int n = 0; n <= bucket_num; n++) { data[index] = bucket.get(k).DeQueue(); index++; } } index =0; powed *=10; } } int getMaxlength(int[] data) { int maxsize = 0; for(int i = 0; i < data.length; i++) { int length = (int)Math.log10((double)data[i])+1; if(maxsize <length) { maxsize = length; } } return maxsize; }

0 ~ 9 까지의 Bucket (Queue 자료구조) 준비 모든 데이터에 대해 가장 낮은 자리 수에 해당하는 Bucket에 차례대로 데이터 저장 0부터 차례대로 Bucket에서 데이터 다시 가져옴 가장 높은 자리 수 기준으로 자리 수를 높여가며 위의 2, 3번 과정을 반복함

 

 

소스 코드 품질분석 도구

개념

소스 코드에 대한 코딩 스타일, 설정된 코딩 표준, 코드 복잡도, 코드 내 존재하는 메모리 누수 현황, 스레드 결함 등을 발견하기 위해 사용하는 분석 도구.

 

 

소스코드 품질도구 종류

정적 분석 도구 (Static code analyzer)

• 작성된 소스 코드를 실행하지 않고 코드 자체만으로 코딩 표준 준수 여부, 코딩 스타일 적정 여부, 잔존 결함 발견 여부 확인하는 코드 분석 도구
• 사전에 결함 발견하고 예방하는 도구, 코딩 표준 준수 여부 분석 도구, 소스 코드 복잡도 계산 도구 등이 있음

 

동적 분석 도구 (Dynamic code analyzer)

• 애플리케이션 실행하여 코드에 존재하는 메모리 누수 현황 발견 및 발생한 스레드 결함 등을 분석하기 위한 도구

 

구분	도구명	도구 설명	지원 환경	개발도구 지원
정적 분석 도구	pmd	자바 및 타 언어 소스 코드에 대한 버그, 데드 코드 (Dead code) 분석	Linux, Windows	Eclipse, NetBeans
		Eclipse에 임베드 되어 사용됨
	cppcheck	C/C++ 코드에 대한 메모리 누수, 오버플로우 등 문제 분석	Windows	Eclipse, gedit, Visual Studio
		배열 범위 체크, 클래스 체크, 메모리 누수 체크, null pointer 체크 등 발생 가능한 결함에 대한 오류 검출
	SonarQube	소스 코드 품질 통합 플랫폼, 플로그인 확장 가능	Cross- Platform	Eclipse
	checkstyle	자바 코드에 대한 코딩 표준 준수 검사 도구	Cross- Platform	Ant, Eclipse, NetBeans
		Sun Check RuleSet 제공
	CodeSonar	Microsoft C# assembly 파일과 디버깅 정보 (.pdb 파일) 기반으로 분석 수행하여 이에 상응하는 소스 코드 (.cs 파일) 통해 검출된 결과 출력	Windows	Eclipse, Visual Studio
	Splint	C 코드 분석하여 오류 검출하는 도구	Cross- Platform	Visual Studio
코드 복잡도	ccm	다양한 언어 코드 복잡도 분석 도구로 Linux, Mac 환경 CLI 형태 지원	Cross- Platform	Visual Studio
	Cobertura	Jcoverage 기반 테스트 커버리지 측정 도구	Cross- Platform	Ant, Maven
	McCabe lQ	컴포넌트 McCabe 복잡도 계산	Cross- Platform	Eclipse, Visual Studio
동적 분석 도구	Avalanche	Valgrind 프레임워크 및 STP 기반 소프트웨어 에러 및 취약점 동적 분석 도구	Linux, Android
	Valgrind	자동화된 메모리 및 쓰레드 결함 발견 분석 도구	Cross- Platform	Eclipse, NetBeans
		메모리 관리에 관련된 오류 검출 및 Cache, Heap, Multi Thread 프로파일링 지원하는 오픈소스 도구