[자료 구조] 자료 구조(data structure)란?

데이터의 순서나 위치 관계를 정한다.

컴퓨터 안에서 데이터는 메모리에 저장되고, 메모리는 아래 그림과 같이 상자가 일렬로 나열된 형태를 하고 있습니다. 그리고 하나의 상자 안에 하나의 데이터를 저장합니다.

 

 

이때, 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계 등을 정하는 것이 '자료 구조'입니다.

 

 

전화번호부의 자료 구조

이해하기 쉽게 전화번호부에 대해 생각해봅시다. 그리고 우리가 직접 종이에 적으면서 전화번호부를 관리한다고 해봅시다.

 

첫 번째 방법으로는 단순하게 아래에 이어서 추가하는 방법이 있을 것입니다.

하지만, 만약 '김짱구'라는 사람을 찾아 전화하고 싶을 때, 짱구를 찾으려면 시간이 오래 걸릴 것입니다.(전화번호부에 사람이 많이 있을수록 오래 걸리겠죠?)

 

 

 

두 번째 방법으로는 가나다순으로 관리하는 방법이 있습니다.

이 방법은 첫 번째 방법보다는 내가 원하는 사람을 찾기가 훨씬 빠를 것입니다. 하지만, 제가 만약 이진수를 넣고싶다면 이민수와 박세렌디 사이에 넣어야 하기 때문에, 박세렌디부터 밑에 있는 정보들을 하나씩 아래로 내려야 하는 단점이 있겠죠?

 

각각의 장단점을 정리해보면, 첫 번째 방법은 데이터 추가 시 가장 뒤에 붙여서 작성하면 되기에 간단하지만, 검색이 필요할 때 시간이 많이 걸립니다. 반대로, 두 번째 방법은 검색은 쉽지만 데이터를 추가할 때 시간이 많이 걸립니다.

 

양쪽 모두 장단점이 있기 때문에, 어느 방법을 선택할지는 사용자의 사용방식에 따라 달라질 것입니다. 만약에, 한 번 만든 후에 변경할 가능성이 없다면 두 번째 방법이 적합할 것이고, 데이터 추가는 자주 하지만 검색을 거의 하지 않는다면 첫 번째 방법이 적합할 것입니다.

 

물론, 두 가지 방법을 섞어서 새로운 방법을 만들 수도 있을 것입니다.

'가', '나', '다' ... 와 같이 자음별로 별도의 표를 만들어서 관리하는 방법처럼 말이죠. 이렇게 만든다면 새로운 데이터를 추가할 때 대응되는 표의 끝에 추가하면 되기 때문에 추가도 쉽고, 검색할 때도 대응되는 표에서 찾으면 되기 때문에(물론 대응되는 표를 처음부터 검색해야 하지만 전체를 검색하는 것보다는 낫겠죠?) 상당히 좋은 방법입니다. 하지만, 표를 여러 개 만들어야 하기 때문에 메모리 사용이 많아지는 단점이 있을 것 같아요.

 

자료 구조를 고민해서 메모리 이용 효율을 높인다.

자료 구조에 대한 접근법도 이와 마찬가지입니다. 데이터를 메모리에 저장할 때 목적에 맞게 구조화해서 메모리의 이용 효율을 높여야 합니다.

 

 

참고 - 책 알고리즘 도감