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

알고리즘이란?

알고리즘의 정의 

알고리즘이란 컴퓨터를 이용하여 문제를 풀기위한 방법을 과정이나 절차를 이용해 만들어 놓은 것으로

프로그래밍을 통해서 어떤 문제를 해결하려면 기본적으로 다음과 같은 순서로 작업을 합니다.

문제 정의 -> 알고리즘 설명 -> 정확성 증명 -> 성능 분석

문제 정의 (Problem Definition) : 해결하고자 하는 문제. 입력과 출력의 형태로 정의될 수 있어야 하고 컴퓨터가 수행할 수 있는 형태로 전환이 가능해야한다.

알고리즘 설명 (Algorithm Description) : 문제를 풀기 위해 수행해야하는 작업을 순서대로 나열하는 것. 일상 언어나 수도 코드등으로 표현.

정확성 증명 (Correctness Proof) : 주어진 알고리즘을 수행했을 때 문제를 풀 수 있는지 증명하는 과정. 문제의 해답을 찾아야 하고 정상적으로 종료되는지 확인해야 한다.

성능 분석 (Performance Analysis) : 알고리즘이 어떤 문제를 풀기 위해서 필요한 시간이나 공간 혹은 자원들이 얼마나 되는지 비교한다. 모든 알고리즘이 동일한 성능을 가진 컴퓨터에서 절대적인 수행시간을 측정하는건 힘들기 때문에 이를 객관적으로 비교하기 위해 점근적 분석이나 점근적 표기법을 사용한다.

실제 현업에서 일을 하다보면 해결방안 구상, 코딩, 디버깅이 뒤섞여서 진행되거나 아예 알고리즘 정리 없이 즉흥적으로 코딩을 하는 경우도 더러 있다. 당연히 올바른 프로그래밍 습관은 아니다. 바쁘다고 제대로 된 설계 없이 코딩부터 들어갔다가 오히려 시간을 버리는 경우를 많이 봤다.

알고리즘이란 문제를 이해하고 해결방안을 구상하는 것이라고 할 수 있는데 이 해결방안 구상이라는 것은 단순히 머리로만 생각하는 것이 아니라 논리적으로 명세화 시켜놓는 것을 말한다. 즉, 알고리즘은 논리적이어야 하고 반드시 명세화하여야 한다. 명세화 하는 방법은 여러가지가 있는데 순서도를 이용할 수도 있고, pseudo code를 짜거나 아니면 그냥 글로 기술할 수 도 있다. 중요한 것은 명세화를 해야한다는것이다.

알고리즘의 조건

입력 : 외부에서 제공되는 자료가 0개 이상 존재한다.

출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안됨)

명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.

유한성(종결성) : 유한 번의 명령어를 수행 후(유한 시간 내)에 종료한다.

효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 한다.

좋은알고리즘이란?

알고리즘을 짤 때는 항상 성능을 고려하여야 한다. 성능을 분석할 때는 공간복잡도와 시간복잡도 이 두 가지를 고려하여야한다. 

공간복잡도 (space complexity) : 총 저장공간의 양

시간복잡도 (time complexity) : 총 소요시간

공간복잡도는 프로그램 실행 시 필요한 고정 또는 가변 메모리의 양을 의미하고 시간복잡도는 프로그램의 컴파일 시간과 실행시간의 합을 의미한다.

좋은 알고리즘은 공간복잡도와 시간복잡도가 작은 알고리즘을 의미한다. 즉, 저장공간을 적게 사용하고 프로그램 수행시간이 적어야 한다는 것이다. 하지만 최근에는 공간복잡도보다 시간복잡도를 더 중요하게 생각하고 있다. 요새는 워낙 하드웨어 비용이 저렴해서 메모리 비용에 대한 부담이 적기 때문이다. 그래서 현업에서 알고리즘을 구상할 때 메모리를 적게 소모하는 방향보다 전체 프로그램 수행 시간을 줄이는 방향으로 개발하는 것이 더 타당하다.

시간복잡도에서는 실행시간이 중요하다. 컴파일 시간은 우리가 제어할 수 없는 경우가 많기 때문에 크게 중요하지는 않다.  즉, 우리가 알고리즘을 구상할 때 반복문의 실행빈도에 따른 명령문의 실행횟수가 중요하다고 할 수 있다. 따라서 좋은 알고리즘인가를 생각할 때는 아주 간단하게 반복문이 몇 번 실행되는가라는 물음으로도 판단 할 수 있다.

빅오 표기법

시간 복잡도 함수에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게 할 목적으로 시간 복잡도를 표시하는 방법

많이 쓰이는 빅오 표기법 (실행시간이 빠른 순)

표기법	설명
O(1)	입력 자료의 수에 관계없이 일정한 실행 시간을 갖는 알고리즘 (상수형)
O(log N)	입력 자료의 크기가 N일경우 log2N 번만큼의 수행시간을 가진다. (로그형)
O(N)	입력 자료의 크기가 N일경우 N 번만큼의 수행시간을 가진다. (선형)
O(N log N)	입력 자료의 크기가 N일경우 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(N2)	입력 자료의 크기가 N일경우 N2 번만큼의 수행시간을 가진다. (2차형)
O(N3)	입력 자료의 크기가 N일경우 N3 번만큼의 수행시간을 가진다. (3차형)
O(2n)	입력 자료의 크기가 N일경우 2N 번만큼의 수행시간을 가진다. (지수형)
O(n!)	입력 자료의 크기가 N일경우 n*(n-1)*(n-2)... * 1(n!) 번만큼의 수행시간을 가진다.