자료구조 - 3 | 알고리즘

알고리즘의 이해

알고리즘
문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

알고리즘이란 컴퓨터가 특정 문제를 해결하기 위한 절차나 방법을 논리적으로 설명하는 과정 또는 명세서를 말한다. 컴퓨터 프로그램은 굉장히 많은 종류가 있는데, 각각은 모두 만들어진 목적이 다르다. 즉, 해당 프로그램을 이용해서 실현할 수 있는 결과가 다 다르다는 것인데, 이를 위해 각 프로그램에는 각자에 맞는 알고리즘이 사용된다.

 

일상생활에서 간단한 예시를 들어보자면, 요리 레시피가 알고리즘의 한 예라고 볼 수 있다.

요리 레시피에는 요리 재료와, 해당 재료를 이용해 어떠한 순서로 요리를 진행하는지 알려주는 부분이 있다. 여기서 재료에 해당하는 부분이 데이터(자료)에 해당할 것이고, 해당 자료를 어떠한 순서와 방식으로 가공하는지에 대한 부분이 알고리즘에 해당하는 부분이라고 볼 수 있다.

 

실제 어떤 요리를 만들 것인지에 따라서, 서로 다른 레시피가 존재한다. 또 설령 같은 음식이더라도 사용되는 재료나 그 방법이 서로 다른 레시피가 다수 존재할 수도 있다. 이렇듯 알고리즘은 만들어내려는 결과물에 따라 그에 맞게 제작되어야 하며, 같은 결과를 만들어 내는 데에도 여러 방법이 존재할 수 있으므로, 그중 가장 합리적인 방식을 따르는 것이 좋다고 볼 수 있다.

알고리즘의 조건

그렇다면 이러한 알고리즘이라고 하는 것들은 어떠한 조건을 가지고 있어야 할까?

아래는 알고리즘의 조건 5가지이다.

• 입력: 알고리즘은 수행에 필요한 자료를 외부에서 제공받을 수 있어야 한다.
• 출력: 알고리즘은 수행 후 하나 이상의 결과를 출력해야 한다.
• 명확성: 수행할 작업의 내용과 순서는 명확하게 명세되어야 한다.
• 유한성: 알고리즘은 수행 뒤에 반드시 종료되어야 한다. (프로그램과의 차이점)
• 효과성: 알고리즘의 모든 명령어는 명백하게 실행(검증)이 가능해야 한다.

---

알고리즘의 표현

알고리즘을 표현하기 위한 방법으로는 크게 아래의 4가지의 방법이 있다.

• 자연어를 이용한 서술적 표현
• 순서도(Flow chart)를 이용한 도식화
• 가상 코드(Pseudo-code)를 이용한 추상화
• 프로그래밍 언어를 이용한 구체화 (실제 프로그램 작성)

자연어를 이용한 서술적 표현

자연어를 이용하여 알고리즘을 표현하는 것은 위에서 예시로 설명한 음식 레시피의 작성법과 굉장히 유사한 방법이라고 할 수 있다. 가장 인간이 이해하기 쉽고 작성하기도 편한 방식이지만, 이는 컴퓨터가 이해할 수 있는 논리적 표현으로 변환하는 과정이 추가로 필요하다. 또한 서술적으로 장황하게 글을 쓰다 보면, 논리적으로 맞지 않는 부분이나 기타 오류가 확연히 드러나지 않기 때문에, 이를 확인하는 것 역시 문제점이 될 수 있다.

순서도를 이용한 도식화

여러 도형과 흐름을 표현한 선을 이용해, 알고리즘이 작동하는 동작 원리를 논리적이고 동시에 한눈에 파악하기 좋게 도식화하는 방법이다. 이러한 방법은 전체 알고리즘의 과정을 한눈에 이해하기 편할 뿐 아니라, 논리적으로 맞지 않는 부분을 쉽게 확인하기도 좋다. 하지만 굉장히 복잡한 형태의 알고리즘의 경우에는 이러한 순서도를 이용하여 표현하기에는 어려움이 있을 수 있다.

순서도의 예시

가상 코드를 이용한 추상화

가상 코드란, 실제로 프로그래밍을 위해 사용하는 프로그래밍 언어가 아닌 알고리즘 기술 언어(ADL; Algorithm Description Language)를 이용하여 알고리즘을 표현하는 방식이다. 해당 방식은 특정 프로그래밍 언어가 아니므로 당연히 직접 실행은 불가능하다. 하지만 이러한 가상 코드는 프로그래밍 언어의 형태이므로, 실제 알고리즘을 적용할 프로그램이 사용하는 특정 프로그래밍 언어로 변환하기가 훨씬 용이하다는 장점이 있다.

 

가상 코드에 대한 자세한 작성방법은 아래에서 추가로 설명한다.

---

가상 코드(Pseduo-code)

가상 코드는 일반적인 프로그래밍 언어와 굉장히 유사한 형태로 작성할 수 있다. 따라서 어떤 언어라도 하나를 제대로 공부한 사람의 경우 누구나 쉽게 이해하고 사용할 수 있다.

 

또한 아무리 규칙이 정해져 있다고는 하지만, 이는 실제 프로그램을 작동시키기 위한 코드가 아니다. 따라서 이를 확인하는 사람끼리 서로 이해할 수 있을 정도로만 표현하면 사실상 큰 문제가 없다. (정해진 규칙에 너무 얽매일 필요는 없다.)

대입문

변수 등에 값을 대입하기 위해서는 아래와 같이 화살표를 이용해 표현한다.

var <- 5
name <- cookie
sum <- 3 + 2

조건문

조건에 따라 실행할 명령문이 결정되는 선택적 제어구조를 만들기 위해서는 if문의 형식을 사용한다.

if (조건식1) then 명령문1;
else if (조건식2) then 명령문2;
else 명령문3

Case문

여러 조건 중에서 특정 조건을 찾아 그에 대한 명령문을 수행하도록 하기 위해 case문을 사용한다.

case {
  조건식1: 명령문1;
  조건식2: 명령문2;
  조건식3: 명령문3;
  else: 명령문4;
}

반복문

일정한 명령을 반복 수행하기 위한 루프(loop) 형태의 제어구조이다. 이러한 제어구조를 사용하기 위해 for문, while문, do-while문 등을 사용할 수 있다.

// for문
for (초기값; 조건식; 증감식) do 명령문;

// while문
while (조건식) do 명령문;

// do-while문
do 명령문;
while (조건식);

함수문

처리 작업을 개별적으로 모듈화 하여 만든 함수는 아래와 같이 표현한다.

함수이름 (매개변수)
  명령문;
  return 결과;
end

---

알고리즘의 성능 분석

처음에 알고리즘을 음식 레시피를 예시로 들어 설명할 때, 같은 요리라도 여러 개의 서로 다른 조리방법이 있을 수 있다고 말했었다. 즉, 알고리즘도 같은 결과를 만들어내기 위해 여러 서로 다른 방법들을 시도해볼 수 있는데, 그중 가장 결과물이 좋고, 또한 동작함에 있어 효율이 좋은 방식을 잘 골라서 사용하는 것이 중요할 것이다.

 

따라서 만들어진 알고리즘의 성능을 분석하는 일은 굉장히 중요한 부분이라고 할 수 있다.

성능 분석의 기준

• 정확성: 올바른 자료 입력 시, 유한한 시간 내에 올바른 결과를 출력하는지 여부
• 명확성: 알고리즘이 얼마나 이해하기 쉽고 명확하게 작성되었는지 여부
• 수행량: 알고리즘의 특성이 나타나는 주요 연산을 수행하는 정도 (시간 복잡도)
• 메모리 사용량: 알고리즘을 동작시키기 위해 사용하는 메모리의 정도 (공간 복잡도)
• 최적성: 가장 중요한 분석 기준

공간 복잡도

공간 복잡도란, 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총메모리의 양을 의미한다. 알고리즘이 동작하면서 필요한 메모리의 경우, 고정적으로 할당되어야 하는 공간과, 가변적으로 할당되는 공간이 있는데, 이를 모두 합하여 필요한 총메모리를 계산해야 한다.

 

이전에 컴퓨터의 하드웨어 성능이 지금처럼 좋지 못했을 때는, 적은 양의 메모리를 최대한 효율적으로 관리하는 것이 필수적이었다. 하지만 지금에 와서는 가정용 컴퓨터임에도 메모리가 굉장히 넉넉한 경우가 많기 때문에, 이전에 비해 중요성이 많이 떨어졌다고 할 수 있다.

 

하지만 그럼에도 사물 인터넷을 구현하기 위해, 최신 전자제품에 함께 장착되어 나오는 임베디드 컴퓨터와 같은 경우에는 메모리 용량이 한정적인 경우가 많다. 이러한 특수한 경우에서는 공간 복잡도를 충분히 고려하여야 할 필요가 있다.

시간 복잡도

시간 복잡도란, 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요시간을 의미한다. 이때 실행 시간은 컴퓨터의 성능에 따라 달라질 수 있으므로, 실제 실행 시간을 측정한다기보다는 명령문의 실행 빈도수를 따로 계산하여 결과를 얻어낸다.

 

이때 보통 대입문, 조건문, 제어문, 반환문 등에서는 실행시간의 차이가 거의 없으므로, 이를 하나의 단위 시간을 갖는 기본 명령문으로 취급하여 계산을 진행한다. 보통 이러한 시간 복잡도를 결정짓는 요인은 반복문 또는 재귀 함수와 같은 여러 번 반복하여 명령문을 실행하는 부분이다.

시간 복잡도 예시

다음은 위의 내용을 기본으로 하여 간단한 알고리즘의 실행 빈도수를 계산하는 예시이다. 이때 사용할 알고리즘은 피보나치수열을 생성하는 알고리즘을 가상 코드로 나타낸 것이다.

피보나치 수열을 가상코드로 추상화

해당 알고리즘의 실행 빈도수를 표로 나타내면 다음과 같다.

행	n < 0	n = 0 or n = 1	n > 1
01	0	0	0
02	1	1	1
03	1	0	0
04	0	1	1
05	0	1	0
06	0	0	1
07	0	0	1
08	0	0	n
09	0	0	n-1
10	0	0	n-1
11	0	0	n-1
12	0	0	0
13	0	0	1
14	0	0	0

이를 식으로 나타내면 (n > 1) f(n) = 4n + 2으로 나타낼 수 있다.

---

알고리즘의 성능 분석 표기법

알고리즘의 효율을 표현하기 위한 점근 표기법으로는 빅오, 빅오메가, 빅세타 표기법이 있다.

 

그런데 방금전에 f(n) = 4n + 2와 같은 식으로 시간 복잡도를 표기할 수 있었는데, 이러한 추가적인 표기법은 왜 필요한 것일까? 그 이유는 첫 문장에서 말한 점근 표기법이라는 단어에 있다. 이러한 복잡도를 계산함에 있어서 각 코드를 한 줄 한 줄씩 분석하는 것은 규모가 굉장히 큰 알고리즘에서 사용하기가 힘들다.

 

따라서 이를 간소화해서 표현하는 것이 좋은데, 이를 점근 표기법이라 한다. 그리고 알고리즘의 성능 분석을 위한 점근 표기법에 빅오, 빅오메가, 빅세타 방식이 있는 것이다. 보통 빅-오 방식을 가장 많이 사용한다.

빅-오 표기법

먼저 빅오 표기법의 수학적 정의는 다음과 같다.

n ≥ n0 > 0 에 대해 0 ≤ f(n) ≤ k·g(n)인 상수 k와 n0가 존재하면 f(n) = O(g(n))이다.

이를 이해하기 쉽게 설명하면 상한선을 잡는 개념이라고 생각하면 된다.

예를 들어 특정 알고리즘의 시간 복잡도가 f(n) = 3n² + 5n -12로 표현된다고 하자. 이때 g(n) = n²이라고 가정하면, k가 4 이상부터는 f(n) < g(n)이라고 할 수 있다.

 

따라서 f(n) = O(n²)으로 간단하게 표현할 수 있다.

충분히 큰 n에서는 n²항을 제외하고는 큰 의미를 가지지 못한다. 따라서 O(n²)으로만 간단히 표기하는 것이다.

n값의 변화에 따른 시간 복잡도 비교

n값의 변화에 따른 시간 복잡도 그래프

시간 복잡도에 따른 알고리즘 수행 시간 비교 예시

빅-오메가 표기법

빅-세타 표기법