[4기 강북 이동욱] 게임을 만들기 전에 #2 - 알고리즘 복잡도 분석

안녕하세요. 강북 멤버십 21기 이동욱 입니다.

  오늘은 지난 이야기에 이어 게임을 만들기 전에 알고 있으면 좋은 또 다른 부분에 대해서 이야기를 해보도록 하겠습니다.

  아무래도 게임을 개발할 때 기본적으로 가장 많이 신경 쓰게 되는 부분은, 메모리와 속도 입니다. 보통 메모리와 속도는 연관되어 있어서, 메모리를 아끼고 속도를 희생하거나, 속도는 약간 느리게 하더라도 메모리를 아끼는 등의 선택을 해야 하는 경우가 많이 있습니다.

  특히 게임의 경우 자료를 효율적으로 저장하면서 빠르게 작동해야 합니다. 그러기 위해서는 알고리즘과 자료구조에 대한 이해가 필수적 입니다. (다만, 요즘에는 워낙 컴퓨터의 성능이 좋아서 속도도 빠르고 메모리도 충분하기 때문에 개발하거나 하는 게임의 요구 사항에 맞춰서 적절하게 분배하는 것이 올바르다고 생각합니다.)

그래서 오늘은 알고리즘에 대하여 이야기 해보도록 하겠습니다.

  우선 알고리즘 복잡도를 알아보기 전에 알고리즘이 무엇인지 짚고 넘어가도록 하겠습니다. 예를 하나 들어 보도록 하겠습니다. 우리가 만들 어떤 게임에 가방이 있고 그 안에 여러가지 아이템들이 들어있습니다. 그런데 그 가방에는 '아이템 정렬' 기능이 있어서, 이 기능을 사용할 경우에 가방 속에 들어 있는 아이템들의 내용이 정렬이 된다고 가정하도록 하겠습니다. 

  그렇다면 사용자가 이 아이템 정렬 기능을 동작 시켰을 때 내부적으로 어떻게 동작 해야 할까요?

모두들 각자 자신만의 생각으로 가방을 '이렇게 혹은 저렇게 정리하면 되겠구나' 하고 생각 하셨을 겁니다. 가방 내부를 정렬 하는 방법은 여러가지가 있을 것입니다.

  알고리즘이란? 어떠한 문제를 해결하기 위한 일련의 절차를 뜻한다고 할 수 있습니다. (알고리즘 자체는 수학적 혹은 공학적으로 정의되어 있는 여러 의미가 있지만 지금은 이렇게만 알고 넘어가도록 하겠습니다.)

모두가 알고 계시겠지만, 어떠한 일을 처리하는 데에 똑같은 결과를 원하더라도 여러 방법으로 처리할 수가 있습니다.

  위의 그림에서 A 에서 G 로 가는 길은 여러 가지 방법이 나올 수 있습니다만, 가장 빠른 길은 누가 봐도 A에서 G로 직선으로 가는 방법입니다. 이처럼 누가봐도 한번에 가장 최고의 경우를 알 수 있다면, 좋겠지만, 실제로 우리가 게임을 개발 하거나 어떤 프로그램을 만들 때, 어떤 방법이 최고의 방법이라고 단언할 수는 없습니다. 

  그렇다면 가능한 여러가지 경우중 어떠한 방법이 가장 효율이 좋은 방법인지(혹은 여러 방법 중 어느 방법이 더 효율적인지) 판단할 수 있는 잣대가 필요하게 됩니다.

그래서 알고리즘 복잡도는?

  알고리즘 복잡도는 어떤 자료구조와 알고리즘이 다른 알고리즘 보다 자신이 원하는 환경에서 성능이 더 좋게 나오는지를 이해하는데 필요합니다. 따라서, 빠르게 많은 정보를 처리하는 게임을 개발하기 위해서는 알고리즘 복잡도에 대한 기본적인 지식을 갖출 필요가 있습니다.

 

알고리즘 복잡도에서 가장 중요한 것은 빅O 입니다. 

오늘은 간단하게 빅O 에 대해서 살펴보도록 하겠습니다.

빅O 표기법(big-O notation)은 어떤 함수의 복잡도를 추정하는 함수라고 할 수 있습니다.

O(함수)

위와 같이 표기합니다.

간단하게 빅O 에 대한 예를 들어 보겠습니다.

---

  민수는 100개의 게임CD를 가지고 있습니다. 그런데 이 게임들을 아무런 분류 없이 각각의 개별 상자에 넣어 두었습니다. 어느 날 민수의 친구 동욱이가 놀러와서 어떤 특정 게임CD를 빌려 달라고 하였습니다. 민수는 게임CD를 따로 분류해 놓지 않아서 상자를 하나씩 열어봐야 한는 상황 입니다. 즉, 최악의 경우는 100개의 상자를 열어야 친구가 원하는 게임 CD를 찾을 수 있습니다. 

---

  이러한 상황에서 검색의 빅O는 O(n) 입니다. 

  알고리즘 복잡도를 분석할 때 '최적의 경우' 와 '최악의 경우' 혹은 '평균적인 경우' 등을 분석하는 각기 다른 방법 들이 있지만, 가장 중요하고 가장 많이 사용하는 것이 빅O입니다. 이 빅O는 '최악의 경우'를 다루는 것으로 위의 경우 민수가 제일 처음 열어본 상자에 찾던 게임CD가 있을 경우는(최상의 경우) 는 무시합니다.

알고리즘 복잡도를 표현하는데 쓰이는 함수들을 복잡도가 낮은 것에서 높은 순으로 나열하면 

상수, log₂n , n , nlog₂n, n²  , n³ , 2ⁿ

입니다.

  사실 이렇게 말로만 적어 보면 무엇을 의미하는지 알아보기 힘들기 때문에, 

그래프를 보면서 이해해 보도록 하겠습니다.

O(c)

  빅O 표기에서 c는 상수를 뜻합니다. 상수의 그래프는 항상 수평인데, 이는 알고리즘 수행에 걸리는 시간이 항상 일정하기 때문입니다.

O(log₂n)

다음 그래프는 기수가 2인 로그 함수 입니다. 즉, 기수 2로그에서 수직 성분은 자료 집합의 크기가 두 배가 될 때마다 1증가합니다. 로그 기반 알고리즘은 자료의 크기에 의존적인 알고리즘들 중 에서는 가장 효율적인 것으로 간주되어 지고 있습니다. (O(c) 는 자료의 크기와 무관합니다)

O(n)

 은 선형(Linear) 함수라고 부릅니다. 자료 크기가 증가함에 따라 일정한 비율로 증가합니다. 앞에서 예를든 게임CD 찾기가 O(n)의 예시 입니다.

O(nlog₂n)

  일반적으로 정렬(sorting) 알고리즘이 가지는 최소한의 복잡도로 간주합니다. 이 정도면 비교적 효율적이라고 간주 합니다.

O(n²)

  이 함수 부터는 자료의 양에 따라 급격히 커지기 때문에 비효율적이라고 간주 합니다. 대표적인 예는 이중for문 을 들 수 있습니다. 

O(n³)

  매우 비효율적인 함수 입니다.

O(2ⁿ)

  자료수가 적은 경우에는 O(2ⁿ)알고리즘이 O(n²) 보다 빠르지만, 나중에는 훨씬 급격하게 증가 합니다.

지금 까지 살펴본 알고리즘의 수행 시간을 비교해 보도록 하겠습니다.

아래 표는 알고리즘이 항목 하나를 처리하는데 1초가 걸린다고 가정한 표 입니다.

 

  한 가지 추가적으로 이야기 하자면, 알고리즘의 복잡도를 측정할 때는 자료의 증가에 따라 수행 시간이 어떻게 증가하는 지만 생각 하시면 됩니다.

  예를 들어 위의 예제 에서 민수가 상자를 찾은 후 친구에게 게임CD를 빌려 주려고 포장을 한다고 하면 (포장하는 시간을 상수C 라고 하면) O(n+c) 가 되지는 않습니다. c의 경우는 무시하고 O(n) 이 됩니다.

  오늘은 알고리즘 복잡도에 대해서 알아 보았는데요. 어떤 알고리즘이 다른 알고리즘 보다 더 효율적이다 

상수> log₂n > n > nlog₂n > n²  > n³ > 2ⁿ

라는 것만 기억 하셔도 많은 도움이 되니 잊지 마시길 바랍니다.

 

---

References and Notes

1. Ron Penton “DATA STRUCTURES FOR GAME PROGRAMMERS” (2004)