데이터 구조란?

지난 글: [알고리즘] - 계산 시간을 표현하는 방법

 

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

컴퓨터 안에서 데이터는 메모리에 저장된다. 메모리는 상자가 일렬로 나열된 형태를 하고 있으며 하나의 상자 안에 하나의 데이터를 저장한다. 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계 등을 정하는 것이 '데이터 구조'이다.

 

전화번호부의 데이터 구조

알기쉬운 예로 전화번호부를 생각해보자. 여기서 전화번호부는 수기로 작성하는 것이다.

 

ex1) 위에서부터 차례로 추가

전화번호부를 관리하는 가장 일반적인 방법은 전화번호를 얻을 때마다 종이 위에서부터 차례로 기입하는 방법이다. 만약 '김예찬'이라는 사람을 찾아서 전화하고 싶다. 그러면 전화번호는 단순히 번호를 받은 순서로 저장되어 있기에 앞에서부터 순서대로 찾는 방법뿐이다. 이는 저장되어 있는 번호가 많아질수록 찾기가 힘들어진다. 

 

ex2) 이름을 가나다순으로 관리

이름을 가나다순으로 관리한다면 이는 이름이 사전순으로 나열된 것이기에 이 데이터들은 '데이터 구조'를 갖는다. 이 구조에서는 원하는 사람을 찾기가 쉽다. 이름의 첫 자를 가지고 저장된 대략적인 위치를 추측할 수 있기 때문이다. 만약 성이 '최'씨인 사람을 전화번호부에 추가한다면 'ㅈ'의 성씨와 'ㅌ'의 성씨 사이에 추가해야하는데 이미 기입이 끝난 상태이기에 빈칸이 없다. 그러므로 'ㅈ'성씨 이하의 전화번호를 하나씩 아래로 내려야한다. 이를 위해서는 '행의 내용을 한 줄씩 아래로 내리고 원래 행을 지우는 작업'을 아래에서부터 순서대로 해야한다. 하지만 이는 저장되어 있는 번호가 많을수록 작업시간이 길어진다. 

 

각각의 장단점

앞의 예를 정리하면 데이터가 온 순서대로 나열하는 방법은 데이터 추가 시 가장 뒤에 작성하면 되는 편리함이 있지만 검색에 많은 시간이 걸린다. 반대로 데이터를 가나다순으로 나열하는 방법은 검색은 쉽지만 데이터 추가가 어렵다. 

 

양쪽 모두 장단점이 있고, 어느 방법을 선택할지는 전화번호부를 어떻게 사용할지에 달렸다. 한 번 만든 후에는 변경될 가능성이 없다하면 후자가 적합하다. 반대로 데이터 추가 빈도는 높지만 검색은 거의 하지 않는다면 전자가 적합하다.

 

선착순과 가나다순을 조합

이 두 가지 방법을 섞어 장단점을 보완하는 방법도 생각해보자. '가행', '나행', '다행'처럼 행마다 별도의 표를 만들어 관리하는 방법이다. 이렇게 하면 새로운 데이터를 추가할 때는 대응되는 표의 끝에 추가하면 되고, 데이터 검색할 때는 대응되는 표만 찾으면 된다. 

 

데이터 구조를 고민해서 메모리 이용 효율을 높인다

데이터 구조에 대한 접근법도 이와 같다. 데이터 메모리에 저장할 때 목적에 맞게 구조화해서 메모리의 이용 효율을 높여야 한다. 

 

오늘 배운 내용은 지난 번보다 훨씬 쉬웠다. 또, 데이터 구조를 고민하는 예를 전화번호부로 쉽게 들어주어 이해에 굉장히 도움이 되었다.

 

참고 서적: