*학부에서 배운 강의 내용을 바탕으로 작성되었습니다*
컴퓨터 알고리즘이란?
"컴퓨터를 사용하여 문제를 해결하기 위한 상세한 단계별 방법"이라고 말할 수 있습니다.
컴퓨터를 사용해 문제를 해결하는 법
문제를 해결하는 법은 크게 6가지 단계로 나눌 수 있습니다.
- Problem
- Stratege
- Algorithm
- Input
- Output
- Step
- Analysis
- Correctness
- Time & Space
- Optimality
- Implementation
- Verfication
1. Problem
: 어떤 문제를 해결할지 정의합니다. 이때 문제는 명시된 입력과 출력으로 정의됩니다.
2. Strategy
: 문제를 어떠한 전략을 통해 해결할지 결정합니다.
3. Algorithm
: 결정한 전략대로 문제를 해결하려면 어떠한 알고리즘을 사용할지 결정합니다.
이때, Input을 알고리즘의 parameter, Output을 알고리즘의 return, Step을 Input을 Output으로 변경하는 절차라고 합니다.
4. Analysis
: 알고리즘에 대해 분석합니다.
이때, 알고리즘의 결과가 정확한지, 알고리즘의 공간 복잡도와 시간 복잡도가 어떠한지, 알고리즘이 Optimal한 지 분석합니다.
5. Implementation
: 알고리즘을 구현합니다.
6. Verification
: 구현한 알고리즘에 대해 증명합니다.
*학부 강의에서는 모든 문제의 해결을 이론적인 학부 강의 성격에 따라 1~4의 과정을 집중해서 배웠습니다.*
Example: 정렬되지 않은 배열의 탐색
정렬되지 않은 배열의 탐색을 예로 들어 문제를 해결해 보겠습니다.
1. Problem
E를 n개의 항목(E[0], E[1], ... , E[n-1])을 특정 순서로 포함하지 않는 배열이라고 하자.
지정된 키 K가 배열에 있으면 K의 인덱스를 찾아서 반환하고, K가 배열에 없으면 –1을 반환한다.
2. Strategy
배열의 각 원소와 K를 비교하면서 K와 일치하는 값이 존재하거나, 배열이 끝날 때까지 탐색한다.
만약 K가 배열에 존재하지 않으면 알고리즘은 답으로 -1을 반환한다.
3. Algorithm
Input : 알고리즘의 입력은 E, n, K이다. 여기서 E는 n개의 원소를 가진 배열이다. 그리고 K가 찾기를 원하는 키 값이다.
여기서는 단순하게 K와 E의 원소들이 정수라고 가정할 것이다.
Output : 배열 E에 존재하는 K의 인덱스를 반환한다. 만약 배열 E에 K가 존재하지 않으면 -1을 반환한다.
Step : Input을 OutPut으로 변환하는 과정은 아래 의사코드를 통해 작성했다.
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])
ans = index; // Success! break; // Done!
return ans;
4. Analysis
먼저 어떤 방식으로 알고리즘을 분석할까?
알고리즘은 실험 분석, 이론 분석 두 가지 방법으로 분석할 수 있습니다.
저는 이론 분석을 통해 알고리즘을 분석할 것입니다.
이유는 다음과 같습니다.
실험 분석의 단점
1. 복잡한 알고리즘을 직접 "구현"해야 한다.
2. 실험하지 않은 데이터에 대한 실험 결과를 알 수 없다.
3. 실험이 이루어지는 소프트웨어, 하드웨어 환경에 종속적이다.
이론 분석의 장점
1. 알고리즘의 수행시간을 입력 크기 n에 대한 함수로 표현이 가능하다.
2. 모든 가능한 n에 대한 알고리즘의 수행시간을 분석 가능하다.
3. 직접 구현대신 알고리즘을 상의 레벨에서 의사코드로 표현 가능하다.
4. 임의의 두 알고리즘을 비교할 때, 소프트웨어 하드웨어 환경에 독립적으로 평가 가능하다.
그다음으로, 어떻게 알고리즘이 수행하는 일의 양을 측정할 수 있을까?
Basic Operation(기본 연산)을 통해 측정할 수 있다.
이 예시에서 알고리즘의 기본연산은 K와 배열의 원소들을 "비교"하는 것이다.
그리고 Worst-Case에 대한 분석을 할 것입니다.
W(n)을 임의의 입력 크기 n에 대하여 알고리즘이 수행하는 최대 기본 연산의 수라고 가정하자.
그러면 이 예시에서는 W(n) = n임이 분명하다.
왜냐하면, 최악의 경우 찾고자 하는 키 값 K가 배열 E의 맨 마지막 위치에만 존재하거나 아예 없을 때이기 때문이다.
이 경우에는 항상 크기가 n인 배열 E의 처음부터 끝까지 탐색하며 비교연산을 수행해야 한다. 따라서 비교 연산을 배열 E의 크기인 n번만큼 수행한다.
알고리즘에 의해 수행된 일의 양
알고리즘에 의해 수행된 일의 양은 컴퓨터, 프로그래밍 언어, 프로그래머 및 기타 세부 구현정보와 무관한 메서드의 효율성에 대해 말해준다.
일반적으로 입력의 크기에 따라 알고리즘에 의해 수행된 일의 양이 결정된다.
Basic Operation(기본 연산)은 문제의 근본적인 연산을 식별한다.
수행된 일의 양은 기본 연산 수에 거의 비례한다.
입력이 정렬된 형태로 주어지는 경우나 입력 값의 범위가 제한된 경우 일의 양이 바뀔 수 있기 때문에 입력의 속성을 파악하는 것은 알고리즘의 수행에 영향을 끼친다.
Worst-Case Complexity
Worst-Case 분석
1. \( D_{n} \)을 문제에서 고려가능한 크기가 n인 i 모든 nput data들의 집합이라고 하자. 그리고 I를 \( D_{n} \)의 원소라고 하자.
2. t(I)를 입력 I에 대해 알고리즘이 수행하는 기본 연산의 수라고 하자.
3. W(n) = max{ t(I) | I \( \in \) \( D_{n} \)}으로 정의하자. 그리고 이를 알고리즘의 Worst-Case Complexity라고 한다.
즉, W(n)은 입력 크기 n에 대하여 알고리즘이 수행하는 최대 기본 연산의 수라고 할 수 있다.
Average-Case Complexity
Avergage-Case 분석
1. Pr(I)를 입력 I가 발생할 확률이라고 하자.
2. 그러면 알고리즘의 Average-Case의 동작을 다음과 같이 나타낼 수 있다.
A(n) = \( \sum_{ i \in D_{n}} \) Pr(I) * t(I)
3. t(I)는 알고리즘을 분석하여 결정할 수 있지만, Pr(I)는 확률이기 때문에 분석적으로 계산할 수 없다.
앞서 말한 예시인 정렬되지 않은 배열의 탐색에서의 평균 수행시간 분석은 다음 글부터 시작하겠다!
