윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

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

자료구조란 무엇인가?

자료구조는 데이터를 표현하고 저장하는 방법에 대해서 설명한다. 넓은 의미에서 int형 변수, 구조체, 배열도 료구조의 일종이라고 할 수 있다. 하지만 보통의 자료구조는 이러한 것들처럼 단순하지 않다.

자료구조는 기본적으로 다음과 같이 분류할 수 있다.

자료구조와 알고리즘

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

예를 들어보자.

const arr = [1,2,3,4,5]; // 자료구조적 측면의 코드
let sum = 0; // 자료구조적 측면의 코드
for(let i=0; i<arr.length; i++) sum += arr[i]; // 알고리즘적 측면의 코드

위의 반복문은 '배열에 저장된 모든 값의 합을 구하는 알고리즘'이라고 할 수 있다. 이와 같이 자료구조와 알고리즘은 밀접한 관계를 갖는다. 자료구조가 결정되어야 그에 따른 효율적인 알고리즘을 결정할 수 있다. 알고리즘은 자료구조에 의존적이기 때문에 자료구조에 따라서 알고리즘은 달라진다.

알고리즘의 성능분석 방법

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

우리는 잘 동작하는 것 뿐만 아니라, 좋은 성능까지 보장받기를 원한다. 때문에 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. 모든 경우에 있어서 항상 우월한 성능을 보이는, 만능 키와 같은 자료구조와 알고리즘은 존재하지 않는다(이하 '자료구조와 알고리즘'을 '알고리즘'으로 총칭한다). 알고리즘을 평가하는 두 가지 요소는 다음과 같이 정리할 수 있다.

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

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

일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행속도에 초점을 둔다. 대게는 속도에 관심이 더 많고, 또 중요한 요소로 판단되기 때문이다.

알고리즘의 수행속도를 평가할 때는 다음과 같은 방식을 취한다.

연산의 횟수를 센다.
그리고 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.

연산의 횟수를 통해서 알고리즘의 빠르기를 판단한다. 그리고 데이터의 수를 함수에 입력하면 연산의 횟수가 바로 계산이 되는 식을 구성한다. 식을 구성하면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 판단할 수 있기 때문이다. 알고리즘 별 연산횟수를 함수 T(n)의 형태로 구성하면, 다음 그림에서 보이는 바와같이 그래프를 통해서 데이터 수의 변화에 따른 연산횟수의 변화 정도를 한눈에 파악할 수 있고, 이로 인해서 둘 이상의 알고리즘을 비교하기가 용이해진다.

위 그림의 두 알고리즘에 대한 비교결과를 얘기해보자.
데이터의 수가 적은 경우, 속도 차가 별로 나지 않는다. 중요한 것은 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도에 있다. 알고리즘 A가 훨씬 좋은 알고리즘이다. 하지만 대게 A와 같이 안정적인 성능을 보장하는 알고리즘은 알고리즘 B와 같은 성격의 알고리즘에 비해서 구현 난이도가 높은 편이다. 따라서 데이터의 수가 많지 않고 성능에 덜 민감한 경우라면 구현의 편의를 이유로 B와 같은 알고리즘을 선택하기도 한다.

상황에 맞게 알고리즘을 사용해야 하는 것이다. 알고리즘의 구현능력에만 관심을 두지 말고, 종합적으로 사고하고 판단하는 능력이 더 중요하다.