알고리즘과 알고리즘의 성능평가

유튜브, SNS, 광고 등 인터넷 서비스 등에서 종종 접할 수 있는 알고리즘은 일반인들에게도 꽤 친숙한 개념이 됐다.

 

알고리즘이란 간단히 말해 어떠한 문제를 해결하기 위해 필요한 논리기반의 방식이라고 할 수 있는데,

 

실제로 우리는 일상생활 속에서도 우리도 모르게 많은 알고리즘을 만들고 수행하고 있다고 할 수 있다.

 

요리를 할 때, 여자친구와의 데이트 코스를 짤 때, 집안일을 할 때 우리가 정하는 나름대로의 순서와 행동의 이유가 모두 알고리즘에 기반되어 있다고 할 수 있다.

 

사실상 넓은 의미에서 우리가 하는 모든 행동은 우리만의 내제적인 알고리즘에 기반하여 이루어 지고 있다고 해도 과언이 아닐 것이다.

 

 

개발자에게 알고리즘이란?

 

개인의 행동을 결정하기 위한 알고리즘은 가끔 조금 효율적이지 못하더라도 잠시 후회하고 말 뿐 그 피해가 극심하진 않을 것이다.

 

하지만 개발자에게 비효율적인 알고리즘은 장, 단기적으로 큰 문제를 야기할 수 있다.

 

많은 사람들이 사용하는 인터넷 서비스의 알고리즘이 효율적이지 못하다면 서비스의 속도는 매우 느려질 것이고

 

데이터를 관리하는데 소요되는 비용도 천문학적으로 증가할 것이며, 이로 인해 발생하는 문제들은 고스란히 서비스 이용자들에게 돌아갈 것이다.

 

많은 양의 데이터를 관리하고 처리하는 큰 기업들의 경우 더욱 그러하다.

 

이러한 이유 때문에 많은 기업들이 사원을 모집하기 위해 알고리즘 능력 평가를 위한 코딩 테스트를 실행하고 있다.

 

 

알고리즘에 대한 평가

 

그렇다면 알고리즘의 좋고 나쁨을 어떻게 판단할 수 있을까?

 

알고리즘이 효율적이기 위해선 메모리에서 차지하는 공간이 최소화되어야 하고, 코드를 실행하는 시간 또한 짧아야한다.

 

다시 말해, 공간과 시간에서 효율적이어야 한다.

 

흔히 여기서 '복잡도'라는 말을 사용하여 공간복잡도, 시간복잡도라는 표현이 사용되는데, 당연히 각 복잡도가 낮을수록 효율적이라는 말이다.

 

공간복잡도의 경우, 개인의 노력보다는 컴퓨터의 성능, 사용하는 언어 등에 의해 더 큰 영향을 받는다.

 

따라서 개인에게 알고리즘을 효율적으로 짜라는 말은 일반적으로 시간복잡도를 최소화하라는 의미로 받아드릴 수 있다. 

 

이러한 이유로 시간복잡도를 평가하기 위한 빅오 표기법(Big-O Notation)이 알고리즘을 평가하기 위한 기준이 된다.

 

빅오 표기법은 데이터의 개수 N개에 대하여 코드의 연산횟수를 기반으로 수행시간을 구하는 방식이다.

 

list1 = [2, 3, 1, 4, 9, 10] # 1
list2 = [5, 22, 13, 9, 2] # 1
add = list1[0] + list2[0] # 2

print(add)

위 코드는 두 개의 리스트의 맨 앞의 값(2, 5)를 뽑아 더한 후 출력해주는 코드이다.

 

각 리스트에 데이터를 저장하는 것과, 리스트의 특정 값을 불러오는 것, 그 값을 더하는 것을 수행하는 시간이 모두 1이라고 할 때,

 

위 연산을 처리하기 위해선 총 4만 큼의 시간이 소요된다고 할 수 있다.

 

my_list = [12, 3, 9, 13, 22] # 1
sum = 0 # 1

for element in my_list: # 5 : 리스트의 원소의 수
	sum = sum + element # 2
    
print(sum)

다음엔 위의 코드를 살펴보자.

 

이 코드는 리스트의 모든 값들을 더하는 코드이다.

 

마찬가지로 특정 데이터를 저장하고 불러오고 더하는 시간은 1이 걸리므로, 해당 연산은 9만큼의 시간이 걸린다고 할 수 있다.

 

 

이제는 똑같은 두 코드의 리스트에 저장되는 원소가 커진다고 생각해보자.

 

첫 번째 add코드의 경우 항상 리스트의 맨 앞의 값을 불러와 더하기 때문에 리스트의 길이가 길어진다고 연산 횟수에 영향을 주진 않는다.

 

반면에, 두 번째 sum 코드의 경우 리스트의 길이가 길어질수록 for문에서 돌아가야 하는 원소의 개수들이 증가하게 된다.

 

다시 말해, 리스트의 개수가 N개일 때, for문에서 처리되어야하는 연산도 N번이 되는 것이다.

 

이렇듯, 데이터의 양에 따라 증가하게 되는 연산의 수를 N번이라고 가정하고 연산횟수를 구하게되면

 

첫 번째 코드 실행시간은 그대로 4이지만 두 번째 코드의 실행시간은 N+4가 된다.

 

이것을 빅오 표기법으로 표현하게 되면 각각 O(4) , O(n+4)이 되는 것이다.  

 

마지막으로, 빅오 표기법에선 최고차항만 남기고 나머지 값들은 버려주며, 상수항은 1로 취급해버린다.

 

이것은 극한의 개념을 차용한 것인데, 데이터가 무한히 증가한다고 가정할 때, 최고차항을 제외한 값들은 사실상 중요하지 않은 값들이 되어버린다.

 

y = 무한 + 100 에서 100이란 값이 중요하지 않은 것처럼 말이다.

 

결국, 두 코드의 최종적인 빅오 표기는 O(1), O(n)이 되는 것이다.