[알고리즘] 알고리즘이란?

📌알고리즘

컴퓨터 과학에서 알고리즘이란 문제를 푸는 절차와 과정을 일컫는다. 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것을 뜻한다.

 

📌조건

1. 입출력: 0개 이상의 외부 입력과 1개 이상의 출력을 생성한다.

2. 명확성: 각 명령은 모호하지 않고 명확해야한다.

3. 유한성: 한정된 수의 단계를 거친 후에는 반드시 종료해야한다.

4. 유효성: 모든 명령은 컴퓨터에서 수행할 수 있어야 한다.

5. 효율성: 알고리즘은 효율적이어야 한다.(실용적 관점)

 

주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는 유한 개의 일련의 명령어들을 순서에 따라 구성한 것을 알고리즘이라 한다.

 

 

📌설계

주어진 문제와 조건은 매우 다양하기 때문에 일반적/범용적인 설계 기법은 존재하지 않는다.

알고리즘 생성 과정: 설계, 표현(기술), 정확성 분석, 효율성 분석

 

욕심쟁이(greedy, 탐욕적) 방법

전후 단계의 선택과 상관 없이 각 단계마다 가장 최선이라고 여겨지는 국부적인 최적해를 선택해나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인(최적해를 보장하지 못함) 전략을 취하는 방법.

단점: 국부적인 최적해가 전체적인 최적해가 아닐 가능성이 높음.

ex) 거스름돈 문제(단, 동전의 액면가가 일반적인 경우 최적해를 구할 수 없음), 배낭 문제(단, 물체를 쪼갤 수 없는 경우 최적해를 구할 수 없음)

 

분할 정복(Divide and Conquer) 방법

하향식 접근 방법. 주어진 문제의 입력을 더이상 나눌 수 없을 때까지 순환적으로 2개 이상의 작은 문제들로 나누고, 이렇게 분할된 작은 문제들을 각각 해결한 후 해로 결합하여 원래 문제의 해를 구하는 방식.

ex)  퀵 정렬, 합병 정렬, 이진 탐색

 

동적 프로그래밍(Dynamic Programming) 방법

입력의 크기가 가장 작은 부분 문제부터 해를 구하여 테이블에 저장하고, 이를 이용하여 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법.

ex) 플로이드 알고리즘(모든 쌍 간의 최단 경로) 문제, 연쇄적 행렬 곱셈 문제, 최장 공통 부분 수열 문제

 

 

 

📌분석

정확성 분석

유효한 입력에 대해 유한 시간 내에 정확한 결과를 생성해내는 지에 대한 여부.

 

효율성 분석

알고리즘 수행에 필요한 자원의 양을 평가.

- 공간 복잡도(메모리의 양)

- 시간 복잡도(실행에서부터 완료까지 걸리는 시간)

 

시간 복잡도

알고리즘의 수행 시간. 입력 크기 n에 따라 실행되는 조작의 수. 알고리즘의 각 문장이 수행되는 횟수의 합. -> 입력 크기의 함수로 표현.

일반적으로 알고리즘의 시간 복잡도는 최악의 수행 시간을 사용함.

최악의 수행 시간으로 따졌을 때 상대적으로 알고리즘 성능의 우열을 가리기 쉬움.(ex 출근 시간 예상)

 

점근 성능

입력 크기 n이 무한히 커짐(증가하는 추세)에 따라 결정되는 성능. 

- 입력 크기가 충분히 커짐에 따라 함숫값에 가장 큰 영향을 미치는 차수(항)을 찾음.

- 수행 시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현.

- 수행 시간의 정확한 값이 아닌 어림값임. -> 수행 시간의 증가 추세 파악 가능. 알고리즘 간의 우열을 따질 수 있음.

Big O 표기법

O(1)  <  O(logn)  <  O(n)  <  O(nlogn)  <  O(n^2)  <  O(n^3)  <  O(2^n)

입력 크기가 커지더라도 수행 시간이 천천히 증가하는 알고리즘이 성능이 좋은 알고리즘임.

 

알고리즘의 시간 복잡도 구하기

기본 연산 수행 횟수의 합 f(n)을 구한 후, f(n)=O(g(n))을 만족하는 최소 차수 함수 g(n)을 찾는다.

-> 알고리즘의 모든 문장이 아닌 루프의 반복 횟수만을 조사하여 최고 차수를 시간 복잡도로 표기하면 알고리즘 성능의 우위를 가릴 수 있음.

 

i = 1;			// 1
while(i <= n) {		// n + 1
	x = x + 1;		// n
    i = i + 1;		// n
}

 

위 알고리즘에 대하여 `f(n) = 3n+2` 이므로, 최고 차항을 뽑아 계수 없이 `O(n)`으로 표기할 수 있음. -> 루프의 반복 횟수와 동일.

 

 

📌순환(재귀 recursion) 알고리즘

알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 상태.

순환 알고리즘의 수행 시간은 점화식 형태로 표현되며, 이를 풀어서 폐쇄형을 구할 수 있음.

- 퀵 정렬(최악) T(n) = T(n-1) + O(n), T(1) = O(1)  -> T(n) = O(n^2)

- 이진 탐색 T(n) = T(n/2) + O(1), T(1) = O(1)  -> T(n) = O(logn)

- 퀵 정렬(최선), 합병 정렬 T(n) = 2T(n/2) + O(n), T(1) = O(1)  -> T(n) = O(nlogn)