[알고리즘 #1] 알고리즘의 정의와 기본개념

이번 포스팅 시리즈를 통해서 알고리즘에 대해서 정리하고자 합니다.

** 반응형 광고 **

1. 알고리즘의 정의

프로그래밍을 통해서 어떤 문제를 해결하려면 기본적으로 다음과 같은 순서로 작업을 합니다.

문제의 이해/분석 -> 해결방안 구상 (알고리즘 구상) -> 프로그래밍 (코딩) -> 실행 및 검증 (디버깅)

실제 현업에서 일을 하다보면 해결방안 구상, 코딩, 디버깅이 뒤섞여서 진행되거나 아예 알고리즘 정리 없이 즉흥적으로 코딩을 하는 경우도 더러 있습니다. 당연히 올바른 프로그래밍 습관은 아닙니다. 바쁘다고 제대로 된 설계 없이 코딩부터 들어갔다가 오히려 시간을 버리는 경우를 많이 봤습니다.

알고리즘이란 문제를 이해하고 해결방안을 구상하는 것이라고 할 수 있습니다. 그리고 이 해결방안 구상이라는 것은 단순히 머리로만 생각하는 것이 아니라 논리적으로 명세화 시켜놓는 것을 말합니다. 즉, 알고리즘은 논리적이어야 하고 반드시 명세화하여야 합니다. 명세화 하는 방법은 여러가지가 있습니다. 순서도를 이용할 수도 있고, pseudo code를 짜거나 아니면 그냥 글로 기술할 수 도 있습니다. 중요한 것은 명세화, 즉 적어놔야 한다는 겁니다.

2. 좋은 알고리즘이란?

알고리즘을 짤 때는 항상 성능을 고려하여야 합니다. 성능을 분석할 때는 공간복잡도와 시간복잡도 이 두 가지를 고려합니다. 

공간복잡도 (space complexity) : 총 저장공간의 양

시간복잡도 (time complexity) : 총 소요시간

공간복잡도는 프로그램 실행 시 필요한 고정 또는 가변 메모리의 양을 의미하고 시간복잡도는 프로그램의 컴파일 시간과 실행시간의 합을 의미합니다. 

좋은 알고리즘은 공간복잡도와 시간복잡도가 작은 알고리즘을 의미합니다. 즉, 저장공간을 적게 사용하고 프로그램 수행시간이 적어야 한다는 것이죠. 하지만 최근에는 공간복잡도보다 시간복잡도를 더 중요하게 생각하고 있습니다. 요새는 워낙 하드웨어 비용이 저렴해서 메모리 비용에 대한 부담이 적기 때문입니다. 그래서 현업에서 알고리즘을 구상할 때 메모리를 적게 소모하는 방향보다 전체 프로그램 수행 시간을 줄이는 방향으로 개발하는 것이 더 타당하다고 보고 있습니다.

시간복잡도에서는 실행시간이 중요합니다. 컴파일 시간은 우리가 제어할 수 없는 경우가 많기 때문에 크게 중요하지는 않습니다.  즉, 우리가 알고리즘을 구상할 때 반복문의 실행빈도에 따른 명령문의 실행횟수가 중요하다고 할 수 있습니다. 따라서 좋은 알고리즘인가를 생각할 때는 아주 간단하게 반복문이 몇 번 실행되는가라는 물음으로도 판단 할 수 있습니다.

** 큰사각형 광고 **