✅자료구조란?

자료구조(Data Structure)는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말합니다. 각각의 자료구조에는 장단점이 있으므로 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있습니다. 그러므로 다양한 자료구조의 장단점을 살펴보며 애플리케이션을 만들 때 어떤 자료구조를 사용하는 것이 최선일지 판단해야 합니다. 

프로그래밍이란 결국 알고리즘을 작성하고, 그에 맞는 자료구조를 선택하는 것이므로 자료구조를 충분히 이해하지 못한다면 결코 좋은 개발자가 될 수 없습니다. 그래서 파스칼을 개발한 스위스의 컴퓨터 과학자 니클라우스 비르트는 ‘알고리즘 + 자료구조 = 프로그램’이라는 유명한 말을 남기기도 했습니다.

알고리즘은 컴퓨터가 무슨 일을 해야 할지 지시하고, 자료구조는 컴퓨터에게 알고리즘에서 사용하는 자료를 어떻게 저장할지 지시합니다. 리눅스를 개발한 리누스 토르발스(Linux Torvalds)는 자료구조의 중요성을 다음과 같이 강조했습니다. 

“형편없는 개발자와 뛰어난 개발자의 차이는 코드를 더 중요하게 생각하는지, 

자료구조를 더 중요하게 생각하는지에 달려있다. 

형편없는 개발자는 코드만 쳐다보고, 뛰어난 개발자는 자료구조와 그들의 관계에 더 집중한다.” 

✅자료구조의 분류

추상 데이터 타입(Abstract Data Type)은 자료구조를 설명하는 데이터의 타입을 말하며, 자료구조는 추상 데이터 타입을 실제로 구현한 결과를 말합니다. 

예를 들어 추상 데이터 타입인 리스트는 각 요소의 위치가 다른 요소에 의해 상대적으로 정해지는 데이터 타입으로, 요소를 추가하거나 제거하는 동작 역시 포함합니다. 반면 파이썬 리스트는 추상 데이터 타입을 실제로 구현한 자료구조입니다. 파이썬에서는 추상 데이터 타입인 리스트를 기반으로 파이썬 리스트와는 완전히 다른 자료구조를 만들 수 있습니다.

자료구조는 선형과 비선형 등의 여러 속성을 기반으로 분류할 수 있습니다. 선형 자료구조(Linear Data Structure)는 데이터 요소를 순서대로 정렬하며, 비선형 자료구조(Nonlinear Data Structure)는 데이터를 비연속적으로 연결합니다. 예를 들어 파이썬의 리스트는 각 요소의 앞과 뒤에 다른 요소가 있는 선형 자료구조인 반면, 그래프는 각 요소가 다른 여러 요소와 연결될 수 있는 비선형 자료 구조입니다.

자료구조를 순회(Traverse)한다는 말은 자료구조의 첫 번째 요소에서 출발해 마지막 요소로 이동한다는 뜻입니다. 선형 자료구조에서는 첫 번째 요소에서 마지막 요소까지 백트래킹(Backtracking)없이 쉽게 순회할 수 있지만, 비선형 자료구조에서는 종종 되돌아가야 합니다. 

비선형 자료구조에서는 원하는 요소에 접근하기 위해 백트래킹이나 재귀가 필요한 경우가 많기 때문에 개별 요소에 접근하는 작업에는 선형 자료구조가 더 효율적입니다. 또한 선형 자료구조는 데이터를 쉽게 순회할 수 있어 비선형 자료구조에 비해 요소 전체를 변경하는 작업이 쉽고, 백트래킹 없이 모든 요소에 접근할 수 있어 자료구조를 설계하고 사용하는 것도 더 쉽습니다. 그러나 비선형 자료구조는 특정한 몇 가지 문제에 대해 더 효율적인 방법일 수 있습니다. 예를 들어 소셜 네트워크의 연결과 같은 데이터는 선형 자료구조로 저장하기에는 비효율적이고, 비선형 자료구조가 더 알맞습니다.

정적인지 동적인지에 따라 자료구조를 분류하기도 합니다. 정적 자료구조(Static Data Structure)는 크기가 고정되어 있는 자료구조를 말하며, 동적 자료구조(Dynamic Data Structure)는 크기가 바뀔 수 있는 자료구조를 말합니다. 보통 정적 자료구조는 프로그램을 생성할 때 크기를 정의합니다. 한 번 정적 자료구조를 정의하면 그 크기는 고정되어 바꿀 수 없지만, 안에 저장된 데이터의 값은 바꿀 수 있습니다. 파이썬에는 정적 자료구조가 없지만, C와 같은 저수준 프로그래밍 언어는 정적 자료구조를 지원합니다.

정적 자료구조에는 반드시 일정량의 메모리를 할당해야 한다는 문제가 있습니다. 컴퓨터 메모리는 데이터를 저장하는 공간입니다. 메모리에는 다양한 종류가 있지만, 이를 모두 설명하는 것은 책의 범위를 벗어나므로 메모리가 컴퓨터가 데이터를 저장하는 공간이며, 주소를 통해 접근할 수 있다는 것만 알면 됩니다. 할당한 메모리보다 사용하는 데이터 요소가 적다면 메모리를 낭비한 것입니다. 또한 처음 할당한 메모리보다 많은 요소를 추가할 수도 없습니다.

정적 자료구조에 요소를 추가하려면 새로운 자료구조를 만들어 기존 요소와 새로운 요소를 모두 담을 정도로 충분히 큰 메모리를 다시 할당한 다음, 기존 구조를 새 구조에 복사하면서 새로운 요소도 함께 추가하는 것이 유일한 방법일 때가 많습니다. 따라서 저장할 요소의 개수를 미리 알 수 없다면 정적 자료구조는 좋은 선택이 아닙니다. 그러나 저장할 요소의 개수를 미리 알고 있고, 그 개수가 변하지 않는 상황이라면 정적 자료구조가 동적 자료구조보다 뛰어난 성능을 보일 때가 많습니다. 예를 들어 사용자가 프로그램에서 ‘실행 취소’ 작업을 수행할 수 있고, 실행 취소 목록을 최대 10개까지 만들 수 있다면 정적 자료구조가 적합할 수 있습니다.

자료구조 중 상당수는 정적일 수도 있고 동적일 수도 있습니다. 배열은 보통 정적 자료구조로 구현하지만 파이썬 같은 최신 프로그래밍 언어에서는 동적 배열(리스트)을 지원합니다.

동적 자료구조는 정적 자료구조와 달리 크기를 자유롭게 바꿀 수 있습니다. 동적 자료구조에서는 요소를 추가할 때 컴퓨터가 추가로 메모리를 할당하고, 요소를 제거할 때 메모리를 비워 다른 데이터가 사용할 수 있도록 만듭니다. 크기가 고정되어 있지 않은 동적 자료구조는 효율적으로 요소를 추가하거나 제거할 수 있어 메모리를 더 효율적으로 사용합니다. 하지만 정적 자료구조에 비해 요소에 접근하는 작업이 느릴 수 있고, 일정 수의 요소를 저장한다고 할 때 정적 자료구조보다 더 많은 메모리를 사용할 수 있습니다. 저장해야 할 데이터의 양을 특정 할 수 없고, 특히 메모리 공간이 한정적일 때는 동적 자료구조가 더 나은 선택인 경우가 많습니다.

운영 체제에 사용할 저수준 코드를 작성하거나 활용 가능한 최적화 수단을 모두 동원해 극한의 효율을 쥐어짜야 하는 상황이 아니라면 정적 또는 동적 자료구조를 선택하는 데 시간을 허비할 필요가 없습니다. 그보다는 선형 또는 비선형 자료구조 중 무엇을 택할지에 집중하는 것이 더 효율적입니다. 이미 언급했듯이 자료구조에는 저마다의 장단점이 있습니다. 이러한 장단점은 주로 데이터의 삽입과 삭제, 탐색의 효율성과 관련되며, 메모리 공간을 얼마나 효율적으로 사용하는가에 달려 있습니다. 예를 들어, 파이썬의 딕셔너리는 수십억 개의 데이터가 들어있다고 해도 순식간에 요소를 탐색합니다. 하지만 이렇게 효율적인 구조라 하더라도 특정 문제에서는 그래프에서 데이터를 탐색하는 것보다 비효율적일 수 있습니다.

위 콘텐츠는 『나의 첫 알고리즘 + 자료구조 with 파이썬』의 내용을 기반으로 작성되었습니다.