알고리즘 개념

알고리즘이란?

어떤 문제를 해결하기 위해서 잘 정리된 방법!

예를 들어, 요리를 하기 위해서 필요한 레시피를 알고리즘이라고 생각하면 된다.

 

컴퓨터 프로그래밍으로 예를 들면,

두 개의 숫자를 더하는 알고리즘에 a, b라는 숫자를 넣고 알고리즘을 통해서 계산한 값을 출력한다.

여기서 알고리즘은 

 

1. '+' 기호를 통해 두 개의 숫자를 더한다.

2. 그 값을 출력한다.

 

알고리즘은 input, output이 정확해야 하고, 그 단계가 명확해야 한다.

 

왜 사용해야 할까?

알고리즘은 다양한 방법이 있을 수 있고 그 중 가장 효율적인 방법을 통해서 문제를 해결해야 한다.

그러면 많은 방법 중 어떤 방법이 가장 효율적인지는 어떻게 계산하면 될까?

 

알고리즘 비교하기

알고리즘이 실행되는 시간을 정확하게 측정하는 것은 어렵다. 

알고리즘을 실행하는 언어, 동시에 실행되고 있는 프로그램, 운영 체제의 퀄리티 등에 영향을 받기 때문이다.

 

그래서 시간 복잡도와 공간 복잡도를 통해서 알고리즘을 평가한다.

- 시간 복잡도: 알고리즘이 실행되는데 걸리는 시간

- 공간 복잡도: 알고리즘이 실행되는데 필요한 메모리

 

그래서 주어진 환경에 있어서 가장 최선의 해결 방법을 사용하는 것이 좋다.

만약 애플리케이션이 엄청 빨라야 하고 메모리가 충분하다면 공간 복잡도를 생각하지 않아도 되고,

반대로 엄청 메모리 공간이 적다면 조금은 느리지만 메모리를 덜 쓰는 알고리즘을 택해야 한다.

 

복잡도를 나타내기

수학에서 시간, 공간 복잡도를 나타내는 방법으로 Asymptotic Notations 가 있다.

그리고 그 안에는 세 가지의 방법이 있다

 

1. Big-O Notation : 최악 케이스 복잡도

2. Omega Notation : 최고 케이스 복잡도

3. Theta Notation : 평균 케이스 복잡도

 

우리는 1번만 신경쓰면 된다. 왜냐면 ,, 면접에서 그것만 물어보니까 ,, ?