01. 알고리즘이란

* 문제와 해결방법

2 + 3 = ?
3 + 5 = ?
5 + 2 = ?
...

위와 같은 상황일 때, 알고리즘의 측면에서 문제는 한 개임.
일반적으로 말하는 문제를 여기선 인스턴스라고 함.
즉, 위에는 인스턴스가 3개인 것임.
해당 과목에서 "문제(Problem)"와 "인스턴스(Instance)"는 구분되어 사용됨에 유의할 것.
 

- 한 문제는 많은(대체로 무수히 많은) 인스턴스를 가짐.

예를 들어,
두 양의 정수가 주어졌을때, 최대공약수(GCD, Greatest Common Divisor) 구하기라는 "문제"가 있을 때, 461,952 와 116,298 의 최대공약수를 구하기 (정답 = 18) 와 같은 "인스턴스"가 얼마든지 생성 될 수 있음.
 

* 일반화

문제 P )   f : D -> R 인 f를 구해라. (D는 Domain(정의역)의 약자, R은 Range(치역)의 약자)
문제 P의 답) f 를 구하는 알고리즘.
 
인스턴스) 집합 D에 속한 d가 주어졌을 때, f(d)의 값을 구해라.
인스턴스의 답) f(d)의 값.
 

+ 최대공약수 구하기 문제의 가능한 해답들

1. 알고리즘 n_gcd(m, n)

# Pseudo Code
i <- min(m, n) + 1
repeat i <- i-1
   until i divides both m,n
return i

2. Euclidean(유클리드) 알고리즘1
= 알고리즘 e_gcd1(m,n)  (m>n)

while ( n != 0 )
{ 
   tmp = m;
   m = n;
   n = tmp mod n;
}
return m;

3. Euclidean(유클리드) 알고리즘2
= 알고리즘 e_gcd2(m,n)  (m>n)

if ( n == 0 ) return m;
else return e_gcd2( n, m mod n );

※ e_gcd1 과 e_gcd2 는 같은 알고리즘임.
 

- P) f : D -> R

f를 구할 알고리즘이 존재하다면 P는 해결(solved)이라고 하며,
존재하지 않는다면 미해결(unsolved)이라고 하며,
존재할 수 없음이 증명되었다면 해결불가능(unsolvable)이라고 함.
+ 추가로 해결가능(solvable)도 있음.
 

* 알고리즘이란?

해결가능 문제의 해결방법을 위해 컴퓨터가 사용가능한 정확한 수단.
알고리즘은 문제의 모든 인스턴스에 대해 정확히 동작해야 함.
※참고※ 알고리즘 문제 풀이 순서
문제 정의 -> 알고리즘 설계 -> 증명 ( Correctness정확도, Efficiency효율성 측면에서 ) <-> 반례
 

- 명령어의 유한(Finite)한 진행이며,

각각의 명령어는 분명(Definitive)하고 효과적(Effective)이어야하고,
결과가 올바르고(Correct),
명령어의 실행이 종료(Terminate)가 되어야 함.
(마지막 조건에 의해, OS는 종료되지 않기 때문에 알고리즘이 아님)
 

- 알고리즘의 필요 조건(Necessary Condition)

1. 입력 : 0개 이상
2. 출력 : 1개 이상
3. 분명함 : 결정론적(Deterministic)이고, 모호하지 않음(Unambiguous).
4. 유한함 : 종료되어야 함.
5. 효과적임 : 기본 명령어들로 해결되어야 함.
 

* 프로그램

특정 언어로 알고리즘을 구현한 것.
자료 구조.

- 주어진 문제를 해결하기 위해 컴퓨터 프로그램을 작성하는 과정

1. 문제 정의
2. 구체화 : 수학적 모델링
3. 해결방법 설계(i.e. 알고리즘 설계)
   ㄴ 추상적 자료구조가 필요함(ex. C언어 - 구조체)
   ㄴ 증명 : 알고리즘의 정확성을 수학적으로 입증
4. 구현
   ㄴ 자료 구조와 프로그래밍 언어를 결정
   ㄴ 증명 : (프로그램의) 정확도와 유한성
5. 테스트
   ㄴ 디버깅
   ㄴ 대체로 샘플링(샘플 데이터)을 통해 테스트 됨. 하지만 수학적 증명도 필요함.
6. 문서화
7. 해결법 평가(or 분석)
   ㄴ 효율성이 더 나은 최적의 해결법이 있는가?
   ㄴ 두 알고리즘을 비교하는 기준
      a. 소스코드 가독성 - 유지보수를 쉽게함
      b. 디버깅 난이도
      c. 공간, 속도 측면의 효율성 (각각 메모리와 실행 시간에 해당함)
      d. 실용적인 입력 크기
      e. 기계, 프로그래밍 언어, OS 독립성
※ 이번 알고리즘 과목은 4, 5, 6번 항목을 다루지 않음.
 

- 알고리즘 분석 (알고리즘의 복잡도)

문제가 주어지면, 알고리즘이 존재함.
이 알고리즘을 다른 것들과 비교하는 방법은?
=> 문제의 더 큰 인스턴스를 해결하는데 필요한 시간과 공간의 증가하는 정도(= 함수)를 비교함

정렬 알고리즘 예시

* 크기

어떤 방식으로든 측정되는 인스턴스의 요소 수를 의미함. (정렬의 경우 비교대상의 수, 그래프 문제에선 노드 수 등)

- 문제의 크기 (= 입력 크기) n

입력을 인코딩하기 위한 비트의 수, 하지만 문제에 따라서는 본인이 세고 싶은 것으로 정해도 됨. (그래프에서 노드 수를 이용해도 되지만, 간선의 수를 이용해도 됨.)
 

* 복잡도(Complexity)

1. 공간 복잡도 : 문제 크기를 문제 해결에 필요한 공간에 매핑하는 함수
2. 시간 복잡도 : 문제 크기를 문제 해결에 필요한 시간에 매핑하는 함수

정렬 알고리즘 예시

=> n이 무한대로 발산하면 최고차항이 제일 중요함. => 이를 Asymptotic(점근) 시간복잡도라고 함
 

- 최악(Worst case) 복잡도

   ㄴ 입력의 크기가 n인 경우에 걸리는 최대의 시간.
   ㄴ 해당 사이즈(n)에서 나올 수 있는 최악의 경우.
 

- 평균 복잡도

   ㄴ 입력의 크기가 n인 경우에 걸리는 평균적인 시간.
 

- 두 방법간의 비교

   ㄴ 최악이 가지는 장점
      a. 상한이 있음. (더 나빠지지 않음)
      b. 성능이 보장됨.
      c. 분석이 쉬움.
 

* Asymptotic Notations (점근 표기법)

- O (Big-Oh) 표기법

$f(n) = O(g(n))$. Order of at most(최악의 순서).
$|f(n)| ≤ |c·g(n)|$ 를 만족 시키는 $n\geq n_0$에 대해, 양수 $n_0$와 c가 존재함.
$g(n)$은 $f(n)$의 상한임.

f(n) = O(g(n)) 예시

f(n) = O(g(n)) 그래프 보충설명

- 추이(Transitive) 속성 만족

$f(n) = O(g(n))$ 이고, $g(n) = O(h(n))$ 이면, $f(n) = O(h(n))$ 임.
   ㄴ 보조정리(Lemma) : Maximum Rule
      $O(f+g) = O(max\{f, g\})$
      e.g. $O(n^3+ n^2) = O(max\{n^3, n^2\}) = O(n^3)$
 

- Ω (Omega) 표기법

$f(n) = Ω (g(n))$. Order of at least(최소의 순서).
$|f(n)| ≥ |c·g(n)|$ 를 만족 시키는 $n\geq n_0$에 대해, 양수 $n_0$와 c가 존재함.
$g(n)$은 $f(n)$의 하한임.
 

- θ (Theta) 표기법

$f(n) =θ(g(n))$.
일치(Exactly).
$f(n) = O(g(n)) = Ω(g(n))$
※ 정확도는 세타가 가장 좋지만, 빅오도 구해야 하고 오메가도 구해야 하기 때문에 오래걸림.