추상 자료형(abstract data type, adt)
추상적으로 정의된 자료형이다
추상 : 세부적이고 복잡한 것을 생략
대표적인 것, 중요한것만을 나타낸다
-자료구조를 기술하는 가장 대표적인 방법 중 하나
정보은닉 >중요한 정보만을 나타내고 중요하지 않은 것은 숨김
인터페이스(겉) 내부 구현 로직
자료구조를 사용할 수 있는 인터페이스(interface) 정의, 자료구조의 연산(operation)들의 정의
자료형 (data type) 자료 + 연산 =명령
예) 정수 자료형(int) 자료(data)-1,2,3,4 명령-더하기 빼기 곱하기
추상 자료형 MyPosition
x좌표 y좌표의 위치를 나타내는 정수(자료)
명령
| 이름 | 입력(input) | 출력(output) | 설명 | |
| 변경 | modify() | 1.위치자료 :p 2.x축변경거리 :x 3.y축 변경 거리 :y |
n/a (없음) | 위치 p에서 x축으로 x만큼 y축에서 y만큼 변경 |
| 위치 사이 거리 계산 | distance() | 위치자료 p1 위치자료 p2 |
두 위치 사이의 거리 | 두 위치 p1 p2 사이의 거리를 구한다 |
| 위치비교 | equal() | 위치자료 p1 위치자료 p2 |
true or false | 두 위치 p1 p2가 같은 위치인지 조사 |
자료구조를 이용하는 사용자의 관점
자료구조의 내부 구현 소스에 대한 분석없이 신속하게 자료구조를 이용가능 (이름, 입력, 출력) “인터페이스“
개발자의 관점
자료구조를 구현하기 전에 설계도를 미리 그려보는 것
자료구조의 개발자와 사용자 사이의 간섭 문제가 해결 (사용자는 자료구조가 아닌 인터페이스만 보기 때문)
알고리즘(algorithm)
넓은의미 : 자료구조와 함께 컴퓨터 프로그램을 구성하는 한가지 요소이다
명령어들의 집합이다
좁은의미 : 어떠한 문제를 해결하기 위한 절차이다
예) 1부터 100까지 합을 구하는 문제 pseudo code(의사코드)
알고리즘의 필수 5가지 특성
- 입력 : 외부에서 제공되는 자료가 0개이상 있어야 한다.
- 출력 : 적어도 1개이상의 결과를 만들어야 한다 .
- 명백성(definiteness): 각 명령어는 의미가 모호하지 않고 명확해야 한다.
- 유한성(finiteness) : 한정된 수의 단계되에는 반드시 종료된다. 무한히 동작해서는 안된다.
- 유효성(effectiveness) : 모든 명령은 실행가능한 연산이어야 한다
알고리즘과 자료구조와의 관계
- 알고리즘의 성능은 자료구조에 종속된다
- 같은 자료라 하더라도 어떻게 표현되고 저장되느냐에 따라 사용가능한 알고리즘이 달라진다
- 자료구조의 기본적인 연산을 구현하기 위해서 알고리즘이 사용된다
알고리즘의 표현 : 주로 순서도와 의사코드가 쓰인다.
| 종류 | 내용 | 특성 |
| 자연어 | 사람이 사용하는 일반적인 언어로 표현 | 알고리즘 표현으로 부적절 일관성과 명확성이 떨어짐 |
| 순서도 (flow chart) |
알고리즘을 그림으로 도식화해서 표현 | 장점: 알고리즘 각 단계를 직관적으로 표현 단점 : 복잡한 알고리즘 표현에는 비효율적 |
| 의사 코드 (pseudo code) |
특정 프로그래밍 언어가 아닌 가상의(유사한) 언어로 표현 | 프로그래밍 언어보다는 덜 엄격한 문법이나, 자연어보다는 더 체계적으로 기술가능 자료구조/알고리즘 책마나 약간씩 구문에 차이가 있다. 책에따라 가상코드, 유사코드 슈도 코드 등으로 불린다 |
| 프로그래밍 언어 | c와 같은 프로그래밍 언어로 포현 | 추가 구현단계가 필요없다는 장점 (알고리즘을 구현소스를 통해 나타내기 때문) 너무 엄격하게 기술하여 비효율적인 경우가 있다. |