[자료 구조 & 알고리즘]자료구조와 알고리즘(Algorithm)의 관계

목차 1. 자료구조란? 2. 자료구조와 알고리즘의 관계 3. 알고리즘 표기법 4. 일반 표기법 vs 서적 표기법 5. 자료구조의 추상 데이터 타입 6. 추상 데이터 타입(ADT)란?

# 자료구조란?

1. 자료를 저장, 관리, 조직하는 방법

2. 문제 해결에 사용할 부품

3. 생각하는 방법을 훈련하는 도구

 

일반적으로 다루는 자료구조는 리스트, 스택, 큐, 힙, 검색트리, 해시 테이블, 그래프 등이 있으며, 생각하는 방법에는 재귀, 추상화, 정렬, 그래프 등이 있습니다. 

 

// "알고리즘"도 "자료구조"에 포합니다.

// 스택 : 먼저 들어간 이가 늦게 나옴

// 큐 : 먼저 들어간 이가 먼저 나옴

 

- 선형 자료 구조 : 리스트, 스택, 큐

- 색인 자료 구조 : 검색 트리(이진, 균형 트리), 해시 테이블 (테이터를 효율적으로 찾기 위해)

- 효율적인 자료 구조 : 우선순위 큐 : 힙 ( 우선순위를 다루는데 유용 )

- 관계 처리 자료 구조 : 그래프 ( 개체나 대상들의 관계 표현에 유용 )

 

# 자료구조와 알고리즘의 관계

자료구조는 데이터를 구조화하고 관리, 저장하는 방법을 다루고, 알고리즘은 자료구로를 활용하여 데이터를 처리하고 조작하는 방법을 다룹니다.

 

# 알고리즘 표기법

가장 좋은 방법은 "가상 코드"를 활용한 표기법이며, 이는 프로그래밍 언어로 표현했을 때 생기는 단점을 보완한 방법입니다. 프로그래밍 언어의 형태를 갖춘 가상코드(Pseudo-Code)로 알고리즘을 표현합니다. 일반적인 프로그램밍 언어와 형태가 유사해 원하는 특정 프로그래밍 언어롤 구체화하기 쉽습니다.

 

# 일반 표기법 vs 서적 표기법

- 일반 표기법

move(n, a, b, c) {     if(n>0) then {         move(n-1, a, c, b);         a에 있는 원반을 b로 옮기기         move(n-1, c, b, a);     } }

- 서적 표기법

move(n, a, b, c):     if(n>0)         move(n-1, a, c, b)         a에 있는 원반을 b로 옮기기         move(n-1, c, b, a)     else         에러처리

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

자료구조와 추상 데이터 타입이 대체 무슨 관계일까? 라고 생각할 수 도 있습니다.

 

결론부터 말씀 드리자면 자료구조에서는 밑에 예시 처럼 어떤 대상이 지원하는 작업을 나열해 표현하는 것을 추상적으로 표현한다 라고 하며, 그렇게 표현하는 것은 추상 데이터 타입이라고 합니다.

 

자료구조는 데이터를 구성하고 조직하는 방법을 구체적으로 나타내며, 이를 실제로 구현하는 데 관련이 있습니다. 예를 들어, 배열, 연결 리스트, 스택, 큐 등은 모두 데이터를 저장하고 조작하는 구체적인 방법을 제공하는 자료구조입니다.

반면에 추상 데이터 타입 (ADT)은 데이터와 해당 데이터에 대한 연산을 추상적으로 정의하는 개념입니다. ADT는 어떤 데이터 타입이 어떤 연산을 지원하는지를 나열하는 추상적인 명세를 제공합니다. 이것은 사용자에게 데이터와 연산의 인터페이스를 제공하며, 구체적인 구현 내용은 숨겨져 있습니다.

 

예를 들어서

n 번째 자리에 새 원소 넣기 원소 x 찾기 n 번째 원소 삭제하기

원소를 첫 번째, 두 번째, ..., n 번째 원소를 가리킬 수 있는 자료구조

# 추상 데이터 타입란?

추상 데이터 타입은 데이터와 그 데이터에 대한 연산을 추상적으로 정의하는 개념입니다. ADT는 데이터와 해당 데이터를 조작하는 함수 또는 연산을 묶어 놓은 것으로, 어떤 데이터 타입이 어떤 연산을 지원하는지를 정의합니다. ADT는 이러한 연산의 명세를 제공하며, 실제 구현 내용은 추상화되어 있습니다. 이것은 데이터와 연산의 분리를 의미합니다. 예를 들어, 스택 ADT는 다음과 같은 추상 연산을 제공할 수 있습니다.

Push(): 스택에 원소를 추가합니다.
Pop(): 스택에서 원소를 제거하고 반환합니다.
Peek(): 스택의 맨 위 원소를 반환합니다.
이러한 연산은 스택의 추상적인 동작을 정의하고, 실제 구현은 스택을 어떻게 배열 또는 연결 리스트로 구현할지에 따라 달라집니다.

자료구조는 ADT의 구현 방법 중 하나일 뿐입니다. 자료구조는 데이터를 물리적으로 구성하고 저장하는 방법을 정의하며, ADT는 데이터와 그 데이터에 대한 연산을 추상화하고 정의하는 방법을 제공합니다. 즉, 자료구조는 ADT의 구체적인 구현이 될 수 있습니다.

요약하면, 자료구조는 데이터를 구조화하고 조직화하는 방법을 제공하며, 추상 데이터 타입은 데이터와 그 데이터에 대한 연산을 추상적으로 정의하는 방법을 제공합니다. 추상 데이터 타입은 자료구조를 설계하고 사용하는데 도움을 주는 개념 중 하나입니다.