[자료구조/알고리즘] Chapter 01. 자료구조란?

해당 시리즈는 제가 책(쉽게 배우는 자료구조 with 자바)을 읽고 해당 내용을 정리하기 위하여 작성되었습니다.

어렵다고 느껴지는 자료구조를 최대한 쉽게 설명하고자 풀어쓰는 점 참조해주시고,

같이 자료구조/알고리즘에 대해 공부하는 시간이 되었으면 좋겠습니다. 감사합니다.

---

자료구조?

데이터를 저장, 조직, 관리하는 방법

 

서점이나 도서관을 가면 어떻게 내가 원하는 책을 바로 찾을 수 있을까요?

책이 10권 이내라면 아무 기준없이 쌓아둬도 내가 원하는 책은 쉽게 찾을 수 있을 것입니다.

 

허나 책이 100권, 1000권, 1만권이 넘어간다면? 이때부터는 종류별로 분류가 필요합니다.

이처럼 책(자료)을 효율적으로 관리하는 방법을 '자료구조'라고 합니다.

이러한 자료구조는 일상생활에서 쉽게 찾아볼 수 있습니다.

 

문제 해결에 사용할 부품

 

그럼 알고리즘은 무엇일까요?

어떠한 문제를 해결하기 위한 일련의 순서를 만들어내는 과정을 기술한 것을 알고리즘이라 합니다.

이 때 자료구조는 알고리즘을 수행할 수 있게 도와주는 '부품' 역할을 합니다.

 

예를 들어, 건축 재료와 구조물에 대해 몰라도 집을 지을 순 있지만 효율적이고 튼튼한 집을 짓기는 어렵습니다.

콘크리트나 철골이라는 재료를 몰라 돌과 짚을 이용해 집을 짓는 것처럼 말이죠.

 

돌과 짚을 이용해 만든 집도 집이긴 하지만..

현대에는 돌과 짚보다 훨씬 좋은 재료들이 많습니다.

 

이처럼 알고리즘이 복잡할 수록 자료구조를 사용한 결과물은 간편하고 유지보수하기도 쉬워집니다.

 

자료구조의 종류와 자바의 컬렉션 패키지

 

출처 : https://www.lavivienpost.com/data-structures-and-java-collections/

자료구조는 데이터를 저장하고 조작하기 위한 다양한 방법을 제공합니다. 자바에서는 배열, 리스트, 행렬, 스택, 큐, 그래프, 트리, 최대 힙 등의 자료구조를 기본적으로 제공합니다. 하지만 모든 상황에 최적화된 자료구조가 항상 있는 것은 아니므로, 필요에 따라 직접 자료구조를 만들어 사용할 수도 있습니다. 이를 위해서는 자료구조의 내부 작동 원리를 잘 이해해야 합니다.

 

• 리스트, 스택 큐: 데이터가 한 줄로 배치되는 선형 자료구조
• 검색 트리, 해시 테이블 : 데이터를 효율적으로 찾기 위한 구조, 즉 색인을 위한 자료구조
• 힙 : 우선 순위를 다루는 자료구조
• 그래프 : 개체나 대상들의 관계를 표현하는 자료구조

자료구조의 추상 데이터 타입

추상

 

'추상'에 관해서는 제 블로그에서 객체지향의 4대 특성을 다룰 때 자세히 언급했었는데요.

자료구조에서도 '추상'이란 개념은 굉장히 중요합니다! 이미 잘 알고 계시겠지만 한 번 더 짚고 넘어가도록 하겠습니다.

 

예술계(미술, 음악)에서 추상이 의미하는 바는 "사물의 사실적 재현, 특정한 이미지 혹은 상징적 의미를 표출하는 것이 아닌 순수한 예술성을 추구하는 것" 입니다. 자료구조에서 말하는 '추상'이란 의미도 크게 다르지 않습니다.

 

점, 선, 음 같은 가장 하부 단위의 관점이 계층화하면서 작품이 만들어지듯 하위의 개념들을 결합하여 상위의 개념을 만들어나가는 단계 입니다. 하여 프로젝트나 문제 해결 과정에서는 의미 단위를 분리하고 계층화하는 작업이 반복됩니다.

(객체 지향의 클래스)

 

의미 단위는 모듈이라고도 합니다. 모듈을 추상화 한다는 것은 '세부 사항을 생략하고 가장 중요한 기능만 드러내는 것'을 의미합니다.

 

모듈을 추상화하는 것이 자료구조의 핵심이라고 할 수 있습니다.

 

추상 자료형: ADT

 

추상 자료형(Abstract Data Type)은 데이터의 논리적 구조와 연산의 집합을 정의한 것입니다. 즉, 추상 자료형은 데이터와 그 데이터에 대한 연산을 묶어 놓은 개념적인 틀이라고 볼 수 있습니다.

추상 자료형은 데이터와 연산의 구체적인 구현 방법에 대해서는 규정하지 않습니다. 즉, 추상 자료형을 사용하는 프로그래머는 데이터와 연산에 대한 명세만을 알고 있으면 됩니다. 따라서 추상 자료형은 데이터의 표현 방법과 그에 따른 연산의 구현 방법을 감추어, 사용자가 보다 쉽게 데이터를 다룰 수 있도록 해 줍니다.

예를 들어, 추상 자료형으로 스택(Stack)을 정의하면, 스택의 연산에는 push(데이터 추가), pop(데이터 삭제), top(스택의 맨 위에 있는 데이터 조회) 등이 있습니다. 이 연산을 사용하면 데이터를 삽입, 삭제, 조회할 수 있으며, 이 연산들이 어떻게 구현되었는지는 사용자가 알 필요가 없습니다.

따라서, 추상 자료형은 데이터 구조를 추상화하고, 구현 세부 사항을 숨기는 기술로, 프로그래머에게 코드의 재사용성, 유지보수성, 그리고 코드의 가독성을 향상시키는 데 도움을 줍니다.

 

자바에서는 추상 자료형을 나타내기 위해 인터페이스(interface)를 사용합니다. 

---