알고리즘 이론 1강. 알고리즘의 개요

 

# 알고리즘이란?

: 어떠한 입력을 어떠한 출력으로 변환하는 정확하고 명백한 계산 과정.

: 어떤 입력(어떤 값, 값 집합)을 어떤 출력(어떤 값, 값 집합)하는 잘 정의된 계산 절차

: 잘 정의된 계산 문제를 풀기 위한 도구

 

 

 

# 알고리즘 문제에서 발견되는 특징

1. 수많은 후보해가 있지만, 그중 대표의(최상의) 해를 찾는것이 어렵다.

2. 실용적인 응용 예시가 존재한다.

 

 

 

# 알고리즘의 필요성

: 아무리 컴퓨터가 속도가 빠르고 용량이 무한해도 결국 한정된 값이 존재.
: 자원의 효율적인 사용, 시공간적 효율적인 알고리즘이 필요!

 

 

 

# 알고리즘 vs 프로그램 코드

– 알고리즘

  : 실제 프로그램의 추출(abstraction)

  : 끝이 있는(terminates) 계산 절차

  : 한정된 절차의 구성

 

– 프로그램 코드

  : 프로그래밍 언어에서 알고리즘의 표현수단

 

 

 

# 알고리즘의 특징

1. Description(서술) : 알고리즘은 여러가지 예시들로 묘사된다.

2. Specification(차별성, 구별성) : 알고리즘은 의사 코드(pseudo code)로써 묘사된다.

3. Vaildation(확인) : 알고리즘은 모든 문제 케이스에 대해 옳다는 것에 대해 증명된다.

4. Analysis(분석) : 알고리즘의 시간, 공간 복잡성이 진화된다.

 

 

 

# 알고리즘의 디자인

1. simple(간단함) : Unambiguous(명백함)

2. Feasible(실행가능한)

3. Cost Effecive(경제적인) : CPU 시간 / 메모리 사용 / 상호작용 / 에너지

 

 

 

# 알고리즘의 진화

: 우리는 알고리즘의 수행을 시간, 공간 기준으로 진화시킨다.

: 알고리즘 실행 시간은 다음과 같은 것들에 의해 결정된다.

  – 데이터의 개수

  – 다항식의 깊이

  – 정렬되야되는 파일의 크기

  – 그래프내 노드의 개수

: 컴퓨터 과학은 요구되는 시간, 공간적 에너지를 최소화하기위해 노력(endeavor)해야한다.

 

 

 

# 문제 해결 과정

[문제]–분석–> [문제 명세]–디자인–> [알고리즘]–구현–> [프로그램]–컴파일–> [실행]

 

 

 

# 기술로써의 알고리즘

– 효율성(Efficiency)

: 동일한 문제를 푸는 알고리즘이라해도 효율성에서 극적인 차이가 있을 수 있다.

 

– 공간 효율성(Space efficiency)

: 일반적으로 두가지 상태로 나뉨(직관적)

: 여유 있으면 ok, 여유 없으면 실행불가.

 

– 시간 효율성(Time efficiency)

: 알고리즘의 효율성이라 할때 보통 시간 효율성을 의미.

: 얼마나 빠른 시간안에 문제 해결이 가능한가?

 

 

 

# 알고리즘의 효율성 예시

– 두개의 정렬 알고리즘 : 삽입 정렬(Insertion sort), 병합정렬(Merge sort)

- 삽입 정렬의 시간 복잡도 : n^2 - 병합 정렬의 시간 복잡도 : nlog(n) => 정렬하는데 병합 정렬이 시간이 덜 소모된다. - 그러면 다음과 같이 상황을 가정. A 컴퓨터(초당 10^9 실행) 로 삽입정렬 수행 B 컴퓨터(초당 10^7 실행) 로 병합정렬 수행 c1 = 2 , c2 = 50 컴퓨터 A가 B보다 100배 빠르다. 결과) A 수행시간 : 2(10^6)2 / 10^9 = 2000 초 B 수행시간 : 50(10^6)log(10^6) / 10^7 = 약 100 초 컴퓨터 B가 20배 더 빠름!

 

 

# 결론

– 더 빠른 컴퓨터 만드는 것보다 더 효율적인 알고리즘을 사용하는게 더 효율적이다!