알고리즘 1. Problem Solving의 절차

1. Analyzing Algorithms and Problems: Principles and Examples

-알고리즘 & 문제 complexity 분석

 

 

1-1. Introduction

 

컴퓨터 알고리즘

상세한 단계별(step-by-step) 방법으로 유한 시간(finite time) 이내 컴퓨터를 이용해 문제를 해결하는 것

 

Problem Solving의 체계적 절차

Problem(문제 정의) > Strategy(문제풀이 전략) > Algorithm(알고리즘, 의사코드 서술) > Anaysis(서술한 알고리즘을 분석) > Implementation(구현) > Verification(검증)

 

1. Problem 문제 정의 ex. 비정렬 배열을 정렬하는 알고리즘

input : 5, 3, 67, 1, 2 -> n개의 정수

output: 1, 2, 3, 5, 67 -> 오름차순 정렬된 n개의 정수

 

2. Strategy 전략

 

3. Algorithm 알고리즘 서술(의사코드)

Input

Output

Step

세 가지 요소를 작성

 

4. Analysis 서술한 알고리즘 분석

Correctness 정확성

Time & Space 효율성(efficiency)

• Time(수행시간이 얼마나 빠른지)
• Space(storage usage, 저장공간을 얼마나 사용하는지)

Optimality 최적성

• 더 이상 빠르게 문제를 풀 수 없음
• 알고리즘 복잡도 = 문제 복잡도: Optimal algorithm
• 복잡도 complexity: 문제를 해결하기 위한 일의 양의 최솟값

 

Example: 비정렬 배열 탐색

Problem 문제정의

Input 

배열 E(원소 n개를 포함, 원소들은 정렬되지 않은 상태)

Output

1. 특정 key K가 배열 내에 존재한다면, K의 인덱스를 출력

2. K가 배열 내에 존재하지 않는다면, -1 출력

 

Strategy 전략

• 남은 배열이 없을 때까지, 배열의 처음부터 끝까지 순차적으로 K와 비교
• 만약 K가 배열 내에 존재하지 않는다면, -1 출력

 

Algorithm 알고리즘 서술(의사코드)

Input

• E(배열)
• n(배열의 항목 갯수)
• K(찾는 key)
• → 모두 정수라고 가정

Output

• E에서 K의 위치인 ans를 반환(K를 찾지 못하면 -1 반환)

 

Algorithm: Step

int seqSearch(int[]E, int n, int K)

int ans, index;
ans = -1; //Assume failure.
for(index = 0; index < n; index++)
	if(K==E[index])	//basic operation
    	ans = index; //success
        break; //done
return ans;

 

Analysis 서술한 알고리즘 분석

<의사코드를 이용해 이론적 분석을 이용하는 이유>

• 실험적 방식을 사용하기 위해서는 알고리즘 구현이 필수적이다(프로그래머의 역량 필요)
• 테스트 케이스 이외의 input에 대한 실행결과를 알 수 없음
• 하드웨어 및 소프트웨어의 성능에 따른 실행결과의 차이 배제
• 모든 가능한 input에 대한 고려 가능

<알고리즘에 의해 수행된 일의 양을 측정하는 방법>

기본연산(primitive operation) 일일이 카운팅

• primitive operation: 컴퓨터 시스템이나 패키지 내에서 가장 근본이 되는 최소 단위의 연산으로서 마이크로 연산으로 간주되는 기본 연산. 원시 연산의 몇 단계가 모여 보통 하나의 매크로 연산으로 정의된다.(출처: 네이버 지식백과 it용어 사전) ex. memory access, +, - , *, /, %, store, ....

Basic Operation

• 해당 알고리즘에서 가장 기본이 되는 연산
• 해당 예제의 경우 basic operation은 비교연산

Worst-Case Analysis 최악의 수행시간

• 함수로 표현☞ W(n): 알고리즘이 임의의 input size n에 대해 수행하는 최대 기본 연산 수.
• 해당 예제의 경우, W(n) = n이다. → 최악의 경우(K가 배열의 인덱스 n-1에 존재할 시 or K가 배열 내에 존재하지 않을 시), 인덱스 0부터 n-1까지 n번 비교연산이 필요하다.

 

추가적인 알고리즘 분석 방법

• Average-Behavior Analysis 평균수행시간 비교
• Optimality
• Correctness

 

알고리즘 언어(의사코드 서술 방식)

• 언어제약이 없다
• 알고리즘의 각 단계는 pseudo-code로 명시되어야 한다. 
• 지나치게 디테일한 내용을 작성하기 보다 문제 해결 시 전략이나 테크닉에 초점을 맞추어 영어식 표현으로 서술한다.

 

 

 

 

 

 

---

자료 출처

Computer Algorithms

(Sara Baase, Allen Van Gelder저, Addison Wesley, 2000)