[Algorithm] 1) 알고리즘의 필요성, 시간복잡도(Time Complexity)

알고리즘

(Algorithm)

" 어떠한 문제를 해결하기 위한 여러 동작들의 모임 "

 

컴퓨터 공학에서 뿐만이 아닌, 수학이나 해석학 등 여러 학문에서도 자주 등장하는 단어이다.

어떠한 문제를 해결하기 위해, 하나 하나의 동작들을 어떻게 구성할지 계획하고, 그 동작들이 특정 기준(정확성, 작업량, 복잡도 등)을 어느정도 만족해 나가면서 이전보다 나은 해결방법을 찾기 위해 고안된 이론이라고 볼 수 있다. 

 

 

그래서 개발을 할 때는 이러한 알고리즘의 좋은 기준들을 통과하며 코드를 작성하게 되면, 그 코드로 이루어져 있는 프로그램들은 최적의 퍼포먼스를 내면서, 좀 더 사용자에게 좋은 서비스를 제공할 수 있게 된다.

 

 

특히나 웹(Web) 개발 같은 경우 브라우저 단에서 주로 개발이 이루어지는데, 이런 브라우저를 포함하고 있는 OS보다 초기에 상대적으로 더 적은 메모리를 할당 받기 때문에, 좋은 알고리즘으로 메모리 관리에 신경을 써야 한다.

 

물론 C언어, 어셈블리어 같은 저수준 언어가 아닌. Javascript 같이 고수준 언어로 개발을 할때는 가비지 컬렉터(Garbage Collector)가 지원되므로, 할당 시점과 해제 시점을 자동으로 관리해주지만, 완벽하게 메모리가 관리되는 것은 아니다.

 

[참고] https://itstory.tk/entry/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EC%97%90%EC%84%9C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EB%88%84%EC%88%98%EC%9D%98-4%EA%B0%80%EC%A7%80-%ED%98%95%ED%83%9C

자바스크립트에서 메모리 누수의 4가지 형태

 

 

결국엔, 한정된 자원 안에서 주어진 문제에 대해서 효율적으로 풀어내기 위해, 그리고 그 안에서 최대한의퍼포먼스를 뽑아내기 위해서 알고리즘 이라는 것이 필요하다는 것이다.

 

여기서 좋은 알고리즘의 기준일 될 수 있는 '시간복잡도(Time Complexity)' 에 대해서 알아보겠다.

 

 

 

시간복잡도

" 문제를 해결하는데 걸리는 시간과 입력의 함수 관계 "

 

알고리즘의 성능을 나타내는 대표적인 기준으로, 알고리즘이 해당 문제를 해결하기 위해 필요한 시간 당 연산 횟수를 의미한다고 보면 된다.

 

그리고 이러한 시간복잡도를 측정할 때는 점근적 표기법(Asymptotic Notation) 을 기준으로 해서, 세가지 방식으로 표현해 낸다.

( * 점근적 표기법: 입력값의 크기를 계속적으로 늘려나가면서 알고리즘의 실행시간을 측정하는 방법. )

 

 

빅오 표기법(Big O Notation), 오메가 표기법(Ω Notation), 세타 표기법(Θ Notation)

 

 

그리고 여기서 빅오 표기법은 최악의 경우(Worst case) 즉, 특정 알고리즘이 문제를 해결할 때 '최대한 오래 걸리는 시간이 이정도 ~ ' 라는 점을 제시해주기 때문에, 수행시간을 측정하는 의미로 봤을 때는 가장 효과적인 기준이라고 볼 수 있다.  

( * 그리고 대부분의 코딩테스트 사이트에서 알고리즘의 성능 기준을 빅오 표기법에 의거해서 표시하고 있다. )

 

 

[참고] https://www.bigocheatsheet.com/

 

 

 

 이 글을 쓰기 전에 웹팩(Webpack)의 주요한 개념(Module, Bnudling 등)에 대해서 쓴 글이 있는데, 웹팩의 주요 기능 중 하나가 '최적화(Three Shaking)' 라는 것이 있다. 사실 웹개발을 하면서 가비지 컬렉터가 대부분 지원되는 고수준 언어를 주로 다루다보니, 메모리라는 부분에 그렇게 신경을 써야하나 의문이었는데, 이미 수많은 개발자들이 지속적으로 이러한 메모리 관련 퍼포먼스에 신경을 쓰고 있는 것을 보니, 이전에 메모리 관리에 전혀 무지했던 내가 부끄러울 정도이다.

 

더군다나, 현재는 대부분의 웹 어플리케이션들이 SPA(Single Page Application) 방식으로 개발이 되다보니, 한 파일에 수십가지 혹은 수백가지의 모듈들이 들어간 상태에서 브라우저 상에 노출되다보니, 어떻게 보면 이러한 메모리 관리가 당연하게 필요하다고 지금은 생각된다.  

( * 자칫 잘못된 코드를 작성하다가 정작 백(Back) 단에서 불러와야 할 데이터는 못부르고, 레이아웃만 렌더링하다가 브라우저가 꺼지는 일도 발생할 수 있겠다는 생각이 든다.....)

 

 

아무튼 여기까지 알고리즘과 시간복잡도에 대한 대략적인 개념은 마무리하고,

실제 좋은 알고리즘을 측정하는 기준 중 하나인, 빅오 표기법에 대해서 다음 장에 자세하게 설명을 해보겠다.