알고리즘이란 무엇인가?

2022-12-22 01:22:30 | 조회수 187



알고리즘(영어algorithm), 셈법은 수학과 컴퓨터과학언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 
(출처 : 위키백과)


우리는 알고리즘의 정의대로, 컴퓨터 프로그램을 통해 어떠한 문제를 해결하기 위한 일련의 절차를 마련할 필요가 있습니다. 그런 절차를 마련하기 위해 명령어를 입력하는데, 이러한 명령어의 집합체를 우리는 알고리즘이라고 부를 수 있을 것입니다.


어떠한 방법으로든 문제를 해결할 수 있는 절차를 제시한다면 그것을 알고리즘이라고 부를 수 있지만, 같은 결과를 도출하더라도 시간이 더 적게 소요되는 알고리즘이 있다면 우리는 그 알고리즘을 이용할 것입니다. 이처럼 알고리즘은 절차가 어떻게 구성되어 있냐에 따라 수행되는데 필요한 시간이 다르게 되는데, 우리는 이를 알고리즘의 복잡도로 표현할 수 있습니다.


컴퓨터 프로그램에서 알고리즘은 일반적으로 주어진 입력에 대한 출력값을 얻을 수 있는데, 이 때 $N$개의 입력값에 대해 가장 빠른 복잡도로 표현될 수 있는 것은 $O(1)$ 입니다. 이는 $N$ 의 크기에 관계 없이 상수 시간, 즉 일정한 시간 이내에 알고리즘 동작이 완료될 수 있음을 의미합니다. 예를 들어, $N$개의 인덱스를 가진 배열에서, 특정 $i$번째 인덱스의 값이 null인지 아닌지 체크할 때의 시간복잡도는 $O(1)$ 에 해당됩니다.


입력의 크기에 따라 연산 시간이 비례하여 증가하는 경우 $O(N)$, 제곱으로 증가하는 경우 $O(N^2)$ 등으로 입력할 수 있습니다. 시간복잡도에 따라 우리는 주어진 문제를 해결할 때 어느 정도의 시간이 걸리는지 짐작할 수 있게 됩니다. 이를 통해 어떤 문제를 해결할 때 이 알고리즘을 쓸 수 있는지 없는지 결정할 수 있게 됩니다. 예를 들어, 입력의 값이 최대 100개라고 한다면, $O(N^2)$ 의 시간 복잡도가 소요되는 알고리즘을 이용하더라도 문제 해결에는 전혀 문제가 없지만, 입력 값의 크기가 100만 개라고 한다면 매우 긴 시간이 소요되므로 사용할 수 없게 됩니다.


주어진 문제를 해결하는 알고리즘에 필요한 공간은 공간 복잡도를 이용해 표현할 수 있습니다. 표기법 자체는 Big-O 표기법으로 동일하게 표현합니다. 이후에 나올 동적 프로그래밍 등, 공간 복잡도가 매우 중요한 알고리즘에서는 이를 중요하게 다룹니다.


알고리즘이란 무엇인가? - 알고리즘닷컴