알고리즘 기초

• 정렬: O(n^2)
• 정렬: O(nlogn)
• 탐색
• 스트링
• 동적 프로그래밍
• NP-완전 문제
• 병렬 알고리즘
• 유전 알고리즘

알고리즘 소개

알고리즘 기본개념

주어진 문제에 대한 결과를 생성하기 위해 모호하지 않고 컴퓨터가 수행가능한 유한개의 일련의 명령을 순서적으로 구성한 것

다음의 조건을 만족한다

• input & output: 0개 이상의 외부입력과 1개 이상의 출력이 있어야 함
• definiteness: 명령은 모호하지 않고 명확해야 한다
• finiteness: 한정된 수의 단계를 거친 뒤 반드시 종료해야 한다
• effectiveness: 모든 명령들은 실행 가능해야 한다

알고리즘 설계

일반적으로 적용할 수 있는 알고리즘 설계기법은 존재하지 않음

비교적 많은 부류의 문제에 사용할 수 있는 기법으로는 greedy, divide and conquer, dynamic programming 등이 있음

분할정복 (divide and conquer)

순환적으로 문제를 푸는 방법

문제를 더 이상 나눌 수 없을 때까지 작은 문제로 나누고, 나누어진 작은 문제를 각각 해결한 후 결합하여 원래의 문제를 해결하는 방식

• 분할(divide): 주어진 문제를 여러개의 작은 문제로 분할
• 정복(conquer): 작은 문제를 순환하여 더 이상 분할되지 않을때까지 분할함
• 결합(combine): 작은 문제의 정복된 해를 결합하여 원래 문제의 해를 구함

분할 정복을 적용한 알고리즘: 퀵정렬, 합병정렬, 이진탐색, 선택문제(n개의 원소중 i번째 작은원소 찾기...) ...

동적 프로그래밍 (dynamic programming)

주어진 문제를 여러 개의 부분문제로 분할하고 가장 작은 부분부터 해를 구한뒤 이를 이용하여 입력크기가 큰 문제를 해결해 나가는 방법

동적 프로그래밍을 적용한 알고리즘: 플로이드 알고리즘(모든 쌍의 최단경로 찾기) ...

욕심쟁이 (greedy)

어떤 기준에 따라 전후단계의 선택과 상관없이 각 과정마다 최적해를 선택해나가면 결과적으로 전체적인 최적해를 얻을 수 있을 것이라 기대하는 방법 따라서 적용범위는 제한적이다.

욕심쟁이 방법을 적용한 알고리즘 : 프림 알고리즘(최소비용 신장트리), 크루스칼 알고리즘, 데이크스트라 알고리즘(단일 출발점에서 최단경로 구하기), 거스름돈 문제, 배낭문제

거스름돈 문제

가게에서 고객에게 돌려준 거스름돈이 T 만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법은? 동전은 500원, 100원, 50원, 10원, 5원, 1원의 6종류가 있다고 가정

욕심쟁이 해법은 액면가가 큰 동전부터 뽑아서 거스름돈을 만드는 것

배낭문제

최대 용량이 M인 배낭 하나와 무게 Wi, 이익Pi인 물체 n개가 있을 때, 배낭에 담을 물체의 이익을 최대화 하는 방법은?

욕심쟁이 해법은 단위 무게당 가장 이익이 많이 나는 물체를 순서대로 반복해서 넣으면 된다.

알고리즘 분석

알고리즘은 정확하고 효율적이어야 한다

정확성 분석

알고리즘에 유효한 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성해야 한다

효율성 분석

알고리즘을 수행하기 위해서 필요한 컴퓨터 자원 (메모리, 주변창치, 수행시간)의 측정을 통해 이루어짐

공간 복잡도 (space complexity)

알고리즘을 실행시켜 완료까지 필요한 총 메모리의 양을 말함 (정적 공간 + 동적 공간)

시간 복잡도

알고리즘을 실행시켜 완료하는 데 걸리는 시간

일반적으로 알고리즘의 총 수행시간은 단위 연산이 몇 번 수행되는가에 거의 비례한다

알고리즘의 수행시간은 주어진 입력 데이터의 상태에 영향을 받는다. 따라서 다양한 형태의 입력에 따라 수행되는 시간의 평균, 최선, 최악을 구하는 것이 필요하다.

점근성능

알고리즘 성능은 입력의 크기에 따라 달라지므로, 데이터의 양이 무한히 많아지는 상황을 전제로 알고리즘의 성능을 표현하는 것이 바람직하다

알고리즘의 성능은 단위 연산의 실행 빈도수를 통해 유도된 다항식의 수행시간에 대해서, 최고차항만을 이용하여 표시된다.

최고차항을 이용한 성능 표기값은 어림값이므로 정확한 성능을 표현할수는 없을지라도 알고리즘 간의 성능비교가 용이하고 데이터 개수의 증가에 따른 알고리즘 수행시간 증가추이를 쉽게 파악할 수 있다.

점근 성능을 표기하는 대표적인 방법으로 다음 세 가지 방법이 있다

함수 f와 g를 각각 양의 정수를 갖는 함수라 하면

• Big-oh (O): 어떤 양의 상수 c와 n0가 존재하여 모든 n >= n0에 대하여 f(n) <= cg(n)이면 f(n) = O(g(n))이다
• Big-omega (Ω): 어떤 양의 상수 c와 n0가 존재하여 모든 n >= n0에 대하여 f(n) >= cg(n) 이면 f(n) = Ω(g(n))이다
• Big-theta (Φ): 어떤 양의 상수 c1, c2와 n0가 존재하여 모든 n >= n0에 대하여 c1g(n) <= f(n) <= c2g(n)이면 f(n) = Φ(g(n))이다

함수 f(n)은 일반적으로 알고리즘의 수행시간을 나타낸다

이때 f(n)이 O(g(n))이라면, n이 무한히 커지더라도 f(n)의 값은 결국 g(n)의 상수 배보다 적다는 것을 의미한다 다시말해 O 표기법의 성능은 최악의 경우에 대해서도 알고리즘의 수행시간이 O(g(n))이 되고 g(n)을 함수의 점근적 상한이라 표현한다.

Ω(g(n))은 f(n)의 점근적 하한을 의미하며, 알고리즘 최선의 경우를 의미한다.

f(n)이 g(n)을 점근적 상한과 하한을 동시에 갖는경우 Φ 표기법을 사용한다.

예를 들어 복잡도 함수가 O(n^3)이라는 것은 점근적 상한 수행 시간이 n^3을 넘지 않는 함수 f(n)의 집합이다. 따라서 f(n)이 반드시 3차 함수일 필요는 없고 3차 함수 아래에 놓이기만 하면 된다

점근성능의 효율성

주어진 함수 f(n)의 최고차항으로 표시한 점근성능의 연산시간 순서는 다음과 같다

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

순환 알고리즘의 성능 (recursive)

이진 탐색(binary search) 알고리즘의 경우 주어진 리스트 중앙값과 탐색값의 비교를 통해 크기가 반으로 줄어든 리스트를 대상으로 동일한 이진 탐색과정을 반복한다.

이와 같이 알고리즘의 수행과정에서 자신의 알고리즘을 다시 수행하는 형태를 순환/재귀(recursive) 알고리즘이라 부른다.

순환 알고리즘의 수행시간을 나타내기 위해 점화식이 사용된다.

n은 1보다 큰 경우 T(n)을 다음과 같은 점화식으로 표현할 수 있다.

T(n) = T(n/2) + c2, T(1) = c1

위 식을 전개하여 점화식의 폐쇄형을 구하면 다음과 같다

T(n) = T(n/2) + c2 = T(n/4) + c2 + c2
= T(n/2^2) + 2c2 = T(n/8) + c2 + c2 + c2
= T(n/2^3) + 3c2 = T(n/2^(k-1)) + (k-1)c2
= T(1) + kc2 (n = 2^k 인경우 정의 가능 k = log2n)
= c1 + kc2
= c1 + c2log2n

이를 점근 표기법으로 나타내면 O(logn)이 된다

몇 가지 기본적인 알고리즘의 점화식에 대한 폐쇄형을 정리하면 다음과 같다

점화식	폐쇄형	CASE
T(n) = T(n-1) + Φ(1), n >= 2	T(n) = Φ(n)
T(n) = T(n-1) + Φ(n), n >= 2	T(n) = Φ(n^2)	퀵정렬(최악)
T(n) = T(n/2) + Φ(1), n >= 2	T(n) = Φ(log2n)	이진탐색
T(n) = T(n/2) + Φ(n), n >= 2	T(n) = Φ(n)
T(n) = 2T(n/2) + Φ(1), n >= 2	T(n) = Φ(n)
T(n) = 2T(n/2) + Φ(n), n >= 2	T(n) = Φ(nlog2n)	퀵정렬(최선), 합병정렬