자료구조? 알고리즘? 추상 자료형?

컴퓨터가 기본적으로 하는 일

 - 데이터 저장

 - 데이터 연산

 

자료구는 데이터를 '저장'할 때 알고리즘은 데이터를 '연산'할 때 어떻게 하면 컴퓨터가 처리하기 쉽게 만드는 지 다루는 것을 이야기 한다.

자료구조 (Data Structure)는 자료를 저장하는 방법을 알고

알고리즘 (Algorithm)은 문제를 효율적으로 해결하기 위한 방법을 안다.

 

알고리즘을 대충 짜고 항상 배열 자료구조만을 사용해도 동작은 하겠지만 메모리를 효율적으로 사용하고

알고리즘의 성능을 높이기 위해 어느 정도 규모가 넘어간다면 그에 가장 적합한 자료구조와 알고리즘을 선택해야 한다.

---

ADT( Abstract: 추상 Data Type ) 추상적 자료형

추상적 자료형이란 자료들과 그 자료에 대한 연산들을 명기(明 밝을 명 記 기록할 기 : 똑똑히 밝히어 적음)한 것이다.

 

자료형 : 데이터를 식별하는 구분, 연산, 저장 방법등을 모두 표현 하는 것!

 區 구분 할 구 分 나눌 분 따로따로 갈라 나눔

 演 펼 연 算 셈 산 숫자로 식이 보이는 대로 그 답을 내는 일 계산의 방식

 貯 쌓을 저 藏 감출 장 물건을 쌓아서 간직하여 둠 모아두는 일

 

추상화 : 핵심 개념이나 기능을 간추려 내는 것 => 개념을 만들어 가는 과정

 - 자료구조에서 추상화는 세부 구현으로부터 분리하여 개념을 일반화 시키는 것을 의미( 데이터 모델링 )

 - 무엇(what) 인지는 정의하지만 어떤 언어를 사용해서 어떻게(how) 구현할 것인지는 정의하지 않음.

 

추상 자료형 (Abstract Data Type : ADT) => 세부 구현으로부터 분리해 핵심 개념이나 기능을 간추려 낸자료형

// 구현 내용은 명시하지 않고 인터 페이스만 제공

 

추상 자료형은 객체지향의 Class 또는 현실의 사용 설명서(User's Guide)와 유사하다.

 => 기능의 구현 부분은 나타내지 않고 데이터의 형태와 그 데이터의 연산들을 정의한 것이다.

<> 우리가 아는 자료구조 (Data Structure)는 추상 자료형이 정의한  연산들을 구현한 구현체를 가리킨다.

<> 즉 추상 자료형은 구현 방법을 명시하고 있지 않다는 점에서 자료구조와는 다르다.

구현 具 갖출 구 現 나타날 현 : 어떤 내용이 구체적인 사실로 나타나게  함.

 

Ex )

스택 (Stack)의 형태는 LIFO( Last In First Out) 값들의 모임이며 push, pop, size등의 연산으로 정의 할 수 있다.

 => 추상 자료형 (Abstract Data Type) // 개념 정의 최소한의 것만 놔둠 나중에 들어온 것 먼저 나감? 스택

스택 (Stack)이 내부적으로 배열로 구현되는 지 연결 리스트로 구현되는 지 또는 size 연산을 수행할 때 원소의 개수를 일일이 세는 지 아니면 개수를 따로 저장해 두는 지와 같은 세부 사항들을 다루어 구현했다

 => 자료구조 (Data Structure) // 개념 정의를 내가 원하는 방식, 내게 적합한 방식으로 구현한 것! 스택을 배열 자료구조를 쓸것 // 구현? 스택 자료구조

 

추상 자료형과 그것을 구현한 자료구조의 이름이 비슷하거나 아예 같은 경우가 많다. 이를 구분하는 법은 조금이라도 구현 방법이 정해져 있는지 보는 것이다. 자바(Java)로 치면 클래스인지 인터페이스인지를 확인하면 된다. 스택이나 큐는 구현 방법이 전혀 정의되어 있지 않으니 추상 자료형이고, 배열은 연속적으로 저장되어 있도록 구현되어 있어야 하므로 자료구조이며, 연결 리스트도 다음 데이터의 위치를 저장하는 방식으로 정해져 있으니 자료구조이다. 이렇듯 추상 자료형은 구현 방법을 명시하고 있지 않다.

 

---

추상적 자료형이 가장 high level의 개념이고 알고리즘으로 갈수록 구체적인 방법론이 된다

 

// 연결된 데이터 보관함이 필요해 // 리스트 추상적 자료형 쓰자 // 근데 update나 delete 보다는 조회 기능이 더 많이 필요할 거 같애 // 연결리스트 말고 배열 자료구조를 사용하자!