[Algorithm] 1-1. Analyzing Algorithms and Problems - Introduction

[Algorithm 카테고리에는 알고리즘을 배우면서 얻은 지식에 관해 주로 다루겠다.

이번 시간에는 알고리즘과 문제를 분석하는 방법의 소개를 하겠다.

 

 

● Computer Algorithm

- 컴퓨터 알고리즘이란 컴퓨터를 이용하여 문제를 해결하는 잘 정의된 절차, 방법이다.

- 컴퓨터를 이용하여 문제를 해결하기 위해서는 먼저 문제를 명확하게 정의해야한다. 그렇지 않으면 문제를 정확히 해결할 수 없고, 엉뚱한 답이 나올 수 있다.

- 문제는 입력과 출력을 이용하면 명확하게 정의된다.

  → 어떤 상황, 즉 입력을 주고 원하는 결과, 즉 출력을 물어보는 것이 문제이다.

- 문제를 해결한다는 것은 입력을 출력으로 변환하는 잘 정의된 절차로, 입력을 이용하여 출력을 만들어내는 것이다.

 

 

 

● Problem Solving Using Computers

1. Problem

- 답을 올바르게 내기 위해서는 문제를 제대로 정의해야하고, 입력, 출력을 정의하는 것도 포함된다.

 

 

2. Strategy

- 이 문제를 어떻게 해결할 것인지 전략을 설정한다.

- 분할 정복, greedy technique, dynamic programming technique 등 알고리즘 설계 기법을 말하기도 하고, 이 문제가 해결되어야하는 환경에 대한 전략을 말하기도 한다.

- 예: 어떤 문제가 고성능의 PC 또는 서버에서 해결되어야할 때와, 상대적으로 computing power나 메모리 크기가 작은 소형 모바일 디바이스에서 해결되어야할 때는 전략이 다를 수 있겠다.

 

 

3. Algorithm

- Input

- Output

- Step

- 문제를 해결하는 절차 정의, 즉 알고리즘을 만든다.

- 알고리즘에는 입력, 출력, 절차가 명시되어야 함.

 

 

4. Analysis

- 3단계까지 옳게, 바르게 수행하면 문제는 해결된 것이다. 하지만 만들어진 알고리즘이 문제를 제대로 해결했는지를 알기 위해서는 이 알고리즘을 분석해야 한다. 분석은 크게 위의 세 가지 측면에서 수행한다.

① Correctness : 이 알고리즘이 옳은 알고리즘인지를 분석.

② Performance (Time & Space) : 성능에 대한 분석. 성능은 보통 시간과 공간 이 두 가지 측면에서 분석.

    → 지금까지 해온 분석이 이 성능 분석이고 특히 time.

③ Optimality : '최적성 분석' 이 알고리즘이 최선인가? 더 좋은 알고리즘은 없나?

 

 

5. Implementation

6. Verification

- 4단계까지 분석이 다 끝났을 때 실제로 구현을 해보고 검증하는 단계. 이론적으로 분석했을 때 성능이 우수하다고 해서 실제로 구현해봤을 때 항상 우수한 것은 아닐 수 있다. 5, 6단계도 중요하지만 우리는 이론 분석까지만 다루도록 하겠다.

 

 

 

이 과정들을 바탕으로 정렬되지 않은 배열을 탐색하는 예를 가지고 위의 단계를 수행해보겠다.

 

 

Step 1. Problem

- E가 n개의 입력을 가진 배열, 입력이라고 하고, E[0], E[1], ... E[n-1]은 순서가 없다.

- K라는 key를 인덱스로 하는 원소가 만약 배열에 있으면 찾는다.

- 만약 배열에 해당 원소가 없으면 -1을 반환한다.

 

 

Step 2. Strategy

- 배열이 끝날 때까지 처음부터 끝까지 K가 나올 때까지 다 찾는다

- 만약 K가 없으면 -1을 답으로 반환한다.

 

 

Step 3. Algorithm (and data Structure)

- 명확한 컴퓨터 알고리즘을, 만약 필요한 자료구조가 있으면 이를 이용하여 서술하는 단계이다.

- 입력은 E, n, K이고 단순함을 위해 K와 E의 원소들은 정수라고 하자.

- 출력은 E에서의 K의 위치이고, 만약 없으면 -1일 것이다.

 

 

알고리즘의 절차를 서술하는 방법은 flow chart(순서도), 의사 코드(pseudo code)의 두 가지가 있는데, 우리는 의사 코드를 사용하겠다.

 

int seqSearch(int[] E, int n, int K)
1. int ans, index;
2. ans = -1; // Assume failure.
3. for (index = 0; index < n; index++)
4.	if (K == E[index])
5.    	ans = index; // Success!
6.      break; // Done!
7. return ans;

 

 

Step 4. Analysis of the Algorithm

- 알고리즘 분석은 대부분 최악의 경우에 대한 시간 분석을 많이 한다.

- 알고리즘 분석은 '일의 양'을 측정하는 것으로, 예를 들어, 3 + 3 + 3 + 3 + 3과 3 * 5는 결과는 같지만 연산 수는 다르다. 연산을 적게 한 알고리즘이 성능이 좋은 것이다.

- Basic Operation

  → 기본 연산(사칙연산, 메모리에 읽고 쓰기, 제어문 등 실제 컴퓨터에서의 instruction set과 유사한 개념.

      우리는 대표적인 기본 연산만 세기로 한다.)

  → seqSearch에서는 찾는 이름과 배열의 원소가 같은지 비교하는 연산이 가장 주요 연산이다.

- Worse-Case Analysis

  → 가장 일을 많이하는 경우가 안 좋은 상황이다. W(n)을 함수로 두고 입력 크기가 n이라고 했을 때 기본 연산의

      최대 수행 횟수이다.

  → 우리의 경우에는 W(n) = n이다.

  → 이 경우에 최악의 경우는 배열의 맨 마지막에 우리가 원하는 원소가 있거나 아니면 배열에 애초에 찾는 원소가

      없었을 때일 것이다.

 

 

 

이렇게 분석까지 하고 나면 Optimality(최적성), Correctness(어떤 입력에 대해서도 옳은 출력을 내는지) 검사하면 된다.

의사 코드를 쓰면 세부적인 구현에 신경을 덜 쓰고 알고리즘의 전략과 설계 기법, 테크닉에 집중하게 해주어서 알고리즘 분석을 용이하게 한다.

 

 

 

 

다음 시간에는 알고리즘에 자주 사용되는 수학적 배경 지식에 대해 알아보도록 하겠다.