[자료구조 스터디] 2. 자료구조와 알고리즘

[자료구조 스터디] 2. 자료구조와 알고리즘

1. 자료구조와 알고리즘의 관계
2. 알고리즘 표기법
3. 자료구조의 추상 데이터 타입

---

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

-알고리즘 Algorithm: 문제를 해결하기 위해 입력받아, 원하는 출력을 만들어내는 과정
-자료구조는 그 자체로 여러 알고리즘을 포함한다.

자료구조와 알고리즘은 긴밀한 관계다. 자료구조는 원두, 알고리즘은 커피를 만드는 방식(드립, 프렌치, 모카포트 등등...) 에 비유할 수 있다!

 

---

2. 알고리즘 표기법

-알고리즘을 만들 때에는 과정을 애매하지 않게 기술해야 한다.
-알고리즘은 다양한 방식으로 표현할 수 있다.
 
(1) 자연어를 이용한 서술적 표현
-사람이 사용하는 자연어(언어/ex: 영어, 한국어, 중국어 등등...)으로 표현하는 방법.
-서술적이고, 화자에 따라 일관성이나 명확성을 이해하기 어렵다.
 
(2) 순서도를 이용한 도식화
-순서도(Flow chart)로 표현하는 방법.
-명령의 흐름을 쉽게 파악할 수 있지만, 알고리즘에 복잡해지면 표현하기 어렵다. 
 
(3) 프로그래밍 언어를 이용한 구체화
-알고리즘 자체를 프로그래밍으로 구현하는 방법.
-하지만 해당 프로그래밍 언어를 모르면 이해하기 어렵다. (범용성 낮음)
 
(4) 가상코드를 이용한 추상화
-(3)을 보완하기 위해 나온 방법. (=ADL/알고리즘 기술 언어)
-프로그래밍 언어의 형태를 갖춘 가상 코드(Psedo-Code)로 표현한다. 
-실제로 실행할 순 없지만, 특정 프로그래밍 언어로 구체화시키기 쉽다.

순서도 (좌측) / 알고리즘 기술 언어의 예시. (출처: wikihow)

 

---

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

(1) 추상(Abstract): 미술, 음악에서의 '추상'과 프로그래밍에서의 '추상'은 비슷한 개념이다.
-논문의 '초록'역시 영어로 Abstract이다. 초록은 논문을 추상화해 표현한 것이다. (=전체적인 요약본) 
-프로그래밍에서의 추상 = 관점이 계층화되어 상승한 것. 상위의 고급 개념을 만들어나가는 지적 발전의 단계.
 
(2) 모듈(Module): 의미의 단위.
-모듈을 추상화하는 것=세부 사항을 생략하고, 가장 중요한 기능만 드러내는 것. 
 
(3) 추상 데이터 타입(ADT)
-기초 데이터 타입(byte,int,float,boolean...) 외의 데이터 타입들에는 추상적 성격이 있다.
-추상 데이터 타입(ADT; Abstract Data Type)은 세부 사항에서 벗어나 추상적으로 정의한 데이터 타입이다. 
=> 어떤 데이터 타입이 어떤 작업으로 이루어지는 지만 표현한 것. (ex: 배열, 인터페이스)
 
*추상 데이터 타입(ADT)은 프로그래밍 작업을 보다 효율적으로 하기 위해 존재한다.
=>즉, ADT는 내부에서 작업을 어떻게 하는지보다는, '무엇을 하는지'에 집중하게 해준다.