자료구조의 기초

본 포스트는 윤성우님의 열혈 자료구조를 출처로 작성된 글입니다.
필자의 복습이 주 목적이며, 오타나 잘못된 내용이 발견될 시 답글로 남겨주시면 감사하겠습니다.

자료구조란?

프로그램은 데이터를 표현(자료구조)하고, 표현된 데이터를 처리(알고리즘)하는 일련의 과정이다.

데이터를 표현한다는 것은 어떤 방식으로 데이터를 저장할지 선택하는 것과 같다.

또한 데이터가 어떻게 저장되어 있는지에 따라 알고리즘이 정해진다. 즉, 알고리즘은 자료구조에 의존적이다.

ADT와 자료구조의 관계

ADT란, Abstract Data Type의 약어이다.
ADT는 어떤 자료구조의 구체적인 기능의 구현방법을 언급하지 않고, 순수하게 해당 기능들이 어떤것들이 있는지 나열한 것이다.

예를들어.. Wallet이라는 자료구조가 있다면, ADT를 다음과 같이 정의할 수 있다.

int TakeOutMoney(Wallet* pw, int coinNum, int billNum)

• 첫 번째 인자로 전달된 주소의 지갑에서 돈을 꺼냄.
• 두 번째 인자로 꺼낼 동전의 수, 세 번째 인자로 꺼낼 지폐의 수 전달
• 꺼내고자 하는 돈의 총액 반환. 그만큼 돈 차감

void PutMoney(Wallet *pw, int coinNum, int billNum

• 첫 번째 인자로 전달된 주소의 지갑에 돈을 넣음
• 두 번째 인자로 넣을 동전의 수, 세 번째 인자로 넣을 지폐의 수 전달
• 넣은 만큼 동전과 지폐의 수가 증가한다.

출처 : 열혈 자료구조

자료구조는 항상 기능(ADT로 표현된)을 포함한다.

예를들어.. int라는 자료형을 생각하면 보통 데이터만을 생각한다. 하지만 int자료형은 대입연산=, 합연산+등의 기능을 갖고 있다.

앞으로는 특정 자료형과 함수(기능)을 따로따로 생각하는게 아니라, 같이 정의해 묶어 생각하는 관점을 가지도록 한다.

이 자료형들은 기능과 떼어 생각할 수 없으므로, 어떤 구조체를 통해 자료형을 정의했다면, 구조체가 수행할 연산(함수)들도 함께 정의해줘야 한다. 이것들이 어떤 자료구조의 헤더파일에 담긴 내용이다.

C와 OOP언어를 함께 공부했다면.. 이 자료구조가 OOP에서 말하는 클래스(Class)와 매우 유사한 개념임을 알 수 있을 듯 하다. 클래스 역시 데이터와 메서드의 결합구조이다!

빅오(Big-O)표기법

• 알고리즘을 평가의 두 기준

1. 시간복잡도(Time complexity)
   이는 해당 알고리즘이 얼마나 빠른지, 즉 cpu에 얼마나 부담을 주는지를 기준으로 평가한다.

2. 공간복잡도(Space complexity)
   이는 얼마나 메모리를 적게 사용하는지를 기준으로 평가한다.

오늘날엔 시간복잡도를 주된 알고리즘 평가기준으로 사용한다. 가상메모리등이 등장하며 메모리를 효율적으로 사용할 방법들이 생겨났고, 가상메모리등의 기법을 사용할때 스왑동안 메모리 액세스 시간이 추가된다. 이는 곧 공간복잡도를 고려할때 결국 시간복잡도의 평가가 추가된다는 것임.

• 시간복잡도의 평가 방법

1. 알고리즘의 핵심이 되는 특정 연산의 횟수를 센다.
2. 데이터의 수$(n)$에 대한, 수행속도(연산 횟수)의 함수 $T(n)$을 구한다.

알고리즘의 평가는 데이터의 수가 적은 경우 수행속도에 큰 의미를 두지 않는다.
알고리즘의 평가는 데이터가 충분히 많아질때, 해당 알고리즘의 수행속도(연산속도)의 변화 기준으로 한다.