알고리즘 - 알고리즘의 정의

알고리즘의 정의

안녕하십니까. 알고리즘 카테고리를 만들어놓고 언젠가 정리해야지 하다가 이제야 건들게 되었습니다. 기초부터 차근차근 알고리즘에 대해서 정리할 예정입니다. 그럼 바로 시작하겠습니다.

 

컴퓨터 구조의 기초

알고리즘을 이야기 하기 전에 컴퓨터 구조에 대한 기초적인 내용부터 정리하고 가도록 하겠습니다. 결국 우리가 알고리즘을 짜고 사용하는 이유는 컴퓨터와 밀접한 연관이 있기 때문입니다.

 

컴퓨터의 정의는 전자회로를 이용한 고속 자동 계산기로 3가지 주요한 구성요소 하드웨어, 소프트웨어, 데이터로 구성되어 있습니다. 컴퓨터에는 다양한 부품이 있지만, 그 중 우리에게 중요한 것은 저장소입니다. 옜날에는 하드디스크를 사용했지만, 요즘은 SSD를 많이 사용합니다. 그런데 하드디스크는 우리가 알고있는 포인터와 비슷하다고 합니다. 하드는 포인터처럼 주소와 경로만 저장하도록 설계되어 있습니다. 이외에도 아날로그를 디지털로 바꾸는 것, 주사율, 헤르츠 등 많은 내용이 있지만, 더 중요한 것을 살펴보겠습니다.

 

컴퓨터가 데이터를 보낼 때 버스(bus)라는 통로를 통해 보냅니다. 이 때 한번에 버스에 실려보낼 수 있는 데이터의 양을 워드(Word)라고 하며, 이 내용은 추후 알고리즘을 작성할 때 오버플로우의 개념을 생각하기 위해 필요한 내용입니다. 이 워드는 컴퓨터가 하나의 명령어로 실행될 수 있는 데이터입니다.

 

마지막으로 왜 컴퓨터가 이진법을 쓰는가? 입니다. 그 이유는 이진법의 0과 1을 컴퓨터는 0v와 5v로 표현하기 때문입니다. 그렇다면 이제 진법과 보수에 대해서 가볍게 알아보고 넘어가도록 하겠습니다. 우리가 흔히 알고있는 1의보수와 2의보수가 있는데 이 보수를 쓰는 이유는 결국 동일한 저장공간으로 더 많은 수의 표현이 가능해지기 때문입니다. 특히 2의 보수가 그러한데 2의 보수는 1의 보수보다 수의 표현 범위가 넓고, 논리회로적인 측면에서 더 좋은 전기효율(전력)을 갖습니다.

그 이유는 0의 음수표현을 하지 않기 때문입니다.

 

알고리즘의 정의

알고리즘의 사전적 정의는 어떠한 문제를 해결하거나 특정 작업을 수행하기 위해 명확히 정의된 단계적인 절차나 규칙의 집합입니다. 저희는 알고리즘에 필요한 5가지 요소에 대해 알아보겠습니다. 바로 입력, 출력, 명확성, 유한성, 유효성 입니다.

 

- 입력(input) : 알고리즘 수행을 위해 필요한 자료가 외부에서 입력되어야 함

- 출력 (output) : 적어도 하나 이상의 결과를 출력해야 함

- 명확성(definiteness) : 각 명령은 애매모호하지 않고 명확해야 함

- 유한성 (finiteness) : 정해진 명령의 실행 단계 후에는 반드시 종료되어야 함

- 유효성 (effectiveness) :  모든 명령어는 기본적이며 실행 가능한 것이어야 함

 

그리고 우리가 함수나 실제 코드를 작성할 때 사용하는 5가지의 대표적인 실행 명령문도 있습니다. 대입문, 조건문, 반복문, 입출력문, 함수호출문 입니다. 이 부분은 바로 넘어가도록 하겠습니다.

 

알고리즘의 성능 분석

이제 저희는 앞으로 알아갈 알고리즘의 성능을 분석할 수 있는 지표가 필요합니다. 그 지표는 당연하게도 이미 만들어져 있습니다. 바로 실행시간을 측정하는 방법으로 시간복잡도와 공간복잡도가 있습니다.

 

-  시간복잡도 : 수행시간 분석

-  공간복잡도 분석 : 수행 시 필요로 하는 메모리 공간 분석

 

우리는 이 복잡도를 분석할 때 빅오표기법 이라는 단위를 사용하기로 정했습니다. 빅오표기법의 종류는 아래와 같습니다.

 

- O(1) : 상수형

- O(logn) : 로그형

- O(n) : 선형

- O(nlogn) : 로그선형

- O(n^2) : 2차형

- O(n^3) : 3차형

- O(n^k) : k차형

- O(2n) : 지수형

- O(n!) : 팩토리얼형

 

앞으로 우리는 모든 알고리즘이 등장할 때 마다 이 빅오표기법과 시간복잡도, 공간복잡도를 분석하게 될 것입니다.

 

NEXT

오늘은 알고리즘의 시작으로, 컴퓨터 구조의 기초와 함께 기본적인 알고리즘의 구성요소와 성능을 분석하는 방법에 대해 간단히 알아보았습니다. 다음에는 본격적으로 알고리즘에 대해서 공부하는 시간을 갖도록 하겠습니다. 알고리즘을 배울 때 거의 대부분 처음으로 배우는 정렬 알고리즘부터 차근차근 알아볼까 합니다. 감사합니다.