[자료구조] 자료구조와 알고리즘의 이해

본 포스팅은 윤성우의 열혈 자료구조를 학습하며 개인 정리를 위한 포스팅입니다

---

1) 자료구조(Data Structure)에 대한 기본적인 이해

 

* 자료구조란 무엇인가?

 

자료구조는 데이터를 표현하고 저장하는 방법을 설명한 것이다. 책에서 프로그램의 정의는 "데이터를 표현하고, 표현된 데이터를 처리하는 것"이라고 정의한다. 여기서 '데이터의 표현'은 '데이터의 저장'을 포함하는 개념이며 '데이터의 저장'을 담당하는 것이 바로 자료구조이다.

 

* 자료구조의 분류

자료구조의 분류(도서 발췌)

여러가지 자료구조의 분류가 있지만 중점적으로 학습하게 될 대상은 '선형 자료구조'와 '비선형 자료구조' 이다. 선형 자료구조는 자료를 표현 및 저장하는 방식이 선형(linear)으로 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이며, 비선형 자료구조는 데이터를 나란히 저장하지 않는 구조로 선형에 비해 복잡성을 띈다.

 

* 자료구조와 알고리즘

 

자료구조가 '데이터의 표현 및 저장방법'을 뜻한다면, 알고리즘은 표현 및 저장된 데이터를 대상으로 하는 '문제의 해결 방법'을 뜻한다. 배열 선언을 예로 들어보자.

 

int arr[10] = {1,2,3,4,5,6,7,8,9,10};

배열의 선언은 자료구조적 측면인 코드이다

 

for(idx=0; idx<10; idx++)        sum += arr[idx]++;

배열에 저장된 모든 값의 합을 더하는 반복문의 구성은 알고리즘적 측면의 코드이다.

 

2) 알고리즘의 성능분석 방법

 

* 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

 

우리는 잘 동작하는 것은 물론이고 좋은 성능까지를 보장받기를 원한다. 때문에 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. 알고리즘을 평가하는 요소는 다음과 같이 두 가지로 정리할 수 있다.

 

"어떤 알고리즘이 어떠한 상황에서 더 빠르고 또 느린가?"   "어떤 알고리즘이 어떠한 상황에서 메모리를 적게 쓰고 또 많이 쓰는가?"

 

이렇듯 하나는 '속도'에 관한 것이고 다른 하나는 '메모리의 사용량'에 관한 것인데 속도에 해당하는 알고리즘의 수행시간 분석결과를 가리켜 '시간 복잡도(time complexity)'라 하고 메모리의 사용량(공간)에 대한 분석결과를 가리켜 '공간 복잡도(space complexity)'라 한다.

 

메모리를 적게 쓰고 속도도 빨라야 최적의 알고리즘이라고 할 수 있지만 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 두게 된다. 그렇다면 다음과 같은 의문이 드는것이 합리적이다.

 

"어떻게 속도를 평가할 수 있는가?"

 

이를 위해서는 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다. 말 그대로 연산의 횟수를 통해서 알고리즘의 빠르기를 판단한다. 물론 연산의 횟수가 적어야 빠른 알고리즘이다. 그리고 '데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다'는 것은 데이터의 수에 대해 연산의 횟수가 계산되는 식을 구성한다는 뜻이다. 식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있다.

 

* 빅-오 표기법(Big-Oh Notation)

 

빅-오란 O가 매우 크다는 뜻이다. 장난같은 말이지만 함수 T(n)에서 가장 영향력이 큰 부분이 어디인가를 따지는 것인데, 이때 사용되는 표기법에 대문자 O를 붙여 사용하기 때문에 빅-오라고 말한다. 예를들어 다음과 같은 시간 복잡도를 같는 함수를 보자.

 

T(n) = n^2+2n+1

 

다음과 같은 시간 복잡도 함수에서 데이터(n)의 변화에 따라 가장 큰 영향을 받는 부분은 n^2이 절대적이다. 즉 이 함수에서 빅-오를 구하면 다음과 같다.

 

T(n) = n^2+2n+1 -> O(n^2)

 

* 대표적인 빅-오

 

대표적인 빅-오 표기에 대해 알아보자.

 

• O(1) : 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘이다
• O(log n) : 로그형 빅-오, '데이터 수의 증가율'에 비해서 '연산횟수의 증가율'이 훨씬 낮은 알고리즘이다
• O(n) : 선형 빅-오, 데이터의 수와 연산횟수가 비례하는 알고리즘이다
• O(n*log n) : 데이터의 수가 두 배로 늘 때, 연산횟수는 두 배를 조금 넘게 증가하는 알고리즘이다
• O(n^2) : 데이터 수의 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다
• O(n^3) : 데이터 수의 세 제곱에 해당하는 연산횟수를 요구하는 알고리즘을 의미한다
• O(2^n) : 지수형 빅-오, 사용하기에 매우 무리가 있으며 데이터 증가에 따라 연산횟수가 기하급수로 늘어난다

지금까지 설명한 빅-오 표기들의 성능(수행시간, 연산횟수)의 대소를 정리하면 다음과 같다

 

O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) < O(2^n)