알고리즘이란?
알고리즘이란 수학, 컴퓨터 과학 등의 분야에서 어떠한 문제를 해결하기 위한 일련의 절차 혹은 방법을 공식화한 형태로 표현한 것이라고 말하고 있습니다. 그러니까 어떠한 연산의 계산을 위한 단계적 절차라는 의미입니다. 뭐 예를 들면, 동전을 넣으면 뭔가가 나오는 기계가 있다고 생각해보겠습니다. 이 기계를 우리가 설계해서 판매를 해야 하는 입장이라면 일련의 절차를 마련해야 합니다. 쉽게 생각하면 동전이 들어오고, 기계의 물리적 장치를 이용해서 기계 내부의 물품이 빠져나가는 방식이겠죠? 세상이 이렇게 쉽게 돌아간다면 정말 좋으련만 그렇지 않습니다. 몇 가지 변수가 존재합니다.
-
동전이 들어옵니다. 하지만 들어온 쇳덩이가 동전인지 동전 같은 존재인지 판별해야 합니다.
-
동전이라는 것이 확인이 되었다면, 기계의 물리적 장치가 물품이 나오는 출구를 막고 있던 잠금장치를 해제합니다.
이런 유의 변수를 제어한 절차가 필요하겠죠? 이를 코드로 나타내 보겠습니다.
COIN := 500
LOCK := TRUE
IF COIN IS NOT A FAKE_COIN => LOCK := FALSE
ELSE => LOCK := TRUE
IF LOCK => RETURN NULL
ELSE => RETURN ITEM
대략적으로 위와 같은 코드로 작성할 수 있겠습니다. 그렇다면 우리는 뽑기 기계의 절차를 공식화한 형태의 알고리즘을 방금 완성한 것입니다!!
어떤 알고리즘이 좋은 알고리즘인가?
어떤 알고리즘이 좋은 알고리즘인지는 사실 측정할 수 있는 방법은 있습니다. 물론 최악의 방법을 사용해야만 해결되는 경우라면 어쩔 수 없겠지만 어느 정도의 공식은 존재한다는 겁니다!!
알고리즘에는 시간 복잡도와 공간 복잡도가 존재합니다. 시간 복잡도는 말 그대로 시간의 복잡성을 따지며, 공간 복잡도는 메모리의 복잡성을 따지는 단위입니다. 그렇다면 당연하게도 시간 복잡도가 비교적 낮으며, 공간 복잡도 또한 낮은 알고리즘이 효율적인 알고리즘이라고 볼 수 있습니다. 하지만 둘 다 잡을 수는 없습니다. 애석하게도 시간 복잡도가 높으면 공간 복잡도는 상대적으로 떨어지게 되는 반대되는 관계(?)라고 볼 수 있기 때문이죠. 그렇기 때문에 둘 중 하나만 낮추면 성공입니다만, 개발하는 프로그램에 따라 이 점은 달라집니다. 시간 복잡도는 높아도 되지만, 기계적 한계성 때문에 공간 복잡도를 낮추는 경우도 있으며, 시간이 부족해서 메모리를 얼마나 잡아먹을지 몰라도 연산을 빨리 수행해야 한다면, 공간 복잡도를 높이되, 시간 복잡도를 낮추는 경우도 생각해 볼 수 있다는 거죠.
점근적 표기법
보통 시간 복잡도를 논할 때 나오는 것이 바로 O입니다. Big-O-Notation이라고 하는 점근적 표기법이죠, 알고리즘의 복잡도를 단순화할 때 사용하는 표기법입니다. 그렇다면 왜 이와 같은 방법으로 표기를 할까요?
빅오 표기법을 사용하려 할 때는 아래와 같은 점이 매우 중요하게 작용됩니다.
-
입력된 데이터가 무엇인지, 또한 데이터가 나타내는 것을 분석합니다.
-
알고리즘의 점화식이 존재하고 그 점화식의 최대 수를 표현하면 그와 같은 연산 복잡성으로 알고리즘이 수행됨을 분석합니다
-
가장 높은 최대 수 외에 나머지 수를 제거합니다.
-
상수값들을 제거합니다.
| Time Complexity | 설명 | 예 |
| O(1) | 수행되는 알고리즘의 n에 관계 없이 일정 시간 이하에 수행되는 알고리즘으로 가장 빠름 | 입력된 데이터가 참인지 판별하는 것 |
| O(log n) | log_2 n에 비례하는 시간 이하에 수행되는 알고리즘 | Binary Search |
| O(n) | n에 비례하는 시간 이하에 수행되는 알고리즘 | 반복문 혹은 정렬 |
| O(n log n) | n에 대략 비례할 수 있는 시간 이하에 수행되는 알고리즘 | 정렬 알고리즘 |
| O(n^2) | n^2에 비례하는 시간 이하에 수행되는 알고리즘임 | 문자열 매칭 |
| O(n!) | n!(factorial)과 비슷한 수행 시간 이하로 수행되는 알고리즘 가장 느림, | 배열의 모든 열을 검사함 |
예제)
예제 알고리즘으로 준비해본 bubble sort입니다. 아래 코드를 보고 시간 복잡도가 얼마나 나올지 예상해보세요! 힌트를 드리자면 반복문을 잘 보면 알 수 있습니다.
#include <iostream>
using namespace std;
void swapArr(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}
void bubbleSort(int arr[], int n)
{
int i, j;
bool swap;
for (i = 0; i < n -1; ++i)
{
swap = false;
for (j = 0; j < n-i-1; ++j)
{
if (arr[j] > arr[j+1])
{
swapArr(&arr[j], &arr[j+1]);
swap = true;
}
}
if (swap) {}
else break;
}
}
void printArr(int arr[], int arrSize)
{
for (int i = 0; i < arrSize; ++i)
printf("%d\t", arr[i]);
puts("END");
}
int main()
{
int arr[] = {9,8,7,6,5,4,3,2,1};
int size = sizeof(arr)/sizeof(int);
bubbleSort(arr, size);
printArr(arr, size);
return 0;
}
다음 글에는 정렬에 관련한 글을 계속해서 올리도록 하겠습니다. 알고리즘 중에 가장 기본이 되는 알고리즘이기 때문에 보는 것이 가장 좋습니다!!
읽어주셔서 감사합니다!
댓글